Browse Articles

Doubly Linked List in Data Structures

Amit Kumar Ghosh  52 min read
21 Sep 2023
Beginner
303 Views

Doubly Linked List in Data Structure: An Overview

If you are studying computer science, data structure, and algorithms then it is essential for you to learn about doubly linked lists. A doubly linked list is a type of data structure that stores a sequence of elements. It consists of elements arranged in a linear fashion such that each element contains references or pointers to the next element in the list as well as the previous one. The advantages associated with this particular data structure are tremendous ranging from efficient traversal capabilities to freeing up memory while manipulating complex datasets. This article will explore further into doubly linked lists why they're important and how they work so let's dive right in!

What is a doubly linked list in data structure?

A doubly linked list is a popular data structure used in computer science to store data in a specific order. Unlike a singly linked list, a doubly linked list allows each node to be connected to both its previous and next nodes, creating a chain that can be traversed in both directions. Doubly linked lists are excellent for text editors and other jobs that need efficient mid-list node operations as well as bidirectional traversal. They have become essential to computer science because of their adaptability and effectiveness.

A doubly linked list is a type of linked list in which each node consists of 3 components:

  • *prev - address of the previous node
  • data - data item
  • *next - address of next node

Representation of Doubly Linked List

A doubly linked list is a data structure that consists of nodes, where each node contains a value and two pointers: one to the previous node and one to the next node. This allows for traversal in both directions.

Here is an algorithm for a doubly linked list:

  1. Define a Node class with three properties: value, prev (pointer to the previous node), and next (arrow to the next node).
  2. Create a DoublyLinkedList class with two properties: head (pointer to the first node) and tail (pointer to the last node).
  3. Implement the following methods in the DoublyLinkedList class:
    • isEmpty(): Check if the list is empty by verifying if the head is null.
    • prepend(value): Add a node with the given value at the beginning of the list.
    • append(value): Add a node with the given value at the end of the list.
    • insertAfter(value, targetValue): Insert a node with the given value after the first occurrence of the target value in the list.
    • remove(value): Remove the first occurrence of a node with the given value from the list.
    • removeFirst(): Remove the first node from the list.
    • removeLast(): Remove the last node from the list.
    • printList(): Traverse the list from the head to the tail and print the values of all the nodes.
  4. In each method, consider different cases such as adding or removing nodes at the beginning, end, or middle of the list, and update the pointers accordingly

Doubly Linked List in Data Structures Example


 # Node of a doubly linked list
class Node:
    def __init__(self, next=None, prev=None, data=None):
        # reference to next node in DLL
        self.next = next
        # reference to previous node in DLL
        self.prev = prev
        self.data = data

 // Class for Doubly Linked List
 public class DLL {
     // Head of list
     Node head;
     // Doubly Linked list Node
     class Node {
         int data;
         Node prev;
         Node next;
         // Constructor to create a new node
         // next and prev is by default initialized as null
         Node(int d) { data = d; }
     }
 }

 // Node of a doubly linked list
 class Node {
 public:
     int data;
     // Pointer to next node in DLL
     Node* next;
     // Pointer to previous node in DLL
     Node* prev;
 };

In this doubly linked list program in data structure, we create a Node class for a doubly linked list (DLL) with features for data storage, references to the following and preceding nodes, and more.

Advantages of Doubly Linked List

  1. Efficient insertion and deletion: Unlike arrays, which require shifting of elements to insert or delete an element, doubly linked lists only require changing the pointers of the adjacent nodes. This makes the insertion and deletion operations much more efficient.
  2. Bidirectional traversal: The two pointers in each node allow for bidirectional traversal of the linked list, meaning the developer can traverse the list forward and backward. This is particularly useful in situations where the a need to search for elements or perform operations from both ends of the list.
  3. Flexibility: Because nodes in a doubly linked list have pointers to both the previous and next nodes, they can be easily removed from the list or inserted into the list without affecting the rest of the nodes. This makes doubly linked lists very flexible and adaptable to different situations.
  4. Memory efficiency: Unlike other data structures requiring a fixed amount of memory for each element, doubly linked lists can be allocated and resized dynamically, based on the amount of data being stored. This means that the user can use memory more efficiently and avoid wasting resources.
  5. Implementing other data structures: Doubly linked lists are often used as a building block for implementing other data structures, such as queues, stacks, and associative arrays. By using a doubly linked list as a base, anyone can implement these data structures more efficiently and with greater flexibility.

Disadvantages of Doubly Linked List

  1. Memory usage: Doubly linked lists require more memory than singly-linked lists, as they need to store a pointer to the previous node in addition to the next node.
  2. Insertion and deletion: Although doubly linked lists allow for more efficient insertion and deletion operations than arrays, they are less efficient than singly-linked lists. This is because each insertion or deletion requires updating both the previous and next pointers, which can be time-consuming.
  3. Traversal: Traversing a doubly linked list can also be slower than traversing an array or singly linked list, as it requires following both the previous and next pointers.
  4. Complexity: The use of doubly linked lists can add complexity to the code and increase the risk of bugs, as there are more pointers to manage and more edge cases to consider.
  5. Not suitable for some algorithms: Some algorithms may require random access to elements in a list, which is not efficient with doubly linked lists.
  6. Extra work for maintaining the list: In a doubly linked list, the user needs to handle the cases for both the next and previous node while inserting and deleting the node, it increases the complexity and there is a chance for error

Basic Operations on Doubly Linked List

Insertion Operation:

  • Insertion at the beginning: To add a new node at the beginning of the list, you need to create a new node and update the references accordingly. If the list is empty, the new node will be both the head and tail of the list. Otherwise, you update the next reference of the new node to point to the current head, update the previous reference of the current head to point to the new node, and update the head reference to the new node.
  • Insertion at the end: To add a new node at the end of the list, you create a new node and update the references accordingly. If the list is empty, the new node will be both the head and tail of the list. Otherwise, you update the next reference of the current tail to point to the new node, update the previous reference of the new node to point to the current tail, and update the tail reference to the new node.
  • Insertion at a specific position: To insert a new node at a specific position in the list, you need to traverse the list until you reach the desired position. Once you reach the position, you create a new node and update the references accordingly. You update the next reference of the new node to point to the node currently at that position, update the previous reference of the new node to point to the node before the position, update the next reference of the node before the position to point to the new node and update the previous reference of the node at the position to point to the new node.

Algorithm for insertion operation

  1. Create a new node with the given data.
  2. If the doubly linked list is empty, set the head and tail pointers to point to the new node, and make the new node's prev and next pointers null.
  3. If the doubly linked list is not empty, do the following:
    • Set the new node's next pointer to point to the current head of the list.
    • Set the new node's prev pointer to null.
    • Set the current head's prev pointer to point to the new node.
    • Set the head pointer to point to the new node.
  4. The insertion operation is complete.

Example


 class Node:
     def __init__(self, data):
         self.data = data
         self.prev = None
         self.next = None
 def insertAtBeginning(head, data):
     # Create a new node
     newNode = Node(data)
     newNode.next = head
     # Update the previous pointer of the head node if it exists
     if head is not None:
         head.prev = newNode
     # Update the head pointer
     head = newNode
     return head
 def displayList(head):
     current = head
     while current is not None:
         print(current.data, end=" ")
         current = current.next
     print()
 # Main function
 if __name__ == '__main__':
     head = None # Initially, the list is empty
     # Insert nodes at the beginning of the list
     head = insertAtBeginning(head, 3)
     head = insertAtBeginning(head, 2)
     head = insertAtBeginning(head, 1)
     # Display the list
     print("Doubly Linked List:", end=" ")
     displayList(head)

 class Node {
     int data;
     Node prev;
     Node next;
 }
 class DoublyLinkedList {
     Node head;
     // Function to insert a new node at the beginning of the list
     void insertAtBeginning(int data) {
         // Create a new node
         Node newNode = new Node();
         newNode.data = data;
         newNode.prev = null;
         newNode.next = head;
         // Update the previous pointer of the head node if it exists
         if (head != null)
             head.prev = newNode;
         // Update the head pointer
         head = newNode;
     }
     // Function to display the contents of the doubly linked list
     void displayList() {
         Node current = head;
         while (current != null) {
             System.out.print(current.data + " ");
             current = current.next;
         }
         System.out.println();
     }
     public static void main(String[] args) {
         DoublyLinkedList list = new DoublyLinkedList();
         // Insert nodes at the beginning of the list
         list.insertAtBeginning(3);
         list.insertAtBeginning(2);
         list.insertAtBeginning(1);
         // Display the list
         System.out.print("Doubly Linked List: ");
         list.displayList();
     }
 }

 #include <iostream>
 // Node structure for doubly linked list
 struct Node {
     int data;
     Node* prev;
     Node* next;
 };
 // Function to insert a new node at the beginning of the list
 void insertAtBeginning(Node** head, int data) {
     // Create a new node
     Node* newNode = new Node();
     newNode->data = data;
     newNode->prev = nullptr;
     newNode->next = *head;
     // Update the previous pointer of the head node if it exists
     if (*head != nullptr)
         (*head)->prev = newNode;
     // Update the head pointer
     *head = newNode;
 }
 // Function to display the contents of the doubly linked list
 void displayList(Node* head) {
     Node* current = head;
     while (current != nullptr) {
         std::cout << current->data << " ";
         current = current->next;
     }
     std::cout << std::endl;
 }
 int main() {
     Node* head = nullptr; // Initially, the list is empty
     // Insert nodes at the beginning of the list
     insertAtBeginning(&head, 3);
     insertAtBeginning(&head, 2);
     insertAtBeginning(&head, 1);
     // Display the list
     std::cout << "Doubly Linked List: ";
     displayList(head);
     return 0;
 }

This example defines a doubly linked list and offers functions to show the list and insert nodes at the start of the list. It displays the doubly linked list: "1 2 3" after showing how nodes with the values 1, 2, and 3 are inserted at the beginning.

Output

Doubly Linked List: 1 2 3

Deletion Operation

  • Deletion from the beginning: To remove the first node from the list, you update the head reference to point to the next node, update the previous reference of the new head to null, and optionally free the memory occupied by the old head node.
  • Deletion from the end: To remove the last node from the list, you update the tail reference to point to the previous node, update the next reference of the new tail to null, and optionally free the memory occupied by the old tail node.
  • Deletion from a specific position: To remove a node from a specific position in the list, you need to traverse the list until you reach the desired position. Once you reach the position, you update the next reference of the node before the position to point to the node after the position, update the previous reference of the node after the position to point to the node before the position, and optionally free the memory occupied by the node at the position.

Algorithm for deletion operation

  • If the list is empty, exit the algorithm since there is nothing to delete.
  • If the node to be deleted is the first node (head) of the list:
    • Set the head pointer to point to the next node (head = head.next).
    • If the new head exists, set its previous pointer to null (head.prev = null).
    • If the new head is null, set the tail pointer to null as well (tail = null).
    • Exit the algorithm.
  • If the node to be deleted is the last node (tail) of the list:
    • Set the tail pointer to point to the previous node (tail = tail.prev).
    • If the new tail exists, set its next pointer to null (tail.next = null).
    • Exit the algorithm.
  • If the node to be deleted is somewhere in the middle of the list:
    • Set the previous node's next pointer to the next node (previousNode.next = currentNode.next).
    • Set the next node's previous pointer to the previous node (nextNode.prev = currentNode.prev).
    • Exit the algorithm

Example


 class Node:
     def __init__(self, data):
         self.data = data
         self.prev = None
         self.next = None
 def insertAtBeginning(head, data):
     newNode = Node(data)
     if head is None:
         head = newNode
     else:
         newNode.next = head
         head.prev = newNode
         head = newNode
     return head
 def insertAtEnd(head, data):
     newNode = Node(data)
     if head is None:
         head = newNode
     else:
         current = head
         while current.next is not None:
             current = current.next
         current.next = newNode
         newNode.prev = current
     return head
 def displayList(head):
     if head is None:
         print("The list is empty.")
     else:
         current = head
         while current is not None:
             print(current.data, end=" ")
             current = current.next
         print()
 def deleteNode(head, data):
     if head is None:
         print("The list is empty.")
         return head
     current = head
     prevNode = None
     while current is not None:
         if current.data == data:
             if prevNode is None:
                 head = current.next
                 if head is not None:
                     head.prev = None
             else:
                 prevNode.next = current.next
                 if current.next is not None:
                     current.next.prev = prevNode
             del current
             print("Node with data", data, "deleted successfully.")
             return head
         prevNode = current
         current = current.next
     print("Node with data", data, "not found in the list.")
     return head
 if __name__ == '__main__':
     head = None
     # Insert nodes at the beginning
     head = insertAtBeginning(head, 5)
     head = insertAtBeginning(head, 3)
     head = insertAtBeginning(head, 1)
     # Insert nodes at the end
     head = insertAtEnd(head, 7)
     head = insertAtEnd(head, 9)
     print("Initial list: ")
     displayList(head)
     # Delete a node
     head = deleteNode(head, 3)
     print("List after deletion: ")
     displayList(head)

 class Node {
     int data;
     Node prev;
     Node next;
     Node(int data) {
         this.data = data;
         this.prev = null;
         this.next = null;
     }
 }
 class DoublyLinkedList {
     Node head;
     // Function to insert a node at the beginning of the list
     void insertAtBeginning(int data) {
         Node newNode = new Node(data);
         if (head == null) {
             head = newNode;
         } else {
             newNode.next = head;
             head.prev = newNode;
             head = newNode;
         }
     }
     // Function to insert a node at the end of the list
     void insertAtEnd(int data) {
         Node newNode = new Node(data);
         if (head == null) {
             head = newNode;
         } else {
             Node current = head;
             while (current.next != null) {
                 current = current.next;
             }
             current.next = newNode;
             newNode.prev = current;
         }
     }
     // Function to display the doubly linked list
     void displayList() {
         if (head == null) {
             System.out.println("The list is empty.");
         } else {
             Node current = head;
             while (current != null) {
                 System.out.print(current.data + " ");
                 current = current.next;
             }
             System.out.println();
         }
     }
     // Function to delete a node from the list
     void deleteNode(int data) {
         if (head == null) {
             System.out.println("The list is empty.");
             return;
         }
         Node current = head;
         Node prevNode = null;
         while (current != null) {
             if (current.data == data) {
                 if (prevNode == null) {
                     head = current.next;
                     if (head != null) {
                         head.prev = null;
                     }
                 } else {
                     prevNode.next = current.next;
                     if (current.next != null) {
                         current.next.prev = prevNode;
                     }
                 }
                 System.out.println("Node with data " + data + " deleted successfully.");
                 return;
             }
             prevNode = current;
             current = current.next;
         }
         System.out.println("Node with data " + data + " not found in the list.");
     }
 }
 public class Main {
     public static void main(String[] args) {
         DoublyLinkedList list = new DoublyLinkedList();
         // Insert nodes at the beginning
         list.insertAtBeginning(5);
         list.insertAtBeginning(3);
         list.insertAtBeginning(1);
         // Insert nodes at the end
         list.insertAtEnd(7);
         list.insertAtEnd(9);
         System.out.print("Initial list: ");
         list.displayList();
         // Delete a node
         list.deleteNode(3);
         System.out.print("List after deletion: ");
         list.displayList();
     }
 }

 #include <iostream>
 using namespace std;
 struct Node {
     int data;
     Node* prev;
     Node* next;
 };
 // Function to create a new node
 Node* createNode(int data) {
     Node* newNode = new Node();
     newNode->data = data;
     newNode->prev = NULL;
     newNode->next = NULL;
     return newNode;
 }
 // Function to insert a node at the beginning of the list
 void insertAtBeginning(Node** head, int data) {
     Node* newNode = createNode(data);
     if (*head == NULL) {
         *head = newNode;
     } else {
         newNode->next = *head;
         (*head)->prev = newNode;
         *head = newNode;
     }
 }
 // Function to insert a node at the end of the list
 void insertAtEnd(Node** head, int data) {
     Node* newNode = createNode(data);
     if (*head == NULL) {
         *head = newNode;
     } else {
         Node* current = *head;
         while (current->next != NULL) {
             current = current->next;
         }
         current->next = newNode;
         newNode->prev = current;
     }
 }
 // Function to display the doubly linked list
 void displayList(Node* head) {
     if (head == NULL) {
         cout << "The list is empty." << endl;
     } else {
         Node* current = head;
         while (current != NULL) {
             cout << current->data << " ";
             current = current->next;
         }
         cout << endl;
     }
 }
 // Function to delete a node from the list
 void deleteNode(Node** head, int data) {
     if (*head == NULL) {
         cout << "The list is empty." << endl;
         return;
     }
     Node* current = *head;
     Node* prevNode = NULL;
     while (current != NULL) {
         if (current->data == data) {
             if (prevNode == NULL) {
                 *head = current->next;
                 if (*head != NULL) {
                     (*head)->prev = NULL;
                 }
             } else {
                 prevNode->next = current->next;
                 if (current->next != NULL) {
                     current->next->prev = prevNode;
                 }
             }
             delete current;
             cout << "Node with data " << data << " deleted successfully." << endl;
             return;
         }
         prevNode = current;
         current = current->next;
     }
     cout << "Node with data " << data << " not found in the list." << endl;
 }
 int main() {
     Node* head = NULL;
     // Insert nodes at the beginning
     insertAtBeginning(&head, 5);
     insertAtBeginning(&head, 3);
     insertAtBeginning(&head, 1);
     // Insert nodes at the end
     insertAtEnd(&head, 7);
     insertAtEnd(&head, 9);
     cout << "Initial list: ";
     displayList(head);
     // Delete a node
     deleteNode(&head, 3);
     cout << "List after deletion: ";
     displayList(head);
     return 0;
 }

This example defines a doubly linked list and offers functions to show the list, insert nodes at the start or end, and delete a particular node based on its value. It shows how to add nodes, display the initial list, delete a node with the value 3, and then display the revised list.

Output

 Initial list: 1 3 5 7 9
Node with data 3 deleted successfully.
List after deletion: 1 5 7 9

Traversal Operation:

You can traverse the doubly linked list in both directions. Starting from the head, you can visit each node by following the next references until you reach the end of the list (tail). Similarly, starting from the tail, you can visit each node by following the previous references until you reach the beginning of the list (head)

Algorithm for traversal operation

  1. Start at the head of the doubly linked list.
  2. If the head is null, the list is empty. Exit the algorithm.
  3. Initialize a pointer variable current and set it to the head of the list.
  4. While the current is not null, do the following steps:
    • Process the data of the current node.
    • Move the current pointer to the next node.
  5. Repeat step 4 until the current becomes null.
  6. Exit the algorithm

Example


 class Node:
     def __init__(self, data):
         self.data = data
         self.prev = None
         self.next = None
 # Function to insert a node at the beginning of the doubly linked list
 def insertAtBeginning(head, data):
     # Create a new node
     newNode = Node(data)
     newNode.prev = None
     # If the list is empty, set the new node as the head
     if head is None:
         newNode.next = None
         head = newNode
         return head
     # Make the new node the new head
     newNode.next = head
     head.prev = newNode
     head = newNode
     return head
 # Function to traverse the doubly linked list and print the elements
 def traverseList(head):
     print("Doubly linked list elements: ", end='')
     # Traverse the list
     while head is not None:
         print(head.data, end=' ')
         head = head.next
     print()
 # Initialize an empty doubly linked list
 head = None
 # Insert elements into the list
 head = insertAtBeginning(head, 5)
 head = insertAtBeginning(head, 10)
 head = insertAtBeginning(head, 15)
 head = insertAtBeginning(head, 20)
 # Traverse and print the doubly linked list
 traverseList(head)

 class Node {
     int data;
     Node prev;
     Node next;
 }
 public class DoublyLinkedList {
     // Function to insert a node at the beginning of the doubly linked list
     static void insertAtBeginning(Node[] head, int data) {
         // Create a new node
         Node newNode = new Node();
         newNode.data = data;
         newNode.prev = null;
         // If the list is empty, set the new node as the head
         if (head[0] == null) {
             newNode.next = null;
             head[0] = newNode;
             return;
         }
         // Make the new node the new head
         newNode.next = head[0];
         head[0].prev = newNode;
         head[0] = newNode;
     }
     // Function to traverse the doubly linked list and print the elements
     static void traverseList(Node head) {
         System.out.print("Doubly linked list elements: ");
         // Traverse the list
         while (head != null) {
             System.out.print(head.data + " ");
             head = head.next;
         }
         System.out.println();
     }
     public static void main(String[] args) {
         // Initialize an empty doubly linked list
         Node[] head = new Node[1];
         // Insert elements into the list
         insertAtBeginning(head, 5);
         insertAtBeginning(head, 10);
         insertAtBeginning(head, 15);
         insertAtBeginning(head, 20);
         // Traverse and print the doubly linked list
         traverseList(head[0]);
     }
 }

 #include <iostream>
 // Doubly linked list node
 struct Node {
     int data;
     Node* prev;
     Node* next;
 };
 // Function to insert a node at the beginning of the doubly linked list
 void insertAtBeginning(Node** head, int data) {
     // Create a new node
     Node* newNode = new Node;
     newNode->data = data;
     newNode->prev = nullptr;
     // If the list is empty, set the new node as the head
     if (*head == nullptr) {
         newNode->next = nullptr;
         *head = newNode;
         return;
     }
     // Make the new node the new head
     newNode->next = *head;
     (*head)->prev = newNode;
     *head = newNode;
 }
 // Function to traverse the doubly linked list and print the elements
 void traverseList(Node* head) {
     std::cout << "Doubly linked list elements: ";
     // Traverse the list
     while (head != nullptr) {
         std::cout << head->data << " ";
         head = head->next;
     }
     std::cout << std::endl;
 }
 int main() {
     // Initialize an empty doubly linked list
     Node* head = nullptr;
     // Insert elements into the list
     insertAtBeginning(&head, 5);
     insertAtBeginning(&head, 10);
     insertAtBeginning(&head, 15);
     insertAtBeginning(&head, 20);
     // Traverse and print the doubly linked list
     traverseList(head);
     return 0;
 }

This example defines a function to insert nodes at the list's beginning as well as a doubly linked list. The doubly linked list is traversed and printed after being initialized as an empty list, with the members of the list being output as "20 15 10 5."

Output

Doubly linked list elements: 20 15 10 5

Applications of Doubly Linked List

  • Browser History: A browser history is a list of web pages that a user has visited. A doubly linked list is an ideal data structure for implementing a browser history because it allows users to navigate forward and backward through the pages they have visited.
  • Music and Video Player: Doubly linked lists can be used to implement a music or video player's playlist. The links between the nodes allow users to navigate through the playlist in both the forward and backward directions.
  • Text Editor: Text editors use doubly linked lists to implement the undo and redo features. Each node in the list represents the state of the document, and the links between the nodes allow users to navigate through the document's history.
  • Cache: A cache is a temporary storage area used to speed up data access. Doubly linked lists can be used to implement a cache, with the most recently accessed data at the head of the list and the least recently accessed data at the tail.
  • Operating System: Doubly linked lists are used in many operating systems for various purposes, such as managing processes, allocating memory, and handling input/output operations.
  • File System: File systems use doubly linked lists to implement file directories. Each node in the list represents a file or a directory, and the links between the nodes allow users to navigate through the file system's directory structure

FAQs

1. What is a doubly linked list in data structure?

Each node in a doubly linked list holds a reference to both the node before it and the node after it, enabling bidirectional traversal.

2. Why do we use doubly linked lists in data structure?

Doubly linked lists are used because they can be efficiently traversed both forward and backward, making them appropriate for use in undo capabilities in text editors and other applications.

3. What is the difference between a doubly vs singly linked list?

The main distinction is that each node in a singly linked list only has a reference to the node after it, whereas each node in a doubly linked list includes references to both the nodes before and after it, allowing for bidirectional traversal.

4. Where is the doubly linked list used?

When bidirectional traversal is required, such as when implementing undo/redo functionality, browser history, or specific data structures like deques, doubly linked lists are utilized.

5. What are the advantages of a doubly linked list?

Bidirectional traversal, effective deletion and insertion at both ends and the capacity to create complex data structures and apps necessitating backward traversal are all advantages.

Summary

Ultimately, understanding the basic principles of a doubly linked list in the data structure is essential for any programmer or computer scientist. It not only allows us to store and manipulate complex information but also gives us control over how that is organized and accessed by a computer. Doubly linked lists are effective for applications and data structures that are efficient and save time and resources. You can build complex buildings if you can master them. To succeed more, investigate, explore, and use doubly linked lists!

Share
About Author
Amit Kumar Ghosh (SDE and Mentor)

A passionate professional with over 6 years of experience in development and training. He is passionate about learning new technologies and sharing his experience with professionals. He is an expert in C/C++, Java, Python and DSA.
Accept cookies & close this