So we know there are different data structures around which are a solution or a invention made for different problems in the world. Be it scanning web pages, traversing back and forth the directories or a musical playlist or getting 10 closest pizza shops near me.. Half of the problem is solved by the choice of the tools we use. Say we have to cut a tree we would need a chainsaw not a knife right?? Similarly if we want to store unique elements and discard duplicates we would need Set. We want to preserve insertion order we would need ArrayList. When we need constant time insertion deletion we would use Linked List which is the data structure we will be looking at today.

Linked List - a list where every item is linked with each other. Simple enough?? No? Okay let's expand our understanding.. Linked List is a linear data structure, similar to Array or ArrayList. Yes there are non linear data structures as well like Tree, Graph.. 

For a short understanding linear data structure the elements are accessed sequentially something like the below visual representation

whereas for a non linear data structure the elements are connected to possibly more than one node and the access cannot be always sequentially. Something like this...

Coming back to Linked List, even though we say Array or ArrayList and Linked List are linear data structures there is still a difference between how they work which is why we said it is similar and not same to Array or ArrayList. 

The main difference lies in the memory management of these structures. Array/ArrayList stores data in a contiguous fashion whereas Linked List will do it in a non contiguous way. What do we mean by contiguous and non-contiguous. Let' say these arrays or ArrayList are placed in continuous block of memories where the memory blocks allocated for Linked List are not in continuous fashion.

For illustration purpose, we can see that the memory are allocated (green background) in a sequential / contiguous manner for Array/ArrayList. However when it comes to Linked List the allocation would be probably something similar to this.

We can see that the memory allocation is not continuous / non-contiguous in the linked list. So how does the each element know which element is next? So every node or every element has a pointer which points to the memory address of the next element. So every node in a linked list will have a data element and pointer element which will point to the next node in the list. 

So doesn't matter where the node is present in the memory. It would have its reference stored in the next pointer of its neighboring node.. Something in similar fashion

So in short every node / element in a linked list would have something similar structure

As you can there are two structures available, one with only next pointer and one with a previous pointer as well along with the next pointer. Basically there are two variations for a linked list, Singly Linked List  which has a data element and a next pointer which points to the address of its next node and Doubly Linked List which has a previous pointer along with the data and next pointer where the previous pointer points to the memory address of its previous node.

Along with doubly linked list there is also a concept of Circular Linked List where the last node of the linked list points its next node to an element say in the middle of the linked list there creating a cycle or a loop kind of structure.

So we can move ahead as well and move back as well in a sequential manner. Now what benefits does Linked List provide over say Array or ArrayList?

Array or ArrayList stores data in a sequential manner and there is a default size of a data structure which is kept irrespective of whether we have data or not. Linked List behaves differently here as there is no default size kept, whenever a node is created a memory for the same is allocated and kept.

Another difference is when we have to find an element in an array it goes for O(1) complexity. Why? Since ArrayList data is stored in contiguous manner. Say we have to find a element at the 16th index and we know the starting point of the memory address so we can just do the addition to the first memory address and we will have the value. So it will be faster in case of ArrayList.

In case of Linked List, since the memory allocation is non contiguous we will have to iterate through each element to find it. So it kind of boils down to O(n) complexity. For Insertion / Deletion Linked List has a plus say we have a node and we have to delete the neighboring element. Because we just have to change the reference with respect to the next pointer. All we would need to do is.

Node nodeToBeDeleted = currentNode.next; 

currentNode.next = nodeToBeDeleted.next; 

We just mapped the next of the node to be deleted to the next of the current node and voila.. The linked list would not have a nodeToBeDeleted. What would happen to the nodeToBeDeleted? It would stay in the memory as an orphan node which will be picked for garbage collection post it meets the necessary conditions. 

Now if only have a head node and we need to do some change at the middle or last we would have to traverse the whole list which would kind of make the complexity as O(n). In short, whenever we require traversal, the complexity would go to O(n). So here is the summarization of the complexities involved with respect to Linked List.

Applications of linked list from real scenarios include Music Playlist for traversing to and fro the files, Undo functionality in application, In Web Browsers for maintaining the list of user visited pages to go back and forth, Routing Table for efficient path finding, In Real Time Gaming where we need to do the addition / deletion of bullets or items or say remember the player moves.

Well, that's about the linked list data structure. There are lot of questions based on this data structure which are quite popular be it interviews or coding competitions. For that we need to understand this data structure properly. We would be covering on the questions / problems on linked list. Until next time, think about the non linear data structures...

Powered by Froala Editor