I have got a baby niece. She completed a total of three years on this planet. To celebrate her existence, I decided to teach her about linked list. She has kept me up so many nights with her shrieks. So, I made a little game. I told her she will be given a bunch of clues and if she guesses it properly, she gets her gift s. Jumping, she goes to her Mom. With the third gift in her hand, she listens to her next clue which is given by her Mom. With all four gifts in her hand, the birthday gift hunt came to an end for her. But, with it, comes the beginning of an understanding of linked list for us. What is Linked List in Data Structures. Let me get you a formal definition and of course not-so-formal one where we unpack the jargon. Formal Definition: A linked list is a collection of multiple nodes where each node stores a reference to a data, as well as a reference to the next node of the list A Not-So-Formal-Definition: A linked list is a collection of multiple birthday presents where each present comes in two parts, one gift and a clue to get next gift. Oh yeah, our above birthday gift hunt example was nothing less than a linked list. You know what was a node in our above example. In above example, head node is at memory address 204. So, I was the head of the list in our gift hunt. Traversing The Linked List: So, like we discussed before, we only know the address of our head node which resides in memory address 204. Off to the head node and ask it if it can tell us where the next node lies. It looks at the address part of its node and passes us the address of next node which is 217. Again, we repeat the same steps, we go to node residing at address 217 and ask it to share the memory address of the next node. This empty node can be used to identify the end condition of the Linked list. The last node in the list with no address is known as the tail node. B: This is still ordered data. But, just has a specific sequence of nodes with data and link to the next node Array Vs Linked List: Bunch of nodes each storing data and address. Kind of work which our can do quite easily. Why bother studying linked list then. Direct access Versus Sequential access: Herein lies the major difference between a simple array and linked list. The way both these data structure are stored in the memory is very different. Simple Array in Memory: While storing elements of an array — whatever they are, integers, strings, references of objects — always imagine them stored in a contiguous area of memory. Meaning the elements are next to each other. Did you guess it right. The Mighty indexes of arrays. The only operation which requires going through each and every single element in the array is a linear search. Singly linked list vs doubly linked list that, array supports direct access to the individual element. Head node can help us with addresses of other nodes easily. So, nodes do not need to be located next to each other. They can be scattered anywhere in the memory. We have no concept of index numbers in Linked List. Also, if needed array too can perform the sequential access. All we have to do it put a for loop, look at each element. Because, it makes addition and removal of elements from collection much, much easier as compared to an array. Inserting Or Deleting An Item In Array: We know arrays are stored in contiguous space in memory, now to insert a new element in position 2 requires all elements to be shuffled around. Same goes if the element is deleted from any position. We need to maintain its meaningful index order. But reshuffling the items can be very demanding. Now instead of four gifts, I decided to give her only three gifts by excluding gift given by myself. Since I was the head node, before we get rid of it, we need to make next node as head node Head node is the entry point which knows about the entire list. We need a head node no matter what Something like this: L. First, we check whether our list has a head node. Total Cost Of Operation: O 1 Okay, one last one. Adding A Node At The End: Time to add one more present after Gift 4. Total Cost Of Operation: O 1 Similarly, removing a node from the end will be O 1 operation. Everything still follows a sequence, no nodes need to be changed or shuffled around. Now, imagine, even if we had a very large data, adding elements to a linked list always takes the same amount of time whether the list is small or large. Something, which our array becomes inefficient at when the array is dealing with lots of data. Different Types Of Linked List: The specific idea of a linked list singly linked list vs doubly linked list we discussed above so far is called a singly linked list. Follow each clue and reach Node no 3. So, you reached Node 3. Time to delete it and make Node 2 next field point to Node 4. How do we access Node 2. What is Doubly Linked List. Works just like the single linked list but just with one extra superpower: Power to visit the past node. Simply, by storing one additional piece of information for each node. In the doubly linked list, we have reference to next as well as previous node. Just like the singly linked list, these nodes can be located anywhere in the memory. But each node has two references. A reference to the next node and a reference to the previous node. Coming back to our removing node from center example, since doubly linked list allows us to go forward and backward, we can easily access node no 2 and make its next field point to Node 4. Now, with the doubly linked list, we do the same thing with the previous link of head node too. So, it either stores null or points to the sentinel or terminator. What is a Circular Linked List. Just like doubly or single linked list, just with one difference. But if we get to the end of the list and singly linked list vs doubly linked list next, we just start again at the beginning. If we follow the tail node next field, we will get the head node. Round robin scheduler can be implemented using circular linked list and the queue data structure. There are several operations performed on the linked list and the names can sometimes be different in various environments and libraries. But normally the operations provided below cover most of them. If not present, the list is empty. Big O Complexity For Operations On Singly Linked List: Singly Linked List Operation Names No Tail Pointer With Tail Pointer Add Element At The Front PushFront element O 1 Return Front Element TopFront O 1 Remove Front Element PopFront O 1 Add Element At The End PushBack element O n O 1 Return Last Element TopBack O n O 1 Remove Last Element PopBack O n O 1 Find A Element In The List Find element O n Delete A Element From The List Erase element O n Checking If The List Is Empty Empty O 1 Adding A Element Before a Node AddBefore Node,element O n Adding A Element After A Node AddAfter Node,element O 1 But, We know how to make popping the element at the end and adding before cheap. Yes, you guessed it right. We can do it by using doubly linked list. Thanks to the prev pointer, we can easily track the previous node. So, to remove the last element, all we have to do it, go to the last node, check its prev field and move the tail pointer to the node address present in prev field. Big O Complexity For Operations On Doubly Linked List: Singly Linked List Operation Names No Tail Pointer With Tail Pointer Add Element At The Front PushFront element O 1 Return Front Element TopFront O 1 Remove Front Element PopFront O 1 Add Element At The End PushBack element O n O 1 Return Last Element TopBack O n O 1 Remove Last Element PopBack O n O 1 O 1 Find A Element In The List Find element O n Delete A Element From The List Erase element O n Checking If The List Is Empty Empty O 1 Adding A Element Before a Node AddBefore Node,element O n O 1 Adding A Element After A Node AddAfter Node,element O 1 Applications on Linked List: Linked List is a very popular dynamic data structure. So, all the applications of these data structures can be implemented with the linked list as well. I am passionate about designing Automation Frameworks that are effective and easy to maintain. Please connect with me at or follow me on.
