Doubly Linked List Algorithm in Data Structures with Examples

Doubly Linked List Algorithm in Data Structures with Examples

06 Jun 2024
Beginner
14.4K Views
114 min read
Learn via Video Course & by Doing Hands-on Labs

Free DSA Course with Certificate (Online)

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

Doubly Linked List

Representation of a Doubly Linked List in Data Structures

In the given figure,

Doubly linked list in Data Structures

We can see a doubly linked list that consists of nodes, where each node contains a
value and two pointers: prev to the previous node, and next to the next node. This allows for traversal in both directions.

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,

one, two, and three are the nodes with data items 1, 2, and 3 respectively.
  • 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.

Memory Representation of a doubly linked list

  • 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.

Memory Representation of a doubly linked list

Standard Operations on Doubly Linked Lists in Data Structures

  1. Insertion

Adding a node to a doubly linked list is similar to adding a node to a linked list. The only extra work is to handle the pointer to the previous node. It is faster than linked lists because we just need to change the pointers of adjacent elements of the element we are inserting.

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.

Insertion in a Doubly Linked List

In the above given doubly linked list, Insertion can be done in three ways:
  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.

      Insertion

    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

      Insertion at the beginning of a double linked list

    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

      Final result of Insertion at the beginning of a double linked list

    The above-given steps are implemented in the below program

    Example of Insertion at the Beginning of a Doubly Linked List

    
    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()
    
    
    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();
        }
    }
        
    
     #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;
    }
     

    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.

      Insertion at a specific position in a doubly linked list

    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.

      Insertion at a specific position/in between the nodes

    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

      Insertion at a specific position/in between the nodes

      The final doubly linked list after this insertion is:

      Final result of Insertion at a specific position/in between the nodes

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

    
    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()    
    
    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();
        }
    }
        
    
    #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;
    }
        

    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. Insertion at the end of a doubly linked list

    3. 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.

      Insertion at the end

    4. The final doubly linked list after this insertion is:

      Final result of Insertion at the end in Doubly linked list

    Example of Insertion at the End of a Doubly Linked List

    
    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()  
    
    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();
        }
    }
        
    
    #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;
    }
        

    Output

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

  1. Deletion

Similar to Insertion, deletion in a Doubly Linked List is also fast. It can be done by just changing the pointers of its adjacent Nodes.

doubly linked list

In the above given doubly linked list, deletion can also be done in three ways:
  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. Deletion at the beginning of a doubly linked list

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

      Final result of deletion at the beginning of doubly linked list

    The above-given steps are implemented in the below program

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

    
    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()
    
    
    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();
        }
    }
        
    
    #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;
    }
        

    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.

      Deletion at a specific position of a doubly linked list

    3. Finally, we will free the memory of del_node. And, the final doubly linked list looks like this.
    4. Final result of Deletion at a specific position in a doubly linked list

    The above-given steps are implemented in the below program

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

    
    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()
    
    
    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();
        }
    }
    
    
    #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;
    }
     

    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.
    3. Deletion at the end of the doubly linked list

    Example of Deletion of the Last Node of Doubly Linked List

    
    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()   
    
    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();
        }
    }
        
    
    #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;
    }
        

    Output

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

  1. Traversal

You can traverse the doubly linked list in both directions. We can go to the previous node by following the previous pointers and similarly go to the next nodes by following the next pointers to perform some specific operations like searching, sorting, display, etc.

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

  1. Search

To search in the given doubly linked list, we need to traverse the entire doubly linked list from the first node and keep moving to the next nodes using the next pointer. We can compare each transversed element against the one we are searching for.
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

Operations Time Complexity Space Complexity
Insertion at the beginning

O(1)

O(1)

Insertion at a specific position

O(n)

O(1)

Insertion at the end

O(1)

O(1)

Deletion at the beginning

O(1)

O(1)

Deletion at a specific position

O(n)

O(1)

Deletion at the end

O(1)

O(1)

Traversal

O(n)

O(1)

Search

O(n)

O(1)

Singly Linked List Vs Doubly Linked List

Singly linked list (SLL) Doubly Linked List (DLL)
SLL nodes contain 2 fields -the data field and the next link field. DLL nodes contain 3 fields - the data field, a previous link field, and a next link field.
In SLL, the traversal can be done using the next node link only. Thus traversal is possible in one direction only. In DLL, the traversal can be done using the previous node-link or the next node link. Thus traversal is possible in both directions (forward and backward).
The SLL occupies less memory than DLL as it has only 2 fields. The DLL occupies more memory than SLL as it has 3 fields.
The complexity of insertion and deletion at a given position is O(n). The complexity of insertion and deletion at a given position is O(n / 2) = O(n) because traversal can be made from the start or the end.
Complexity of deletion with a given node is O(n), because the previous node needs to be known, and traversal takes O(n) Complexity of deletion with a given node is O(1) because the previous node can be accessed easily
We mostly prefer to use singly linked list for the execution of stacks. We can use a doubly linked list to execute heaps, stacks, binary trees, etc.
When we do not need to perform any searching operation and we want to save memory, we prefer a singly linked list. In case of better implementation, while searching, we prefer to use a doubly linked list.
A singly linked list consumes less memory as compared to a doubly linked list. The doubly linked list consumes more memory as compared to the singly linked list.
It is less efficient as compared to a doubly-linked list. It is more efficient.

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.

FAQs

Q1. How many pointers does a Doubly Linked List have?

 A Doubly Linked List has two pointers: prev to the previous node, and next to the next.

Q2. How a Doubly Linked List is represented in memory?

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.

Q3. Where are doubly linked lists used?

We can use a doubly linked list to execute heaps, stacks, binary trees, etc.
Share Article

Live Classes Schedule

Our learn-by-building-project method enables you to build practical/coding experience that sticks. 95% of our learners say they have confidence and remember more when they learn by building real world projects.
Generative AI For Software Developers Jul 20 SAT, SUN
Filling Fast
08:30PM to 10:30PM (IST)
Get Details
Angular Certification Course Jul 20 SAT, SUN
Filling Fast
06:00PM to 08:00PM (IST)
Get Details
Azure Master Class Jul 20 SAT, SUN
Filling Fast
03:00PM to 05:00PM (IST)
Get Details
ASP.NET Core Certification Training Jul 28 SAT, SUN
Filling Fast
07:00AM to 09:00AM (IST)
Get Details
Software Architecture and Design Training Jul 28 SAT, SUN
Filling Fast
05:30PM to 07:30PM (IST)
Get Details
.NET Solution Architect Certification Training Jul 28 SAT, SUN
Filling Fast
05:30PM to 07:30PM (IST)
Get Details
Azure Developer Certification Training Jul 28 SAT, SUN
Filling Fast
10:00AM to 12:00PM (IST)
Get Details
Advanced Full-Stack .NET Developer Certification Training Jul 28 SAT, SUN
Filling Fast
07:00AM to 09:00AM (IST)
Get Details
Data Structures and Algorithms Training with C# Jul 28 SAT, SUN
Filling Fast
08:30PM to 10:30PM (IST)
Get Details
Angular Certification Course Aug 11 SAT, SUN
Filling Fast
09:30AM to 11:30AM (IST)
Get Details
ASP.NET Core Project Aug 24 SAT, SUN
Filling Fast
07:00AM to 09:00AM (IST)
Get Details

Can't find convenient schedule? Let us know

About Author
Amit Kumar Ghosh (SDE and Mentor at Scholarhat)

As a software developer with a wealth of experience, he brings a unique combination of technical acumen and a passion for mentorship to my role. With 6 years of experience, he has honed the skills in C/C++, Java, Python, SQL, C#, JavaScript, React, Java Spring etc. and has a proven track record of delivering high-quality, scalable software solutions and core Computer fundamental knowledge DSA, OOPs, CN, OS etc.

As a teacher, his approach revolves around interactive techniques, prioritizing hands-on learning and real-world projects. He explains concepts clearly, offer practical examples, and encourage questions to foster a supportive environment.
Accept cookies & close this