Doubly Linked list

A doubly linked list (DLL) is a type of linked list where each node has a pointer to both the previous node and the next node.

Standard Operations on Doubly Linked Lists in Data Structures

Insertion

Adding a node to a doubly linked list is similar to adding a node to a linked list. The only extra work is handling the pointer to the previous node. It is faster than linked lists because we just need to change the pointers of the 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.

In the given doubly linked list, insertion can be done in three ways:

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

   Let's understand this with an example. Suppose we want to insert a node with value 6 at the beginning of the doubly linked list. Follow these steps:

   1. Create a new node

      • Allocate memory for the new node.

      • Assign the data to the new node.

1. 1. 

      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. 

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

      5. 

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()

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 need to insert a node at the position of Node X. The steps are:

   • Traverse the doubly linked list to 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 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's understand this with an example. Suppose we want to insert a node with value 6 after the second node with value 2 in the doubly linked list. Here are the steps:

1. Create a new node

   • Allocate memory for the new node.

   • Assign the data to the new node.

1. 

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. 

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

5. 

   The final doubly linked list after this insertion is:

   

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()

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 add the new node at the end of the list, after the tail node, and the tail then points to the new node.

   Let's understand this with an example. Suppose we want to add a node with value 6 at the end of the given doubly linked list. We can do this in two steps:

   1. Create a new node

   2. 

   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.

      

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

      

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()

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.

In the above given doubly linked list, deletion can also be done in three ways:

1. Deletion at the beginning: To delete the first node, we move the head to the next node and set the previous pointer of the new head to NULL.

   Let's see an example. Suppose we want to delete the first node with the value 1 in the given doubly linked list. Here are the steps:

   1. Set the new head to the node after the node to be deleted (i.e., node two).

1. 

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

    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()

2. Deleting a node at a specific position: To remove a node from a specific spot in the list, you need to go through the list until you reach that spot. Let's call the node before the one you want to delete Node X and the node after it Node Y. Here are the steps:

   • Change the next pointer of Node X to point to Node Y.

   • Change the prev pointer of Node Y to point to Node X.

Let's understand this with an example. Suppose we want to delete the second node with value 2 after the first node with value 1 in the given doubly linked list. Here are the steps:

1. For the node before the del_node (i.e., the first node):

   • Set the next of the first node to the next of the del_node.

2. For the node after the del_node (i.e., the third node):

   • Set the prev of the third node to the prev of the del_node.

1. 

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

3. 

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()

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. 

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()

Traversal

You can move through the doubly linked list in both directions. You can go to the previous node using the previous pointers and go to the next nodes using the next pointers. This allows you to do tasks like searching, sorting, and displaying the list.

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.

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)

Search

To search in the given doubly linked list, we need to go through the list starting from the first node and keep moving to the next nodes using the next pointer. We can compare each visited element with the one we are looking 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.

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)

Complexity Analysis of Doubly Linked List Operations

Singly Linked List Vs Doubly Linked List

Advantages of Doubly LinkedList over thesingly linked list:

• A DLL can be traversed in both forward and backward directions.

• The delete operation in a DLL is more efficient if a pointer to the node to be deleted is given.

• We can quickly insert a new node before a given node.

• In a singly linked list, to delete a node, a pointer to the previous node is needed. To get this previous node, sometimes the list is traversed. In a DLL, we can get the previous node using the previous pointer.

Disadvantages of Doubly LinkedList over the singly linked list:

• Every node of a DLL needs extra space for a previous pointer. It is possible to implement a DLL with a single pointer though .

• All operations need an extra previous pointer to be maintained. For example, in insertion, we need to update previous pointers along with the next pointers. In the following functions for insertions at different positions, we need 1 or 2 extra steps to set the previous pointer.