Everything You Need to Know About Doubly Linked List
Have you ever wondered how applications manage data that needs to be traversed both forwards and backwards with equal ease? A doubly linked list is a data structure that makes this possible. Each element, or node, in a doubly linked list, contains a reference not only to the next node but also to the previous one, allowing for bidirectional navigation. Let's understand more!
A doubly linked list is a type of linked list that has two pointers, or references, in addition to the data. One of the pointers points to the node that comes before it in the sequence, and the other points to the node that comes after it. It makes it possible to traverse a doubly linked both forward and backward. Take a look at the below image for reference:
Components Of Doubly Linked List
A doubly linked list has 3 key components, as listed below:
1. Node: A node in a doubly linked list holds 3 key information, i.e., the data, address to the previous node & address to the next node.
2. Head: A head of a doubly linked list is the first node of the linked list.
3. Tail: A tail is the last element of a linked list.
Take a look at the below image for reference:
Now that we have made ourselves familiar with the basics of a doubly linked list let’s take a look at its implementation.
Best-suited Data Structures and Algorithms courses for you
Learn Data Structures and Algorithms with these high-rated online courses
Implementing Doubly Linked List
A simple node in Python for a doubly linked list can be represented as below:
class Node: def __init__(self, data): self.data = data self.prev = None self.next = None
Here, the Node class objects have three properties: data and address of the previous node (i.e., prev) and the address to the next pointer.
Now let’s implement the Doubly linked list class:
class DoublyLinkedList: def __init__(self): self.head = None self.tail = None
Now, let’s implement a couple of methods to interact with the above doubly linked list. The first method is to insert data to the doubly linked list called insert_end():
def insert_end(self, data): new_node = Node(data) if self.head is None: self.head = self.tail = new_node else: new_node.prev = self.tail self.tail.next = new_node self.tail = new_node
The second method would be to check the next element of the sequence called display_forward():
def display_forward(self): current = self.head while current: print(current.data, end=" ") current = current.next
Finally, the last method would be to view the previous node of the current node called display_backward():
def display_backward(self): current = self.tail while current: print(current.data, end=" ") current = current.prev
Now, let’s test our linked list by inserting some elements to it and iterating through it backwards and forward.
class Node: def __init__(self, data): # Initialize a node with data self.data = data # Pointer to the previous node self.prev = None # Pointer to the next node self.next = None
# Doubly linked list classclass DoublyLinkedList: def __init__(self): # Initialize an empty doubly linked # list with head and tail as None # Pointer to the head of the list self.head = None # Pointer to the tail of the list self.tail = None
def insert_end(self, data): # Create a new node and insert # it at the end of the list new_node = Node(data) if self.head is None: # If the list is empty, # set the new node as # both head and tail self.head = self.tail = new_node else: # If the list is not empty, # insert the new node after the tail # Set the new node's prev # pointer to the current tail new_node.prev = self.tail # Set the current tail's # next pointer to the new node self.tail.next = new_node # Update the tail to be the new node self.tail = new_node # Display the elements of the # list in forward direction def display_forward(self): # Start from the head # of the list current = self.head while current: # Print the data of the current node print(current.data, end=" ") # Move to the next node current = current.next print()
# Display the elements of the # list in backward direction def display_backward(self): # Start from the tail of the list current = self.tail while current: # Print the data of the current node print(current.data, end=" ") # Move to the previous node current = current.prev print()
# Example usageif __name__ == "__main__": dll = DoublyLinkedList()
# Insert elements into the doubly linked list dll.insert_end('A') dll.insert_end('B') dll.insert_end('C')
# Display the doubly linked list in # forward and backward directions print("Doubly linked list forward:") dll.display_forward()
print("Doubly linked list backward:") dll.display_backward()
Output
Doubly linked list forward:
A B C
Doubly linked list backward:
C B A
Operations on Doubly Linked List
We can perform the below operations on a doubly linked list:
- Insert Node in Doubly Linked list
- Detele Node from a Doubly linked list
Let’s explore both of these operations.
Insert Node in a Doubly Linked List
Now let’s look into the operations that we can perform on a double linked list that are:
- Insert Node at the start
- Insert Node at the End
- Insert Node in-between existing Nodes
Let’s take a look at each one of them in detail:
Insert Node at Start of Doubly Linked List
To insert a node at the start of a doubly linked list, we can follow the below algorithm:
Algorithm:
Step 1: Create a new node with the given data.
Step 2: If the doubly linked list is empty (head is None):
- Set the new node as both the head and the tail.
- Set head = tail = new_node
Step 3: Else (doubly linked list is not empty):
- Set the new node's next pointer to the current head.
- Set the current head's previous pointer to the new node.
Update the head pointer to the new node: head = new_node
Step 4: Done.
This approach ensures the pointers are modified in accordance with the new node. Take a look at the below image for reference:
Insert Node at End of Doubly Linked List
To insert a node at the start of a doubly linked list, we can follow the below algorithm:
Algorithm:
Step 1: Create a new node with the given data.
Step 2: If the doubly linked list is empty (head is None):
- Set the new node as both the head and the tail.
- Set head = tail = new_node
Step 3: Else (doubly linked list is not empty):
- Set the new node's previous pointer to the current tail.
- Set the current tail's next pointer to the new node.
- Update the tail pointer to the new node: tail = new_node
Step 4: Done.
Take a look at the below image for reference:
Insert Node In-Between Nodes of Doubly Linked List
To insert a new node to an existing doubly linked list in between the node, we make use of the following algorithm:
Algorithm:
Step 1: Create a new node with the given data.
Step 2: If the doubly linked list is empty (HEAD is None), return as it cannot perform an insertion between nodes.
Step 3: Traverse the list to find the node after which you want to insert the new node.
Step 4: Create temporary pointers (say, prev_node and next_node) to store the nodes before and after the insertion point.
Step 5: Set prev_node to the node before the insertion point and next_node to the node after the insertion point.
Step 6: Update the pointers:
- Set the new node's previous pointer to prev_node.
- Set the new node's next pointer to next_node.
- Set prev_node's next pointer to the new node.
- Set next_node's previous pointer to the new node.
Step 7: Done.
Take a look at the below image for reference:
Deletion of Node in Doubly Linked List
Similar to insertion, we can delete an existing node from a doubly linked list from the below positions:
- Delete Node at the start
- Delete Node at the End
- Delete Node in-between existing Nodes
Let’s take a look at each one of them in detail.
Delete Node at the Start of Doubly Linked List
Deleting a node from the start of a doubly linked list can be achieved using the below Algorithm:
Algorithm:
Step 1: If the doubly linked list is empty (head is None), return as there's nothing to delete.
Step 2: If there is only one node in the list:
- Set head and tail to None to empty the list.
- Free the memory occupied by the node to be deleted.
Step 3: If there are more than one nodes in the list:
- Set the head's next node as the new head: head = head.next
- Set the new head's previous pointer to None since it's the new starting node.
- Free the memory occupied by the node to be deleted.
Step 4: Done.
Take a look at the below image for reference:
Delete Node at the End of Doubly Linked List
To delete a node at the end of a doubly linked list using the below algorithm.
Algorithm:
Step 1: If the doubly linked list is empty (HEAD is None), return as there's nothing to delete.
Step 2: If there is only one node in the list:
- Set head and tail to None to empty the list.
- Free the memory occupied by the node to be deleted.
Step 3: If there are more than one nodes in the list:
- Traverse to the last node of the doubly linked list.
- Set the tail's previous node as the new tail: tail = tail.prev
- Set the new tail's next pointer to None since it's the new ending node.
- Free the memory occupied by the node to be deleted.
Step 4: Done.
Take a look at the below image for reference:
Delete Node Between Nodes of Doubly Linked List
To delete a node in between existing nodes of a doubly linked list using the algorithm below.
Algorithm:
Step 1: If the doubly linked list is empty (head is None), return as there's nothing to delete.
Step 2: Traverse to the node to be deleted.
Step 3: Update the pointers of the previous and next nodes of the node to be deleted:
- Set the previous node's next pointer to the next node.
- Set the next node's previous pointer to the previous node.
Step 4: Free the memory occupied by the node to be deleted.
Step 5: Done.
Take a look at the below image for reference:
Read Later
Program to Insert Nodes in a Doubly Linked List
We can insert a node at the start, end and in-between doubly linked list. Please go through the code and code explanation for specific programming languages below for the same.
Python Program to Insert Node in a Doubly Linked List
# Node classclass Node: def __init__(self, data): self.data = data self.prev = None self.next = None
# doubly linked list classclass DoublyLinkedList: def __init__(self): self.head = None # method to insert node at the # start of a doubly linked list def insert_start(self, data): new_node = Node(data) # If list is empty, # new node becomes the head if not self.head: self.head = new_node else: new_node.next = self.head self.head.prev = new_node self.head = new_node # method to insert Node # at the end of doubly linked list def insert_end(self, data): new_node = Node(data) # If list is empty, # new node becomes the head if not self.head: self.head = new_node else: temp = self.head # Find the last node while temp.next: temp = temp.next # Set new node's prev to the last node new_node.prev = temp # Set last node's next to new_node temp.next = new_node # method to insert nodes # in-between existing nodes # in a doubly linked list def insert_between(self, data, position_data): new_node = Node(data) # If list is empty, # new node becomes the head if not self.head: self.head = new_node else: temp = self.head # Find the node after which to insert while temp and temp.data != position_data: temp = temp.next # If position_data not found if not temp: print("Node with data", position_data, "not found") return # Set new node's prev to position_node new_node.prev = temp # Set new node's next to the next of position_node new_node.next = temp.next # Set position_node's next's prev to new_node if temp.next: temp.next.prev = new_node # Set position_node's next to new_node temp.next = new_node # method to display the # doubly linked list def display(self): if not self.head: print("Empty list") else: temp = self.head while temp: print(temp.data, end=" <-> ") temp = temp.next print()
# doubly linked list objectdoubly_list = DoublyLinkedList()
# Insert at the startdoubly_list.insert_start(30)doubly_list.display()
# Insert at the enddoubly_list.insert_end(40)doubly_list.display()
# Insert in-between existing nodesdoubly_list.insert_between(35, 30)doubly_list.display()
Output
30 <->
30 <-> 40 <->
30 <-> 35 <-> 40 <->
Java Program to Insert Node in a Doubly Linked List
class Node { int data; Node prev, next;
// Constructor to initialize a node public Node(int data) { this.data = data; this.prev = this.next = null; }}
class DoublyLinkedList { Node head;
// Method to insert a node at the start of a doubly linked list void insert_start(int data) { // Create a new node Node newNode = new Node(data);
// If the list is empty, the new node becomes the head if (head == null) { head = newNode; } else { // Update pointers to insert at the start newNode.next = head; head.prev = newNode; head = newNode; } }
// Method to insert a node at the end of a doubly linked list void insert_end(int data) { // Create a new node Node newNode = new Node(data);
// If the list is empty, the new node becomes the head if (head == null) { head = newNode; } else { Node temp = head;
// Traverse to the last node while (temp.next != null) { temp = temp.next; }
// Update pointers to insert at the end newNode.prev = temp; temp.next = newNode; } }
// Method to insert a node in-between existing nodes in a doubly linked list void insert_between(int data, int positionData) { // Create a new node Node newNode = new Node(data);
// If the list is empty, the new node becomes the head if (head == null) { head = newNode; } else { Node temp = head;
// Find the node after which to insert while (temp != null && temp.data != positionData) { temp = temp.next; }
// If positionData not found if (temp == null) { System.out.println("Node with data " + positionData + " not found"); return; }
// Update pointers to insert in-between newNode.prev = temp; newNode.next = temp.next;
// Update pointers of adjacent nodes if (temp.next != null) { temp.next.prev = newNode; } temp.next = newNode; } }
// Method to display the doubly linked list void display() { if (head == null) { System.out.println("Empty list"); } else { Node temp = head; while (temp != null) { System.out.print(temp.data + " <-> "); temp = temp.next; } System.out.println(); } }}
public class Main { public static void main(String[] args) { DoublyLinkedList doublyList = new DoublyLinkedList();
// Insert at the start doublyList.insert_start(30); doublyList.display();
// Insert at the end doublyList.insert_end(40); doublyList.display();
// Insert in-between existing nodes doublyList.insert_between(35, 30); doublyList.display(); }}
Output
30 <->
30 <-> 40 <->
30 <-> 35 <-> 40 <->
C++ Program to Insert Node in a Doubly Linked List
#include <iostream>
// Node classclass Node {public: int data; Node* prev; Node* next;
// Constructor to initialize a node Node(int data) : data(data), prev(nullptr), next(nullptr) {}};
// Doubly linked list classclass DoublyLinkedList {public: Node* head;
// Constructor to initialize the list DoublyLinkedList() : head(nullptr) {}
// Method to insert a node at the start of the list void insert_start(int data) { // Create a new node Node* newNode = new Node(data);
// If the list is empty, the new node becomes the head if (head == nullptr) { head = newNode; } else { // Update pointers to insert at the start newNode->next = head; head->prev = newNode; head = newNode; } }
// Method to insert a node at the end of the list void insert_end(int data) { // Create a new node Node* newNode = new Node(data);
// If the list is empty, the new node becomes the head if (head == nullptr) { head = newNode; } else { Node* temp = head;
// Traverse to the last node while (temp->next != nullptr) { temp = temp->next; }
// Update pointers to insert at the end newNode->prev = temp; temp->next = newNode; } }
// Method to insert a node in-between existing nodes in the list void insert_between(int data, int positionData) { // Create a new node Node* newNode = new Node(data);
// If the list is empty, the new node becomes the head if (head == nullptr) { head = newNode; } else { Node* temp = head;
// Find the node after which to insert while (temp != nullptr && temp->data != positionData) { temp = temp->next; }
// If positionData not found if (temp == nullptr) { std::cout << "Node with data " << positionData << " not found" << std::endl; return; }
// Update pointers to insert in-between newNode->prev = temp; newNode->next = temp->next;
// Update pointers of adjacent nodes if (temp->next != nullptr) { temp->next->prev = newNode; } temp->next = newNode; } }
// Method to display the doubly linked list void display() { if (head == nullptr) { std::cout << "Empty list" << std::endl; } else { Node* temp = head; while (temp != nullptr) { std::cout << temp->data << " <-> "; temp = temp->next; } std::cout << std::endl; } }};
int main() { // Doubly linked list object DoublyLinkedList doublyList;
// Insert at the start doublyList.insert_start(30); doublyList.display();
// Insert at the end doublyList.insert_end(40); doublyList.display();
// Insert in-between existing nodes doublyList.insert_between(35, 30); doublyList.display();
return 0;}
Output
30 <->
30 <-> 40 <->
30 <-> 35 <-> 40 <->
Program to Delete Node in a Doubly Linked List
Find below the Python, Java and C++ programs to delete a node from a doubly linked list.
Python program to Delete Nodes in a Doubly Linked List
# Node classclass Node: def __init__(self, data): self.data = data self.prev = None self.next = None
class DoublyLinkedList: def __init__(self): self.head = None
# Method to insert node at the start of the doubly linked list def insert_start(self, data): new_node = Node(data) if not self.head: # If the list is empty, new node becomes the head self.head = new_node else: # Update pointers to insert at the start new_node.next = self.head self.head.prev = new_node self.head = new_node
# Method to delete node at the start of the doubly linked list def delete_start(self): if not self.head: # Empty list, deletion not possible print("Empty list, deletion not possible") return
# If there is only one node elif self.head.next is None: self.head = None else: # Rearrange pointers to delete the first node self.head = self.head.next self.head.prev = None
# Method to delete node at the end of the doubly linked list def delete_end(self): if not self.head: # Empty list, deletion not possible print("Empty list, deletion not possible") return
# If there is only one node elif self.head.next is None: self.head = None else: # Traverse to the last node and rearrange pointers to delete the last node temp = self.head while temp.next is not None: temp = temp.next temp.prev.next = None
# Method to delete node in-between existing nodes of the doubly linked list def delete_between(self, position_data): if not self.head: # Empty list, deletion not possible print("Empty list, deletion not possible") return
# If there is only one node elif self.head.next is None: if self.head.data == position_data: self.head = None return else: print("Node with data", position_data, "not found") return else: # Traverse to the node to be deleted and rearrange pointers to remove it temp = self.head while temp.data != position_data: temp = temp.next if temp is None: print("Node with data", position_data, "not found") return
if temp.prev is not None: temp.prev.next = temp.next else: self.head = temp.next
if temp.next is not None: temp.next.prev = temp.prev
# Method to display the doubly linked list def display(self): if not self.head: print("Empty list") else: temp = self.head while temp is not None: print(temp.data, end=" <-> ") temp = temp.next print()
# Doubly linked list objectdoubly_list = DoublyLinkedList()
# Inserting nodesdoubly_list.insert_start(40)doubly_list.insert_start(30)doubly_list.insert_start(20)doubly_list.insert_start(10)doubly_list.display()
# Deleting nodes at startdoubly_list.delete_start()doubly_list.display()
# Deleting nodes at enddoubly_list.delete_end()doubly_list.display()
# Deleting nodes in betweendoubly_list.delete_between(30)doubly_list.display()
Output
10 <-> 20 <-> 30 <-> 40 <->
20 <-> 30 <-> 40 <->
20 <-> 30 <->
20 <->
Java program to Delete Nodes in a Doubly Linked List
// Node classclass Node { int data; Node prev, next;
public Node(int data) { this.data = data; this.prev = this.next = null; }}
// doubly linked list classclass DoublyLinkedList { Node head;
// Method to insert node at the // start of the doubly linked list void insert_start(int data) { Node new_node = new Node(data); if (head == null) { head = new_node; } else { new_node.next = head; head.prev = new_node; head = new_node; } }
// Method to delete node at the // start of the doubly linked list void delete_start() { if (head == null) { System.out.println("Empty list, deletion not possible"); return; } else if (head.next == null) { head = null; } else { head = head.next; head.prev = null; } }
// Method to delete node at // the end of the doubly linked list void delete_end() { if (head == null) { System.out.println("Empty list, deletion not possible"); return; } else if (head.next == null) { head = null; } else { Node temp = head; while (temp.next != null) { temp = temp.next; } temp.prev.next = null; } }
// Method to delete node in-between // existing nodes of the doubly linked list void delete_between(int position_data) { if (head == null) { System.out.println("Empty list, deletion not possible"); return; } else if (head.next == null) { if (head.data == position_data) { head = null; } else { System.out.println("Node with data " + position_data + " not found"); } } else { Node temp = head; while (temp.data != position_data) { temp = temp.next; if (temp == null) { System.out.println("Node with data " + position_data + " not found"); return; } }
if (temp.prev != null) { temp.prev.next = temp.next; } else { head = temp.next; }
if (temp.next != null) { temp.next.prev = temp.prev; } } }
// Method to display the doubly linked list void display() { if (head == null) { System.out.println("Empty list"); } else { Node temp = head; while (temp != null) { System.out.print(temp.data + " <-> "); temp = temp.next; } System.out.println(); } }}
public class Main { public static void main(String[] args) { DoublyLinkedList doublyList = new DoublyLinkedList();
// Inserting nodes doublyList.insert_start(40); doublyList.insert_start(30); doublyList.insert_start(20); doublyList.insert_start(10); doublyList.display();
// Deleting nodes at start doublyList.delete_start(); doublyList.display();
// Deleting nodes at end doublyList.delete_end(); doublyList.display();
// Deleting nodes in between doublyList.delete_between(30); doublyList.display(); }}
Output
10 <-> 20 <-> 30 <-> 40 <->
20 <-> 30 <-> 40 <->
20 <-> 30 <->
20 <->
C++ program to Delete Nodes in a Doubly Linked List
#include <iostream>
// Node classclass Node {public: int data; Node* prev; Node* next;
Node(int data) { this->data = data; this->prev = nullptr; this->next = nullptr; }};
// Doubly circular linked list classclass DoublyCircularLinkedList {private: Node* head;
public: DoublyCircularLinkedList() { head = nullptr; }
// Function to insert node at the start // of the doubly circular linked list void insert_start(int data) { Node* new_node = new Node(data); if (!head) { head = new_node; new_node->next = head; new_node->prev = head; } else { new_node->next = head; new_node->prev = head->prev; head->prev->next = new_node; head->prev = new_node; head = new_node; } }
// Method to delete node at the start // of the doubly circular linked list void delete_start() { if (!head) { // Empty list, deletion not possible std::cout << "Empty list, deletion not possible" << std::endl; return; } else if (head->next == head) { // If there is only one node delete head; head = nullptr; } else { Node* temp = head; head->next->prev = head->prev; head->prev->next = head->next; head = head->next; delete temp; } }
// Method to delete node at the end // of the doubly circular linked list void delete_end() { if (!head) { // Empty list, deletion not possible std::cout << "Empty list, deletion not possible" << std::endl; return; } else if (head->next == head) { // If there is only one node delete head; head = nullptr; } else { Node* temp = head->prev; temp->prev->next = head; head->prev = temp->prev; delete temp; } }
// Method to delete node in-between existing // nodes of the doubly circular linked list void delete_between(int position_data) { if (!head) { // Empty list, deletion not possible std::cout << "Empty list, deletion not possible" << std::endl; return; } else if (head->next == head) { // If there is only one node if (head->data == position_data) { delete head; head = nullptr; } else { std::cout << "Node with data " << position_data << " not found" << std::endl; } } else { Node* temp = head; while (temp->data != position_data) { temp = temp->next; if (temp == head) { std::cout << "Node with data " << position_data << " not found" << std::endl; return; } } temp->prev->next = temp->next; temp->next->prev = temp->prev; delete temp; } }
// Method to display the doubly circular linked list void display() { if (!head) { std::cout << "Empty list" << std::endl; } else { Node* temp = head; do { std::cout << temp->data << " <-> "; temp = temp->next; } while (temp != head); std::cout << std::endl; } }};
int main() { DoublyCircularLinkedList doubly_circular_list;
// Inserting nodes doubly_circular_list.insert_start(40); doubly_circular_list.insert_start(30); doubly_circular_list.insert_start(20); doubly_circular_list.insert_start(10); doubly_circular_list.display();
// Deleting node at start doubly_circular_list.delete_start(); doubly_circular_list.display();
// Deleting node at end doubly_circular_list.delete_end(); doubly_circular_list.display();
// Deleting node in-between nodes doubly_circular_list.delete_between(30); doubly_circular_list.display();
return 0;}
Output
10 <-> 20 <-> 30 <-> 40 <->
20 <-> 30 <-> 40 <->
20 <-> 30 <->
20 <->
Use Case of Doubly Linked List
The below consists of a list of applications of doubly linked list:
- Undo Mechanism in Software Application: Applications that implement the undo mechanism frequently use doubly linked lists. Every operation is saved in a node, and reversing an operation is made simple by the backward link.
- File Systems: Doubly linked lists are used in file systems to maintain the list of blocks that make up a file. This allows for efficient backward and forward traversal of the file.
- Text Editors: Text editors often use doubly linked lists to represent the lines of text. Each line is a node, and the links facilitate easy insertion and deletion of lines.
- DBMS: Doubly linked lists are used in database systems to implement indexes and data structures for efficient data retrieval and manipulation.
- Browser History: A doubly linked list can be utilised to implement browser history. Every page that has been seen is considered a node, and navigating through the history is made simple by the back and forward links.
Conclusion
In this article, we have managed to cover the following concepts associated with doubly linked lists:
- Overview of Doubly Linked List
- Inserting Nodes to a Doubly Linked List
- Deleting Nodes from a Doubly Linked List
- Implementation of Insertion/Deletion of Nodes from Doubly Linked List
- Applications of Doubly Linked List
Contributed By: Raju
This is a collection of insightful articles from domain experts in the fields of Cloud Computing, DevOps, AWS, Data Science, Machine Learning, AI, and Natural Language Processing. The range of topics caters to upski... Read Full Bio
Top Picks & New Arrivals
