A doubly linked list is a Linked List with the nodes linked bidirectionally. So, each node contains the link to its previous and next node along with the data. Doubly Linked List is useful for Navigation systems where both front and back navigation is required.
1. Representation of Doubly Linked List
// Linked list node representation struct Node { int element; Node* prev; Node* next; }; // Head of the list Node* head;
Properties
- Head: The starting point of the linked list
- Node: A node consists of the data element and the pointer to the Previous and Next node
- Element: The actual data (provided as 10, 20, and 30)
- Prev: Pointer to the previous node
- Next: Pointer to the next node
Pros
- Provides the ability to traverse the list backward since it has the link to previous node.
- Also supports faster deletion with the Node pointer. Whereas, the Singly Linked List requires the previous Node pointer to be available for deletion.
- Faster insertion before the given Node pointer. Whereas, the Singly list requires the previous Node pointer to be available.
- Reversing the doubly linked list is simple and straightforward.
Cons
- However, a doubly linked list requires additional memory to store the Prev pointers. (This is addressed in the XOR linked list by keeping the single pointer for both “Prev” and “Next”. The bitwise XOR value of the Prev and the Next pointer is calculated and stored in the node. So, this helps to perform both forward and reverse navigations.)
- Also, it has the operations overhead to keep the Prev pointer up to date.
Applications
- Image Viewer to show previous and next images.
- Browser’s forward and backward navigation.
- Implement Undo and Redo functionalities.
- Construct the MRU (Most Recently Used) and LRU (Least Recently Used) cache.
- In addition, it is useful to Implement other data structures like Stack, Queue, Hash, and Binary Tree.
2. Implementation of Doubly Linked List in C++
/** * C++ example to demonstrate the Doubly Linked List */ #include <iostream> using namespace std; // Linked list node representation struct Node { int element; Node* prev; Node* next; }; /** * Doubly Linked list implementation */ class DoublyList { // Head of the list Node* head; public: // Constructor DoublyList() : head(NULL) {} // Insert an element in front of the list // Returns the new node inserted Node* insert_front(int element); // Insert an element at the end of the list // Returns the new node inserted Node* insert_back(int element); // Insert an element before the given node // Returns the new node inserted Node* insert_before(Node* next, int element); // Insert an element after the given node // Returns the new node inserted Node* insert_after(Node* prev, int element); // Delete the front element // Returns the next node if available, NULL otherwise. Node* delete_front(); // Delete the element from end of the list // Returns the previous node, NULL otherwise. Node* delete_back(); // Delete the given node // Returns the next node if available, NULL otherwise. Node* delete_node(Node* target); // Search and delete the given element void remove(int element); // Search an element from the list // Returns the matching node if found, NULL otherwise. Node* search(int element); // Print the elements void print(const std::string& msg); }; Node* DoublyList::insert_front(int element) { // Step 1. Create the new node Node* new_node = new Node(); new_node->element = element; // Step 2. Link the new node before the head node new_node->prev = NULL; new_node->next = head; if (head != NULL) { head->prev = new_node; } // Step 3. Change the head to point the new node head = new_node; return new_node; } Node* DoublyList::insert_before(Node* next, int element) { // Step 1. Create the new node Node *new_node = new Node(); new_node->element = element; // Step 2. Link the new node before the given node new_node->prev = next->prev; new_node->next = next; next->prev = new_node; if (new_node->prev != NULL) { new_node->prev->next = new_node; } return new_node; } Node* DoublyList::insert_after(Node* prev, int element) { // Step 1. Create the new node Node *new_node = new Node(); new_node->element = element; // Step 2. Link the new node after the given node new_node->prev = prev; new_node->next = prev->next; prev->next = new_node; if (new_node->next != NULL) { new_node->next->prev = new_node; } return new_node; } Node* DoublyList::insert_back(int element) { // Step 1. Check if the list is empty. If true, perform insert_front() and return. if (head == NULL) { return insert_front(element); } // Step 2. Traverse the list and find the last node Node *p = head; while (p->next != NULL) { p = p->next; } // Step 3. Perform insert_after() with the last node found return insert_after(p, element); } Node* DoublyList::delete_front() { // Step 1. Store the reference to head as target and // move the head to next node if available, NULL otherwise. Node* target = head; head = head->next; // Step 2. Disconnect the target node from the list if (head != NULL) { head->prev = NULL; } // Step 3. Delete the target node delete target; return head; } Node* DoublyList::delete_node(Node* target) { // Step 1. Check if the target node is head. If true, perform // delete_front() and return. if (target->prev == NULL) { return delete_front(); } // Step 2. Disconnect the target node by directly linking its // previous and next node. Node *next = target->next; target->prev->next = next; if (next != NULL) { next->prev = target->prev; } // Step 3. Delete the target node delete target; return next; } Node* DoublyList::delete_back() { // Step 1. Check if the list is empty and return if true. if (head == NULL) { return NULL; } // Step 2. Traverse the list and find the last node as target Node *target = head; while (target->next != NULL) { target = target->next; } Node* prev = target->prev; // Step 3. Delete the target node using delete_node() delete_node(target); return prev; } void DoublyList::remove(int element) { // Step 1. Search the element in linked list from start to end. for (Node* p = head ; p != NULL ; p = p->next) { if (p->element == element) { // Step 2. If found, perform delete_node() and return. delete_node(p); return; } } return; } Node* DoublyList::search(int element) { // Iterate the linked list from start to end for (Node* node = head ; node != NULL ; node = node->next) { if (node->element == element) { return node; // Found element } } return NULL; // Not found } // Print the linked list void DoublyList::print(const std::string& msg) { cout << msg << endl; cout << "HEAD --> "; // Iterate the linked list from start to end for (Node* node = head ; node != NULL ; node = node->next) { cout << node->element; cout << ((node->next == NULL)? " --> " : " <==> "); } cout << "NULL" << endl << endl; } int main() { // Create a linked list DoublyList list; list.print("initial list"); // Insert elements Node* node_10 = list.insert_front(10); list.print("insert_front(10)"); Node* node_40 = list.insert_back(40); list.print("insert_back(40)"); list.insert_after(node_10, 20); list.print("insert_after(node_10, 20)"); list.insert_before(node_40, 30); list.print("insert_before(node_40, 30)"); // Search an element Node *node_30 = list.search(30); cout << "search(30) matches node " << node_30->element << endl << endl; // Delete elements list.delete_front(); list.print("delete_front()"); list.delete_node(node_30); list.print("delete_node(node_30)"); list.delete_back(); list.print("delete_back()"); list.remove(20); list.print("remove(20)"); }
Output
initial list
HEAD --> NULL
insert_front(10)
HEAD --> 10 --> NULL
insert_back(40)
HEAD --> 10 <==> 40 --> NULL
insert_after(node_10, 20)
HEAD --> 10 <==> 20 <==> 40 --> NULL
insert_before(node_40, 30)
HEAD --> 10 <==> 20 <==> 30 <==> 40 --> NULL
search(30) matches node 30
delete_front()
HEAD --> 20 <==> 30 <==> 40 --> NULL
delete_node(node_30)
HEAD --> 20 <==> 40 --> NULL
delete_back()
HEAD --> 20 --> NULL
remove(20)
HEAD --> NULL
3. Insertions on a Doubly Linked List
3.1. Insert Front
Insert the new node at the beginning of the list and update the Head pointer.
Algorithm
- Create the new node
- Link the new node before the head node
- Change the head to point to the new node
Example
3.2. Insert Back
Insert the new node on the backside.
Algorithm
- Create the new node
- Traverse the list and find the last node
- Perform insert_after() with the last node found
Example
3.3. Insert After
Insert the new node after the given Node and update the Previous and Next links
Algorithm
- Create the new node
- Link the new node after the given node
Example
3.4. Insert Before
Insert the new node before the given node and update the Previous and Next links.
Algorithm
- Create the new node
- Link the new node before the given node
Example
4. Deletions on a Doubly Linked List
4.1. Delete Front
Delete the front Node and move the Head to the next node.
Algorithm
- Store the reference to head as target and move the head to the next node if available, NULL otherwise.
- Disconnect the target node from the list
Example
4.2. Delete a Node
Delete the Node with the given pointer.
Algorithm
- Check if the target node is the head. If true, perform delete_front() and return.
- Disconnect the target node by directly linking its previous and next nodes.
- Finally, delete the target node
Example
4.3. Delete Back
Delete a Node from the backside.
Algorithm
- Check if the list is empty and return if true.
- Traverse the list and find the last node as the target
- Delete the target node using delete_node()
Example
5. References
- std::list – C++ standard library for the doubly linked list.