Introduction
A Doubly Linked List is a type of linked list data structure where each node has two pointers. One pointer points to the previous node and the other pointer points to the next node. This means that each node in a doubly linked list contains three parts: the data, a pointer to the previous node, and a pointer to the next node.
The first node in the doubly linked list is called the head while the last node is called the tail. Since the nodes in a doubly linked list have both a previous and a next pointer, it allows for traversal of the list in both the directions. So, the double linked list is easier for insertion and deletion operations.
Insertion into a doubly linked list is similar to that of a singly linked list, except that you have to update both the previous and the next pointers of the neighbor nodes. Deletion from a doubly linked list is also similar to that of a singly linked list. The only difference is that you have to update the previous as well as the next pointers of the neighboring nodes.
Traversing a doubly linked list
Traversing a doubly linked list involves visiting each node in the list sequentially, starting from the head node and ending at the tail node or vice versa. To traverse a doubly linked list, we can use a pointer to start at the head node and then follow the next pointers until we reach the end of the list. Similarly, we can start at the tail node and then follow the previous pointers until we reach the head of the list. Let us now understand it using example code.
Here we have two functions i.e. printListForward and printListBackward. In printListForward, we are traversing the Linked list from head to tail using the next pointer. While in printListBackward, we are traversing the linked list from tail to head using the prev pointer. This is the beauty of the doubly liked list that we can traverse on both sides.
Insert a node in Doubly Linked List
Inserting a node in a Doubly Linked List involves creating a new node with the given data and linking it appropriately to the existing nodes. There are three main scenarios for inserting a node in a Doubly Linked List: at the beginning, at the end, and at a specific position. Let us discuss them one by one.
Insert a node at the beginning of a Doubly Linked List
Inserting a node at the beginning of a Doubly Linked List involves the following steps:
- Create a new node with the given data.
- Set the next pointer of the new node to the current head of the list.
- Set the previous pointer of the current head of the list to the new node.
- Set the head of the list to the new node.
Example function for inserting a node at the beginning of a Doubly Linked List:
Insert a node at the end of a Doubly Linked List
Inserting a node at the end of a Doubly Linked List involves the following steps:
- Create a new node with the given data.
- Set the next pointer of the new node to NULL.
- Traverse the list to find the last node.
- Set the next pointer of the last node to the new node.
- Set the previous pointer of the new node to the last node.
Example function for inserting a node at the end of a Doubly Linked List:
Insert a node at a specific position of a Doubly Linked List
nserting a node at a specific position in a Doubly Linked List involves the following steps:
- Create a new node with the given data.
- Traverse the list to find the node before the position where the new node will be inserted.
- Set the next pointer of the new node to the node at the position where the new node will be inserted.
- Set the previous pointer of the new node to the node before the position where the new node will be inserted.
- Set the next pointer of the node before the position where the new node will be inserted to the new node.
- Set the previous pointer of the node before the position where the new node will be inserted to the node that was previously before it.
Delete a node from Doubly Linked List
Deletion from the Doubly linked list means deleting a node from the Linked list and then updating the pointers of neighboring nodes. The deletion can be done in three ways. Lets us understand them one by one.
Deletion of a from the beginning
To delete the first node of a Doubly Linked List, we need to follow these steps:
- Store the address of the second node in a temporary pointer.
- Set the next pointer of the first node to NULL.
- Set the head pointer to the second node.
- Free the memory of the first node.
Deletion of a node from the end
To delete the last node of a Doubly Linked List, we need to follow these steps:
- Traverse the list to reach the last node.
- Store the address of the second last node in a temporary pointer.
- Set the next pointer of the second last node to NULL.
- Free the memory of the last node.
Deletion of a node from a specific position
To delete a node from a specific position in a Doubly Linked List, we need to follow these steps:
- Traverse the list to find the node at the position to be deleted.
- Store the address of the node before the position in a temporary pointer.
- Set the next pointer of the node before the position to the node after the position.
- Set the previous pointer of the node after the position to the node before the position.
- Free the memory of the node at the position.
Advantages of Doubly Linked List
- It allows traversal in both directions, i.e., forward and backward.
- It provides O(1) time complexity for inserting and deleting nodes, both at the beginning and end of the list.
- It is efficient in searching for nodes, as we can start the search from both ends of the list.
- It provides flexibility in implementing some data structures like a deque (double-ended queue) and a LRU (Least Recently Used) cache.
Disadvantage of Doubly Linked List
- It requires extra memory to store the previous pointer, which results in higher memory usage than singly linked lists.
- Insertion and deletion operations can be slower than arrays, due to the overhead of pointer manipulation.
- The complexity of the code increases as compared to singly linked lists, which makes it harder to debug and maintain.
- Random access is not possible, which is a disadvantage over arrays.
Comparision of Singly & Doubly Linked List
Singly linked lists and doubly linked lists are both used to implement dynamic data structures in programming. Here are some of the key differences between the two:
| Property | Singly Linked List | Doubly Linked List |
|---|---|---|
| Memory usage | Less memory usage as each node only needs to store a single pointer | More memory usage as each node needs to store two pointers |
| Traversal | Only allows for forward traversal | Allows for both forward and backward traversal |
| Insertion at beginning | O(1) time complexity | O(1) time complexity |
| Insertion at end | O(n) time complexity | O(1) time complexity |
| Insertion at specific position | O(n) time complexity to find the position, O(1) time complexity to insert | O(n) time complexity to find the position, O(1) time complexity to insert |
| Deletion at beginning | O(1) time complexity | O(1) time complexity |
| Deletion at end | O(n) time complexity | O(1) time complexity |
| Deletion at specific position | O(n) time complexity to find the position, O(1) time complexity to delete | O(n) time complexity to find the position, O(1) time complexity to delete |
| Implementation complexity | Simpler implementation | More complex implementation due to the additional pointers |
| Usage | Useful when forward traversal is sufficient, and memory usage is a concern | Useful when backward traversal is required or when both forward and backward traversal is required, and memory usage is not a major concern |