Doubly Linked List Algorithm in Data Structures with Examples

Doubly Linked Lists in Data Structures: An Overview

We saw that in a Singly Linked List, we could traverse only in one direction from head to tail. We can't travel in reverse i.e. tail to head as each node contains the address of the next node and it doesn't have any record of its previous nodes. To overcome this limitation, we have a Doubly Linked List with us. In this DSA tutorial, we will see the doubly linked list data structure in detail i.e. its features, working, implementation, etc.

To further enhance your understanding and application of linked list concepts, consider enrolling in the Best Dsa Course, to gain comprehensive insights into effective data structure utilization for improved problem-solving and time management.

What is a Doubly Linked List in Data Structures?

A doubly linked list is an enhancement of a singly linked list in which each node consists of 3 components:

1. a pointer *prev: address of the previous node
2. data: data item
3. a pointer *next: address of next node

Representation of a Doubly Linked List in Data Structures

The prev pointer of the first or the head node of the doubly linked list points toNULLto mark the start of the list. The next pointer of the last or the tail node points toNULLto mark the end of the list. It is also known as a two-way linked list as there are two pointers.

Before moving forward, make sure that you are thorough with the concept of pointers. If not refer to the Pointers in C++ tutorial and come back.

How to declare/create a Doubly-Linked List in Data Structures?

Syntax to Declare a Doubly Linked List in Different Languages

class Node:
    def __init__(self, data):
        self.data = data
        self.prev = None
        self.next = None
    

class Node {
   Node previous;  
   int value;      
   Node next;      }
    

struct node {
    int data;
    struct node *next;
    struct node *prev;
}
    

Algorithm for the Creation of a Doubly Linked List

Step 1: Define a class or structure (if working with C/C++) Node with three properties: 
    i. data
    ii. prev (pointer to the previous node)
    iii. next (pointer to the next node).
Step 2: Initially, initialize all the nodes you want to create with NULL.
Step 3: Allocate memory by assigning values to the nodes.
Step 4: Now, all nodes need to be connected to form a linked list. For this,
    i. Assign NULL to the prev pointer of the first node.
    ii. Point the prev pointers of all the other nodes except the last one to the previous node in the series. 
    iii. Point the next pointers of all the nodes except the last one to the upcoming node in the series.
    iv. Assign NULL to the next pointer of the last node.  

Example of Creating a Doubly Linked List in Data Structures

class Node:
    def __init__(self, val):
        self.data = val
        self.prev = None
        self.next = None

# Initialize nodes
head = None
one = Node(1)
two = Node(2)
three = Node(3)

# Connect nodes
one.next = two
one.prev = None

two.next = three
two.prev = one

three.next = None
three.prev = two

# Save the address of the first node in head
head = one

# Print the linked list
current = head
while current:
    print(current.data, end=" ")
    current = current.next
print()
 

class Node {
    int data;
    Node prev;
    Node next;

    Node(int val) {
        data = val;
        prev = null;
        next = null;
    }
}

class Main {
    public static void main(String[] args) {
        // Initialize nodes
        Node head = null;
        Node one, two, three;

        // Allocate memory
        one = new Node(1);
        two = new Node(2);
        three = new Node(3);

        // Connect nodes
        one.next = two;
        one.prev = null;

        two.next = three;
        two.prev = one;

        three.next = null;
        three.prev = two;

        // Save the address of the first node in the head
        head = one;

        // Print the linked list
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }
}

#include <iostream>

// Node structure
struct Node {
    int data;
    Node* prev;
    Node* next;

    Node(int val) : data(val), prev(nullptr), next(nullptr) {}
};

int main() {
    // Initialize nodes
    Node* head = nullptr;
    Node* one = nullptr;
    Node* two = nullptr;
    Node* three = nullptr;

    // Allocate memory
    one = new Node(1);
    two = new Node(2);
    three = new Node(3);

    // Connect nodes
    one->next = two;
    one->prev = nullptr;

    two->next = three;
    two->prev = one;

    three->next = nullptr;
    three->prev = two;

    // Save the address of the first node in the head
    head = one;

    // Print the linked list
    Node* current = head;
    while (current != nullptr) {
        std::cout << current->data << " ";
        current = current->next;
    }
    std::cout << std::endl;

    // Clean up memory
    delete one;
    delete two;
    delete three;

    return 0;
}
 

In the above code,

• For node one, the pointer next stores the address of two, and prev stores NULL.
• For node two, the pointer next stores the address of three, and prev stores the address of one.
• For node three, next stores NULL, and prev stores the address of two.
• Here one is the head node and so its prev pointer points to NULL and three is a tail node so its next pointer points to NULL.

Output

1 2 3 

Read More - Data Structure Interview Questions and Answers

Memory Representation of a Doubly Linked List in Data Structures

A Doubly Linked List is represented using the linear Arrays in memory where each memory address stores three components:

1. Data Value
2. The memory address of the next element.
3. The memory Address of the previous element.

• In the above image, -1 represents NULL.
• Here 1060, 1061, 1062, etc represent the addresses in the memory, and we traverse the Doubly Linked List until we find -1 in the Next of the Node. This memory representation shows that the Values need not be stored contiguously.
• You can see that the element A has Prev = -1 i.e. NULL, therefore it is the first Node in the Doubly Linked List.
• A’s Next points to memory address 1062, where B is stored hence, B is to the next of A.
• Similarly, B’s Next has a memory address of 1069 where C is stored.
• Similarly, D has its Next as -1, meaning it's the last Node of this Doubly Linked List.
• So it forms the Doubly linked List like -1 ← A ⇆ B ⇆ C ⇆ D → -1.

Standard Operations on Doubly Linked Lists in Data Structures

1. Insertion

Generalized Algorithm for Insertion in a Doubly Linked List

Step 1: Create a new node with the given data.
Step 2: If the doubly linked list is empty:
     i. Set the head and tail pointers point to the new node.
     ii. make the new node's prev and next pointers point to NULL.
Step 3: If the doubly linked list is not empty:
     i. Perform the insertion as per your requirement, either in the beginning, end, or at a given position.

1. Insertion at the beginning: Here, we insert the newly created node before the head node, and the head points to the new node.

   Let us understand this with an illustration. Suppose we want to insert a node with value 6 at the beginning of the given doubly linked list. The following three steps to accomplish this operation:

   1. Create a new node
   • allocate memory for new Node
   • assign the data to the new Node.

   

   2. Set prev and next pointers of the new node
   • point next of new Node to the first node of the doubly linked list
   • point prev to NULL

   

   3. Make new node the head node
   • Point prev of the first node to new Node (now the previous head is the second node)
   • Point head to new Node

   

   The above-given steps are implemented in the below program

   Example of Insertion at the Beginning of a Doubly Linked List

   • Python
   • Java
   • C++

   
   class Node:
       def __init__(self, data):
           self.data = data
           self.prev = None
           self.next = None
   
   class DoublyLinkedList:
       def __init__(self):
           self.head = None
   
       # Function to insert a node at the front of the doubly linked list
       def insert_front(self, data):
           # Allocate memory for newNode
           new_node = Node(data)
   
           # Point next of newNode to the first node of the doubly linked list
           new_node.next = self.head
   
           # Point prev to None
           new_node.prev = None
   
           # Point previous of the first node (now the first node is the second node) to newNode
           if self.head is not None:
               self.head.prev = new_node
   
           # Head points to newNode
           self.head = new_node
   
       # Function to print the elements of the doubly linked list
       def print_list(self):
           current = self.head
           while current:
               print(current.data, end=" ")
               current = current.next
           print()
   
   # Creating a sample doubly linked list with nodes 1, 2, 3
   my_list = DoublyLinkedList()
   my_list.head = Node(1)
   second = Node(2)
   third = Node(3)
   
   my_list.head.next = second
   second.prev = my_list.head
   second.next = third
   third.prev = second
   
   print("Original list:", end=" ")
   my_list.print_list()
   
   # Inserting node with data 6 at the front
   my_list.insert_front(6)
   
   print("List after inserting node with data 6 in the beginning:", end=" ")
   my_list.print_list()
   

   Run Code >>

   
   class Node {
       int data;
       Node prev;
       Node next;
   
       Node(int val) {
           data = val;
           prev = null;
           next = null;
       }
   }
   
   class DoublyLinkedList {
       Node head;
   
       // Function to insert a node at the front of the doubly linked list
       void insertFront(int data) {
           // Allocate memory for newNode
           Node newNode = new Node(data);
   
           // Point next of newNode to the first node of the doubly linked list
           newNode.next = head;
   
           // Point prev to null
           newNode.prev = null;
   
           // Point previous of the first node (now the first node is the second node) to newNode
           if (head != null)
               head.prev = newNode;
   
           // Head points to newNode
           head = newNode;
       }
   
       // Function to print the elements of the doubly linked list
       void printList() {
           Node current = head;
           while (current != null) {
               System.out.print(current.data + " ");
               current = current.next;
           }
           System.out.println();
       }
   
       public static void main(String[] args) {
           // Creating a sample doubly linked list with nodes 1, 2, 3
           DoublyLinkedList myList = new DoublyLinkedList();
           myList.head = new Node(1);
           Node second = new Node(2);
           Node third = new Node(3);
   
           myList.head.next = second;
           second.prev = myList.head;
           second.next = third;
           third.prev = second;
   
           System.out.print("Original list: ");
           myList.printList();
   
           // Inserting node with data 6 at the front
           myList.insertFront(6);
   
           System.out.print("List after inserting node with data 6 in the beginning: ");
           myList.printList();
       }
   }
       

   Run Code >>

   
    #include <iostream>
   
   struct Node {
       int data;
       Node* prev;
       Node* next;
   
       Node(int val) : data(val), prev(nullptr), next(nullptr) {}
   };
   
   // Function to insert a node at the front of the doubly linked list
   void insertFront(Node** head, int data) {
       // Allocate memory for newNode
       Node* newNode = new Node(data);
   
       // Point next of newNode to the first node of the doubly linked list
       newNode->next = (*head);
   
       // Point prev to NULL
       newNode->prev = nullptr;
   
       // Point previous of the first node (now the first node is the second node) to newNode
       if ((*head) != nullptr)
           (*head)->prev = newNode;
   
       // Head points to newNode
       (*head) = newNode;
   }
   
   // Function to print the elements of the doubly linked list
   void printList(Node* head) {
       Node* current = head;
       while (current != nullptr) {
           std::cout << current->data << " ";
           current = current->next;
       }
       std::cout << std::endl;
   }
   
   int main() {
       // Creating a sample doubly linked list with nodes 1, 2, 3
       Node* myList = new Node(1);
       Node* second = new Node(2);
       Node* third = new Node(3);
   
       myList->next = second;
       second->prev = myList;
       second->next = third;
       third->prev = second;
   
       std::cout << "Original list: ";
       printList(myList);
   
       // Inserting node with data 6 at the front
       insertFront(&myList, 6);
   
       std::cout << "List after inserting node with data 6 in the beginning: ";
       printList(myList);
   
       return 0;
   }
    

   Run Code >>

   Output

   Original list: 1 2 3 
   List after inserting node with data 6 in the beginning: 6 1 2 3 
   

2. Insertion at a specific position/in between the nodes: Suppose, we have to insert a node at the position of let's say Node X. The steps to be followed are:
   • Traverse the doubly linked list to the position of Node X.
   • Change the next pointer of the new Node to the next pointer of Node X.
   • Change the prev pointer of the node following the Node X to the new Node.
   • Change the next pointer of Node X to the new Node.
   • Change the prev pointer of the new Node to Node X.

   Let us understand this with an illustration. Suppose we want to insert a node with value 6 after the second node with value 2 in the given doubly linked list. The following three steps to accomplish this operation:

   1. Create a new node
   • allocate memory for new Node.
   • assign the data to new Node.

   

   2. Set the next pointer of the new node and the previous node.
   • assign the value of next from the previous node to the next of new Node.
   • assign the address of the new Node to the next of the previous node.

   

   3. Set the prev pointer of new node and the next node.
   • assign the value of prev of next node to the prev of new Node.
   • assign the address of the new Node to the prev of next node

   

   The final doubly linked list after this insertion is:

   

   Example of Insertion in Between or at a Given Position in a Doubly Linked List

   • Python
   • Java
   • C++

   
   class Node:
       def __init__(self, val):
           self.data = val
           self.prev = None
           self.next = None
   
   class DoublyLinkedList:
       def __init__(self):
           self.head = None
   
       # Function to insert a node after a specific node
       def insert_after(self, prev_node, data):
           # Check if the previous node is None
           if prev_node is None:
               print("Previous node cannot be None")
               return
   
           # Allocate memory for newNode
           new_node = Node(data)
   
           # Set next of newNode to next of prev node
           new_node.next = prev_node.next
   
           # Set next of prev node to newNode
           prev_node.next = new_node
   
           # Set prev of newNode to the previous node
           new_node.prev = prev_node
   
           # Set prev of newNode's next to newNode
           if new_node.next is not None:
               new_node.next.prev = new_node
   
       # Function to print the elements of the doubly linked list
       def print_list(self):
           current = self.head
           while current is not None:
               print(current.data, end=" ")
               current = current.next
           print()
   
   # Creating a sample doubly linked list
   my_list = DoublyLinkedList()
   
   my_list.head = Node(1)
   second = Node(2)
   third = Node(3)
   
   my_list.head.next = second
   second.prev = my_list.head
   second.next = third
   third.prev = second
   
   print("Original list:", end=" ")
   my_list.print_list()
   
   # Inserting a node with data 6 after the second node (with data 2)
   my_list.insert_after(second, 6)
   
   print("List after inserting node with data 6 after node with data 2:", end=" ")
   my_list.print_list()    

   Run Code >>

   
   class Node {
       int data;
       Node prev;
       Node next;
   
       public Node(int val) {
           data = val;
           prev = null;
           next = null;
       }
   }
   
   class DoublyLinkedList {
       Node head;
   
       public DoublyLinkedList() {
           head = null;
       }
   
       // Function to insert a node after a specific node
       void insertAfter(Node prevNode, int data) {
           // Check if the previous node is null
           if (prevNode == null) {
               System.out.println("Previous node cannot be null");
               return;
           }
   
           // Allocate memory for newNode
           Node newNode = new Node(data);
   
           // Set next of newNode to next of prev node
           newNode.next = prevNode.next;
   
           // Set next of prev node to newNode
           prevNode.next = newNode;
   
           // Set prev of newNode to the previous node
           newNode.prev = prevNode;
   
           // Set prev of newNode's next to newNode
           if (newNode.next != null) {
               newNode.next.prev = newNode;
           }
       }
   
       // Function to print the elements of the doubly linked list
       void printList() {
           Node current = head;
           while (current != null) {
               System.out.print(current.data + " ");
               current = current.next;
           }
           System.out.println();
       }
   
       public static void main(String[] args) {
           // Creating a sample doubly linked list
           DoublyLinkedList myList = new DoublyLinkedList();
   
           myList.head = new Node(1);
           Node second = new Node(2);
           Node third = new Node(3);
   
           myList.head.next = second;
           second.prev = myList.head;
           second.next = third;
           third.prev = second;
   
           System.out.print("Original list: ");
           myList.printList();
   
           // Inserting a node with data 6 after the second node (with data 2)
           myList.insertAfter(second, 6);
   
           System.out.print("List after inserting node with data 6 after node with data 2: ");
           myList.printList();
       }
   }
       

   Run Code >>

   
   #include <iostream>
   
   struct Node {
       int data;
       Node* prev;
       Node* next;
   
       Node(int val) : data(val), prev(nullptr), next(nullptr) {}
   };
   
   class DoublyLinkedList {
   public:
       Node* head;
   
       DoublyLinkedList() : head(nullptr) {}
   
       // Function to insert a node after a specific node
       void insertAfter(Node* prev_node, int data) {
           // Check if the previous node is NULL
           if (prev_node == nullptr) {
               std::cout << "Previous node cannot be NULL" << std::endl;
               return;
           }
   
           // Allocate memory for newNode
           Node* newNode = new Node(data);
   
           // Set next of newNode to next of prev node
           newNode->next = prev_node->next;
   
           // Set next of prev node to newNode
           prev_node->next = newNode;
   
           // Set prev of newNode to the previous node
           newNode->prev = prev_node;
   
           // Set prev of newNode's next to newNode
           if (newNode->next != nullptr)
               newNode->next->prev = newNode;
       }
   
       // Function to print the elements of the doubly linked list
       void printList() {
           Node* current = head;
           while (current != nullptr) {
               std::cout << current->data << " ";
               current = current->next;
           }
           std::cout << std::endl;
       }
   };
   
   int main() {
       // Creating a sample doubly linked list
       DoublyLinkedList myList;
   
       myList.head = new Node(1);
       Node* second = new Node(2);
       Node* third = new Node(3);
   
       myList.head->next = second;
       second->prev = myList.head;
       second->next = third;
       third->prev = second;
   
       std::cout << "Original list: "; 
       myList.printList();
   
       // Inserting a node with data 6 after the second node (with data 2)
       myList.insertAfter(second, 6);
   
       std::cout << "List after inserting node with data 6 after node with data 2: ";
       myList.printList();
   
       return 0;
   }
       

   Run Code >>

   Output

   Original list: 1 2 3 
   List after inserting node with data 6 after node with data 2: 1 2 6 3   

3. Insertion at the end: Here, we insert the newly created node at the end of the list or after the tail node, and the tail points to the new node.

   Let us understand this with an illustration. Suppose we want to insert a node with value 6 at the end of the given doubly linked list. The following two steps to accomplish this operation:

   1. Create a new node

   

   2. Set prev and next pointers of the new node and the previous node If the linked list is empty, make the new Node as the head node. Otherwise, traverse to the end of the doubly linked list.

      

   The final doubly linked list after this insertion is:

   

   Example of Insertion at the End of a Doubly Linked List

   • Python
   • Java
   • C++

   
   class Node:
       def __init__(self, val):
           self.data = val
           self.prev = None
           self.next = None
   
   class DoublyLinkedList:
       def __init__(self):
           self.head = None
   
       # Function to insert a new node at the end of the list
       def insert_end(self, data):
           # Allocate memory for node
           new_node = Node(data)
   
           # Assign NULL to next of new_node
           new_node.next = None
   
           # Store the head node temporarily (for later use)
           temp = self.head
   
           # If the linked list is empty, make the new_node as the head node
           if self.head is None:
               new_node.prev = None
               self.head = new_node
               return
   
           # If the linked list is not empty, traverse to the end of the linked list
           while temp.next is not None:
               temp = temp.next
   
           # Now, the last node of the linked list is temp
   
           # Point the next of the last node (temp) to new_node.
           temp.next = new_node
   
           # Assign prev of new_node to temp
           new_node.prev = temp
   
       # Function to print the elements of the doubly linked list
       def print_list(self):
           current = self.head
           while current is not None:
               print(current.data, end=" ")
               current = current.next
           print()
   
   # Creating a sample doubly linked list with values 1, 2, 3
   my_list = DoublyLinkedList()
   my_list.head = Node(1)
   second = Node(2)
   third = Node(3)
   
   my_list.head.next = second
   second.prev = my_list.head
   second.next = third
   third.prev = second
   
   print("Original list:", end=" ")
   my_list.print_list()
   
   # Inserting node with value 6
   my_list.insert_end(6)
   
   # Printing the updated list
   print("List after inserting node 6 at the end:", end=" ")
   my_list.print_list()  

   Run Code >>

   
   class Node {
       int data;
       Node prev;
       Node next;
   
       public Node(int val) {
           data = val;
           prev = null;
           next = null;
       }
   }
   
   class DoublyLinkedList {
       Node head;
   
       // Function to insert a new node at the end of the list
       void insertEnd(int data) {
           // Allocate memory for node
           Node newNode = new Node(data);
   
           // Assign NULL to next of newNode
           newNode.next = null;
   
           // Store the head node temporarily (for later use)
           Node temp = head;
   
           // If the linked list is empty, make the newNode as the head node
           if (head == null) {
               newNode.prev = null;
               head = newNode;
               return;
           }
   
           // If the linked list is not empty, traverse to the end of the linked list
           while (temp.next != null)
               temp = temp.next;
   
           // Now, the last node of the linked list is temp
   
           // Point the next of the last node (temp) to newNode.
           temp.next = newNode;
   
           // Assign prev of newNode to temp
           newNode.prev = temp;
       }
   
       // Function to print the elements of the doubly linked list
       void printList() {
           Node current = head;
           while (current != null) {
               System.out.print(current.data + " ");
               current = current.next;
           }
           System.out.println();
       }
   
       public static void main(String[] args) {
           // Creating a sample doubly linked list with values 1, 2, 3
           DoublyLinkedList myList = new DoublyLinkedList();
           myList.head = new Node(1);
           Node second = new Node(2);
           Node third = new Node(3);
   
           myList.head.next = second;
           second.prev = myList.head;
           second.next = third;
           third.prev = second;
   
           System.out.print("Original list: ");
           myList.printList();
   
           // Inserting node with value 6
           myList.insertEnd(6);
   
           // Printing the updated list
           System.out.print("List after inserting node 6 at the end: ");
           myList.printList();
       }
   }
       

   Run Code >>

   
   #include <iostream>
   
   struct Node {
       int data;
       Node* prev;
       Node* next;
   
       Node(int val) : data(val), prev(nullptr), next(nullptr) {}
   };
   
   // Function to insert a new node at the end of the list
   void insertEnd(Node** head, int data) {
       // Allocate memory for node
       Node* newNode = new Node(data);
   
       // Assign NULL to next of newNode
       newNode->next = nullptr;
   
       // Store the head node temporarily (for later use)
       Node* temp = *head;
   
       // If the linked list is empty, make the newNode as the head node
       if (*head == nullptr) {
           newNode->prev = nullptr;
           *head = newNode;
           return;
       }
   
       // If the linked list is not empty, traverse to the end of the linked list
       while (temp->next != nullptr)
           temp = temp->next;
   
       // Now, the last node of the linked list is temp
   
       // Point the next of the last node (temp) to newNode.
       temp->next = newNode;
   
       // Assign prev of newNode to temp
       newNode->prev = temp;
   }
   
   // Function to print the elements of the doubly linked list
   void printList(Node* head) {
       Node* current = head;
       while (current != nullptr) {
           std::cout << current->data << " ";
           current = current->next;
       }
       std::cout << std::endl;
   }
   
   int main() {
       // Creating a sample doubly linked list with values 1, 2, 3
       Node* myList = new Node(1);
       Node* second = new Node(2);
       Node* third = new Node(3);
   
       myList->next = second;
       second->prev = myList;
       second->next = third;
       third->prev = second;
   
       std::cout << "Original list: ";
       printList(myList);
   
       // Inserting node with value 6
       insertEnd(&myList, 6);
   
       // Printing the updated list
       std::cout << "List after inserting node 6 at the end: ";
       printList(myList);
   
       return 0;
   }
       

   Run Code >>

   Output

   Original list: 1 2 3 
   List after inserting node 6 at the end: 1 2 3 6     

2. Deletion

1. Deletion at the beginning: Here, we will move the head to the next node to delete the node at the beginning and make the previous pointer of the current head point to NULL.

   Let us understand this with an illustration. Suppose we want to delete the first node with the value 1 at the beginning of the given doubly linked list. The following two steps to accomplish this operation:

   1. Reset value node after the del_node (i.e. node two)

   

   2. free the memory of del_node. And, the linked list will look like this:

      

   The above-given steps are implemented in the below program

   Example of Deletion of the First Node of a Doubly Linked List

   • Python
   • Java
   • C++

   
   class Node:
       def __init__(self, val):
           self.data = val
           self.prev = None
           self.next = None
   
   class DoublyLinkedList:
       def __init__(self):
           self.head = None
   
       # Function to delete a node from the doubly linked list
       def delete_node(self, del_node):
           # Check if del_node is the head of the linked list
           if self.head == del_node:
               self.head = del_node.next
   
           # Update the next pointer of the previous node (if del_node is not the head)
           if del_node.prev is not None:
               del_node.prev.next = del_node.next
   
           # Update the prev pointer of the next node (if del_node is not the last node)
           if del_node.next is not None:
               del_node.next.prev = del_node.prev
   
           # Free the memory allocated for del_node (Python automatically handles memory)
   
       # Function to print the elements of the doubly linked list
       def print_list(self):
           current = self.head
           while current is not None:
               print(current.data, end=" ")
               current = current.next
           print()
   
   # Creating a sample doubly linked list with values 1, 2, 3
   my_list = DoublyLinkedList()
   my_list.head = Node(1)
   second = Node(2)
   third = Node(3)
   
   my_list.head.next = second
   second.prev = my_list.head
   second.next = third
   third.prev = second
   
   print("Original list:", end=" ")
   my_list.print_list()
   
   # Deleting the head node (with data 1) from the list
   my_list.delete_node(my_list.head)
   
   print("List after deleting the head node with data 1:", end=" ")
   my_list.print_list()
   

   Run Code >>

   
   class Node {
       int data;
       Node prev;
       Node next;
   
       public Node(int val) {
           data = val;
           prev = null;
           next = null;
       }
   }
   
   class DoublyLinkedList {
       Node head;
   
       // Function to delete a node from the doubly linked list
       void deleteNode(Node delNode) {
           // Check if delNode is the head of the linked list
           if (head == delNode)
               head = delNode.next;
   
           // Update the next pointer of the previous node (if delNode is not the head)
           if (delNode.prev != null)
               delNode.prev.next = delNode.next;
   
           // Update the prev pointer of the next node (if delNode is not the last node)
           if (delNode.next != null)
               delNode.next.prev = delNode.prev;
   
           // Free the memory allocated for delNode (Java automatically handles memory)
       }
   
       // Function to print the elements of the doubly linked list
       void printList() {
           Node current = head;
           while (current != null) {
               System.out.print(current.data + " ");
               current = current.next;
           }
           System.out.println();
       }
   
       public static void main(String[] args) {
           // Creating a sample doubly linked list with values 1, 2, 3
           DoublyLinkedList myList = new DoublyLinkedList();
           myList.head = new Node(1);
           Node second = new Node(2);
           Node third = new Node(3);
   
           myList.head.next = second;
           second.prev = myList.head;
           second.next = third;
           third.prev = second;
   
           System.out.print("Original list: ");
           myList.printList();
   
           // Deleting the head node (with data 1) from the list
           myList.deleteNode(myList.head);
   
           System.out.print("List after deleting the head node with data 1: ");
           myList.printList();
       }
   }
       

   Run Code >>

   
   #include <iostream>
   
   struct Node {
       int data;
       Node* prev;
       Node* next;
   
       Node(int val) : data(val), prev(nullptr), next(nullptr) {}
   };
   
   // Function to delete a node from the doubly linked list
   void deleteNode(Node** head, Node* del_node) {
       // Check if del_node is the head of the linked list
       if (*head == del_node)
           *head = del_node->next;
   
       // Update the next pointer of the previous node (if del_node is not the head)
       if (del_node->prev != nullptr)
           del_node->prev->next = del_node->next;
   
       // Update the prev pointer of the next node (if del_node is not the last node)
       if (del_node->next != nullptr)
           del_node->next->prev = del_node->prev;
   
       // Free the memory allocated for del_node
       delete del_node;
   }
   
   // Function to print the elements of the doubly linked list
   void printList(Node* head) {
       Node* current = head;
       while (current != nullptr) {
           std::cout << current->data << " ";
           current = current->next;
       }
       std::cout << std::endl;
   }
   
   int main() {
       // Creating a sample doubly linked list with values 1, 2, 3
       Node* myList = new Node(1);
       Node* second = new Node(2);
       Node* third = new Node(3);
   
       myList->next = second;
       second->prev = myList;
       second->next = third;
       third->prev = second;
   
       std::cout << "Original list: ";
       printList(myList);
   
       // Deleting the head node (with data 1) from the list
       deleteNode(&myList, myList);
   
       std::cout << "List after deleting the head node with data 1: ";
       printList(myList);
   
       return 0;
   }
       

   Run Code >>

   Output

   Original list: 1 2 3 
   List after deleting head node with data 1: 2 3   

2. Deletion at 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. Let the previous node of the Node be deleted at position pos be Node X and the next node be Node Y. The steps to be followed are:
   • Change the next pointer of Node X to Node Y.
   • Change the prev pointer of Node Y to Node X.

   Let us understand this with an illustration. Suppose we want to delete the second node with value 2 after the first node with value 1 in the given doubly linked list. The following three steps to accomplish this operation:

   1. For the node before the del_node (i.e. first node)
      • Assign the value of the next of del_node to the next of the first node.
   2. For the node after the del_node (i.e. third node)
      • Assign the value of prev of del_node to the prev of the third node.

      

   3. Finally, we will free the memory of del_node. And, the final doubly linked list looks like this.

   

   The above-given steps are implemented in the below program

   Example of Deletion of an Inner Node in Between the Doubly Linked List

   • Python
   • Java
   • C++

   
   class Node:
       def __init__(self, val):
           self.data = val
           self.prev = None
           self.next = None
   
   class DoublyLinkedList:
       def __init__(self):
           self.head = None
   
       # Function to remove a node from the doubly linked list
       def remove_node(self, del_node):
           if del_node.next is not None:
               del_node.next.prev = del_node.prev
   
           if del_node.prev is not None:
               del_node.prev.next = del_node.next
   
           # Optionally free the memory of the deleted node
           del_node = None
   
       # Function to print the elements of the doubly linked list
       def print_list(self):
           current = self.head
           while current is not None:
               print(current.data, end=" ")
               current = current.next
           print()
   
   # Creating a sample doubly linked list
   my_list = DoublyLinkedList()
   
   my_list.head = Node(1)
   second = Node(2)
   third = Node(3)
   
   my_list.head.next = second
   second.prev = my_list.head
   second.next = third
   third.prev = second
   
   print("Original list:", end=" ")
   my_list.print_list()
   
   # Removing the second node (with data 2) from the list
   my_list.remove_node(second)
   
   print("List after removing node with data 2:", end=" ")
   my_list.print_list()
   

   Run Code >>

   
   class Node {
       int data;
       Node prev;
       Node next;
   
       public Node(int val) {
           data = val;
           prev = null;
           next = null;
       }
   }
   
   class DoublyLinkedList {
       Node head;
   
       public DoublyLinkedList() {
           head = null;
       }
   
       // Function to remove a node from the doubly linked list
       void removeNode(Node delNode) {
           if (delNode.next != null)
               delNode.next.prev = delNode.prev;
   
           if (delNode.prev != null)
               delNode.prev.next = delNode.next;
   
           // Optionally free the memory of the deleted node
           delNode = null;
       }
   
       // Function to print the elements of the doubly linked list
       void printList() {
           Node current = head;
           while (current != null) {
               System.out.print(current.data + " ");
               current = current.next;
           }
           System.out.println();
       }
   
       public static void main(String[] args) {
           // Creating a sample doubly linked list
           DoublyLinkedList myList = new DoublyLinkedList();
   
           myList.head = new Node(1);
           Node second = new Node(2);
           Node third = new Node(3);
   
           myList.head.next = second;
           second.prev = myList.head;
           second.next = third;
           third.prev = second;
   
           System.out.print("Original list: ");
           myList.printList();
   
           // Removing the second node (with data 2) from the list
           myList.removeNode(second);
   
           System.out.print("List after removing node with data 2: ");
           myList.printList();
       }
   }
   

   Run Code >>

   
   #include <iostream>
   
   struct Node {
       int data;
       Node* prev;
       Node* next;
       
       Node(int val) : data(val), prev(nullptr), next(nullptr) {}
   };
   
   class DoublyLinkedList {
   public:
       Node* head;
   
       DoublyLinkedList() : head(nullptr) {}
   
       // Function to remove a node from the doubly linked list
       void removeNode(Node* del_node) {
           if (del_node->next != nullptr)
               del_node->next->prev = del_node->prev;
   
           if (del_node->prev != nullptr)
               del_node->prev->next = del_node->next;
   
           // Optionally free the memory of the deleted node
           delete del_node;
       }
   
       // Function to print the elements of the doubly linked list
       void printList() {
           Node* current = head;
           while (current != nullptr) {
               std::cout << current->data << " ";
               current = current->next;
           }
           std::cout << std::endl;
       }
   };
   
   int main() {
       // Creating a sample doubly linked list
       DoublyLinkedList myList;
   
       myList.head = new Node(1);
       Node* second = new Node(2);
       Node* third = new Node(3);
   
       myList.head->next = second;
       second->prev = myList.head;
       second->next = third;
       third->prev = second;
   
       std::cout << "Original list: ";
       myList.printList();
   
       // Removing the second node (with data 2) from the list
       myList.removeNode(second);
   
       std::cout << "List after removing node with data 2: ";
       myList.printList();
   
       return 0;
   }
    

   Run Code >>

   Output

    Original list: 1 2 3 
   List after removing node with data 2: 1 3 
   

3. Deletion at the end: Here we will move the tail to the previous node to delete the node at the end and make the next pointer of the tail node point to NULL.

   Let us understand this with an illustration. Suppose we want to delete the last node with the value 3 at the end of the given doubly linked list.

   1. delete the del_node and make the next of node before del_node point to NULL.

      

   2. The final doubly linked list looks like this.

   

   Example of Deletion of the Last Node of Doubly Linked List

   • Python
   • Java
   • C++

   
   class Node:
       def __init__(self, val):
           self.data = val
           self.prev = None
           self.next = None
   
   class DoublyLinkedList:
       def __init__(self):
           self.head = None
   
       # Function to delete the last node from the doubly linked list
       def delete_last_node(self):
           # Check if the linked list is empty
           if self.head is None:
               print("List is empty. Cannot delete last node.")
               return
   
           # Traverse to the last node
           temp = self.head
           while temp.next is not None:
               temp = temp.next
   
           # Check if the list has only one node
           if temp.prev is None:
               self.head = None  # Set head to None as the list is now empty
           else:
               # Update the next pointer of the previous node to None
               temp.prev.next = None
   
       # Function to print the elements of the doubly linked list
       def print_list(self):
           current = self.head
           while current is not None:
               print(current.data, end=" ")
               current = current.next
           print()
   
   # Creating a sample doubly linked list with values 1, 2, 3
   my_list = DoublyLinkedList()
   my_list.head = Node(1)
   second = Node(2)
   third = Node(3)
   
   my_list.head.next = second
   second.prev = my_list.head
   second.next = third
   third.prev = second
   
   print("Original list:", end=" ")
   my_list.print_list()
   
   # Deleting the last node from the list
   my_list.delete_last_node()
   
   print("List after deleting the last node:", end=" ")
   my_list.print_list()   

   Run Code >>

   
   class Node {
       int data;
       Node prev;
       Node next;
   
       public Node(int val) {
           data = val;
           prev = null;
           next = null;
       }
   }
   
   class DoublyLinkedList {
       Node head;
   
       // Function to delete the last node from the doubly linked list
       void deleteLastNode() {
           // Check if the linked list is empty
           if (head == null) {
               System.out.println("List is empty. Cannot delete last node.");
               return;
           }
   
           // Traverse to the last node
           Node temp = head;
           while (temp.next != null)
               temp = temp.next;
   
           // Check if the list has only one node
           if (temp.prev == null) {
               head = null; // Set head to null as the list is now empty
           } else {
               // Update the next pointer of the previous node to null
               temp.prev.next = null;
           }
       }
   
       // Function to print the elements of the doubly linked list
       void printList() {
           Node current = head;
           while (current != null) {
               System.out.print(current.data + " ");
               current = current.next;
           }
           System.out.println();
       }
   
       public static void main(String[] args) {
           // Creating a sample doubly linked list with values 1, 2, 3
           DoublyLinkedList myList = new DoublyLinkedList();
           myList.head = new Node(1);
           Node second = new Node(2);
           Node third = new Node(3);
   
           myList.head.next = second;
           second.prev = myList.head;
           second.next = third;
           third.prev = second;
   
           System.out.print("Original list: ");
           myList.printList();
   
           // Deleting the last node from the list
           myList.deleteLastNode();
   
           System.out.print("List after deleting the last node: ");
           myList.printList();
       }
   }
       

   Run Code >>

   
   #include <iostream>
   
   struct Node {
       int data;
       Node* prev;
       Node* next;
   
       Node(int val) : data(val), prev(nullptr), next(nullptr) {}
   };
   
   // Function to delete the last node from the doubly linked list
   void deleteLastNode(Node** head) {
       // Check if the linked list is empty
       if (*head == nullptr) {
           std::cout << "List is empty. Cannot delete last node." << std::endl;
           return;
       }
   
       // Traverse to the last node
       Node* temp = *head;
       while (temp->next != nullptr)
           temp = temp->next;
   
       // Check if the list has only one node
       if (temp->prev == nullptr) {
           delete temp;
           *head = nullptr; // Set head to null as the list is now empty
       } else {
           // Update the next pointer of the previous node to null
           temp->prev->next = nullptr;
           delete temp;
       }
   }
   
   // Function to print the elements of the doubly linked list
   void printList(Node* head) {
       Node* current = head;
       while (current != nullptr) {
           std::cout << current->data << " ";
           current = current->next;
       }
       std::cout << std::endl;
   }
   
   int main() {
       // Creating a sample doubly linked list with values 1, 2, 3
       Node* myList = new Node(1);
       Node* second = new Node(2);
       Node* third = new Node(3);
   
       myList->next = second;
       second->prev = myList;
       second->next = third;
       third->prev = second;
   
       std::cout << "Original list: ";
       printList(myList);
   
       // Deleting the last node from the list
       deleteLastNode(&myList);
   
       std::cout << "List after deleting the last node: ";
       printList(myList);
   
       return 0;
   }
       

   Run Code >>

   Output

   Original list: 1 2 3 
   List after deleting the last node: 1 2  

3. Traversal

Algorithm for Traversing a Doubly Linked List

  
Step 1. Set a pointer current to the head of the doubly linked list.
Step 2. If the doubly linked list is empty (i.e., current is null), then the traversal is complete.
Step 3. While the current pointer is not null:
    a. Process the data of the current node.
    b. Move the current pointer to the next node (current = current->next).
    or
    b. Move the 'current' pointer to the previous node (current = current->prev)
Step 4. The traversal is complete when the 'current' pointer becomes null.
    

Example of Traversing a Doubly Linked List

class Node:
    def __init__(self, val):
        self.value = val
        self.previous = None
        self.next = None

class DoublyLinkedList:
    def traverse_forward(self, start):
        current = start

        # Checks whether the list is empty
        if start is None:
            print("Node to start from is NULL")
            return

        while current is not None:
            print("Node:", current.value)
            current = current.next

    def traverse_backward(self, start):
        current = start

        # Checks whether the list is empty
        if start is None:
            print("Node to start from is NULL")
            return

        while current is not None:
            print("Node:", current.value)
            current = current.previous

# Creating a sample doubly linked list
first = Node(1)
second = Node(2)
third = Node(3)

first.next = second
second.previous = first
second.next = third
third.previous = second

my_list = DoublyLinkedList()

print("Traversing forward:")
my_list.traverse_forward(first)

print("Traversing backward:")
my_list.traverse_backward(third)

class Node {
    int value;
    Node previous;
    Node next;

    public Node(int val) {
        value = val;
        previous = null;
        next = null;
    }
}

class DoublyLinkedList {
    void traverseForward(Node start) {
        Node current = start;

        // Checks whether the list is empty
        if (start == null) {
            System.out.println("Node to start from is NULL");
            return;
        }

        while (current != null) {
            System.out.println("Node: " + current.value);
            current = current.next;
        }
    }

    void traverseBackward(Node start) {
        Node current = start;

        // Checks whether the list is empty
        if (start == null) {
            System.out.println("Node to start from is NULL");
            return;
        }

        while (current != null) {
            System.out.println("Node: " + current.value);
            current = current.previous;
        }
    }
}

class Main {
    public static void main(String[] args) {
        // Creating a sample doubly linked list
        Node first = new Node(1);
        Node second = new Node(2);
        Node third = new Node(3);

        first.next = second;
        second.previous = first;
        second.next = third;
        third.previous = second;

        DoublyLinkedList myList = new DoublyLinkedList();

        System.out.println("Traversing forward:");
        myList.traverseForward(first);

        System.out.println("Traversing backward:");
        myList.traverseBackward(third);
    }
}
 

 #include <iostream>

class Node {
public:
    int value;
    Node* previous;
    Node* next;

    Node(int val) : value(val), previous(nullptr), next(nullptr) {}
};

class DoublyLinkedList {
public:
    void traverseForward(Node* start) {
        Node* current = start;

        // Checks whether the list is empty
        if (start == nullptr) {
            std::cout << "Node to start from is NULL" << std::endl;
            return;
        }

        while (current != nullptr) {
            std::cout << "Node: " << current->value << std::endl;
            current = current->next;
        }
    }

    void traverseBackward(Node* start) {
        Node* current = start;

        // Checks whether the list is empty
        if (start == nullptr) {
            std::cout << "Node to start from is NULL" << std::endl;
            return;
        }

        while (current != nullptr) {
            std::cout << "Node: " << current->value << std::endl;
            current = current->previous;
        }
    }
};

int main() {
    // Creating a sample doubly linked list
    Node* first = new Node(1);
    Node* second = new Node(2);
    Node* third = new Node(3);

    first->next = second;
    second->previous = first;
    second->next = third;
    third->previous = second;

    DoublyLinkedList myList;

    std::cout << "Traversing forward:" << std::endl;
    myList.traverseForward(first);

    std::cout << "Traversing backward:" << std::endl;
    myList.traverseBackward(third);

    // Clean up memory (delete nodes)
    delete third;
    delete second;
    delete first;

    return 0;
}

Output

Traversing forward:
Node: 1
Node: 2
Node: 3
Traversing backward:
Node: 3
Node: 2
Node: 1

4. Search

Step 1. Start with a pointer current at the head of the doubly linked list.
Step 2. If the doubly linked list is empty (i.e., current is null), the value is not found.
Step 3. While the current pointer is not null:
    a. Check if the data in the current node is equal to the target value.
        - If yes, the value is found, and you can return the node or its position.
    b. Move the current pointer to the next node (current = current->next).
Step 4. If the current pointer becomes null and the value is not found, then the value is not present in the list.

Example of Searching in a Doubly Linked List

class Node:
    def __init__(self, val):
        self.value = val
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def search_node(self, value):
        i = 1
        # Node current will point to head
        current = self.head

        # Checks whether the list is empty
        if self.head is None:
            print("List is empty")
            return

        # Traversing the List.
        while current is not None:
            # Compare value to be searched with each node in the list
            if current.value == value:
                print(f"Node {value} is present in the list at the position: {i}")
                return
            current = current.next
            i += 1

        print(f"Node {value} is not present in the list")

# Creating a sample linked list
my_list = LinkedList()
my_list.head = Node(7)
my_list.head.next = Node(8)
my_list.head.next.next = Node(9)
my_list.head.next.next.next = Node(4)

# Searching for a node in the linked list
my_list.search_node(8)
my_list.search_node(6)

class Node {
    int value;
    Node next;

    Node(int val) {
        value = val;
        next = null;
    }
}

class LinkedList {
    Node head;

    void searchNode(int value) {
        int i = 1;
        // Node current will point to head
        Node current = head;

        // Checks whether the list is empty
        if (head == null) {
            System.out.println("List is empty");
            return;
        }

        // Traversing the List.
        while (current != null) {
            // Compare value to be searched with each node in the list
            if (current.value == value) {
                System.out.println("Node " + value + " is present in the list at the position: " + i);
                return;
            }
            current = current.next;
            i++;
        }
        System.out.println("Node " + value + " is not present in the list");
    }

    public static void main(String[] args) {
        // Creating a sample linked list
        LinkedList myList = new LinkedList();
        myList.head = new Node(7);
        myList.head.next = new Node(8);
        myList.head.next.next = new Node(9);
        myList.head.next.next.next = new Node(4);

        // Searching for a node in the linked list
        myList.searchNode(8);
        myList.searchNode(6);
    }
}
    

#include <iostream>

class Node {
public:
    int value;
    Node* next;

    Node(int val) : value(val), next(nullptr) {}
};

class LinkedList {
public:
    Node* head;

    void searchNode(int value) {
        int i = 1;
        // Node current will point to head
        Node* current = head;

        // Checks whether the list is empty
        if (head == nullptr) {
            std::cout << "List is empty" << std::endl;
            return;
        }

        // Traversing the List.
        while (current != nullptr) {
            // Compare value to be searched with each node in the list
            if (current->value == value) {
                std::cout << "Node " << value << " is present in the list at the position: " << i << std::endl;
                return;
            }
            current = current->next;
            i++;
        }
        std::cout << "Node " << value << " is not present in the list" << std::endl;
    }
};

int main() {
    // Creating a sample linked list
    LinkedList myList;
    myList.head = new Node(7);
    myList.head->next = new Node(8);
    myList.head->next->next = new Node(9);
    myList.head->next->next->next = new Node(4);

    // Searching for a node in the linked list
    myList.searchNode(8);
    myList.searchNode(6);

    return 0;
}
    

Output

Node 8 is present in the list at the position: 2
Node 6 is not present in the list    

Complexity Analysis of Doubly Linked List Operations

Singly Linked List Vs Doubly Linked List

Applications of Doubly Linked List

1. Browser History: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.
2. 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.
3. 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.
4. 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.
5. 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.
6. 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

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.
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: The doubly linked list can be used to manage memory efficiently, as nodes can be easily added or removed as needed.
5. Implementing other data structures:It can be used to implement different tree data structures.

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. Slower access and search times: Access and search operations have O(n) time complexity, where n is the number of elements in the list. This can result in slower performance than other data structures like arrays or trees, especially for large lists.
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

Summary

So, here we saw every aspect of a doubly linked list in data structures. You might have got at least some idea regarding doubly linked lists and their applications. I know it's quite difficult and tricky to understand the whole topic in a single go. There are a lot of concepts and logic to be understood in this. Therefore, refer to it again and again till you get thorough with the linked list in data structures. To test your knowledge of linked lists, enroll in our Dsa Course Online.