Linked List Types – Explanation
In earlier posts of linked lists, we have discussed about Linked list and some of its basic operations like Insertion and Deletion.
Insertion – Insertion to Linked List – Explanation, Types and Implementation
Deletion – Deletion from Linked List – Explanation, Types and Implementation
Insertion, Deletion and Searching are widely used operation. Searching in a linked list is linear. Given the head, finding an element will be sequential and of course that takes O(n). Unfortunately, there is no better way.
Insertion and Deletion takes O(1) time if done at the head, but they do take O(n) time(when the operation is to be performed at the other end of the linked list). This is where modifications are required to achieve O(1) universally. Keeping various modifications into consideration,
A Linked list is mainly classified as:
- Singly Linked List
- Circular Linked List
- Doubly Linked List
1. Singly Linked list
With a head pointing to the first node and a NULL in the reference part of last node singly linked list consists of two parts, Data part and Next part. Next refers to a pointer that points to the next node. Data is the information holder for the node.
For inserting an element at the end of the list, time taken would be O(n) and same for deletion.
Read more – Introduction to Linked List – Explanation and Implementation
Note:- Singly Linked list is the most basic form of Linked list. In all the posts of linked list, explanations are provided assuming Singly linked list unless specified.
Drawbacks:
- Say want to insert a node to the last, therefore time complexity will be O(n) because we have to traverse from starting to the end node, the same will be the case with Deletion. Even to insertion at specified position may take O(n).
- Traversing will be always in the forward direction (backward not possible), as a result, algorithms such as MRU(Most Recently Used) can’t be implemented successfully.
2. Circular Linked List
It is almost like Singly linked list, but in a circular linked list, last node will point to the first node, whereas in a singly linked list the value is NULL. Therefore, the whole list can be traversed again and again as required. However, detecting the end of the singly linked list is pretty straight forward that is list becomes finally NULL, but in a circular linked during traversing each node is compared with the head pointer and if it is equal it means that the entire list is traversed.
Backward traversing is still not possible because we do not have any way to reach to the previous node but related operation can be performed.
However, even Circular linked list does not guarantee always O(1) time for Insertion/Deletion.
Deleting the element 20 will take O(n).
3. Doubly Linked list
Unlike other linked lists it consists of three parts, two parts as contained by Singly linked list i.e. Data and Next. In addition to these every node in a doubly linked list also holds a pointer to it’s previous node i.e. Prev part of the node. Backward traversing is possible any time as required. This one is able to achieve O(1) running time in almost all cases. Thus, it’s widely used.
- Prev – Points to previous node
- Data – Containing data
- Next – Pointing next node
See the below doubly LL, each node is referring to the next node as well as the previous node.
Few points:
- There is another linked list – Multilevel linked list, where node can point to multiple node. Doubly linked list is a special case of a Multilevel linked list.
- Circular doubly linked list is a combination of circular linked list and doubly linked list.
- Interestingly, A Linux kernel has all the three types of linked list implementations.
Knowledge is most useful when liberated and shared. Share this to motivate us to keep writing such online tutorials for free and do comment if anything is missing or wrong or you need any kind of help.
Keep Learning… Happy Learning.. 🙂