Introduction and Implementation of Doubly Linked Lists

Introduction

A doubly-linked list is a data structure that consists of sequentially linked records which are called nodes. A node contains two fields, called links, that refer to the previous and the next node in the sequence of nodes. The Questions related to doubly linked lists are frequently asked in leading product-based companies including Amazon, Facebook, Google.

This article sheds light on the doubly linked lists and the various operations performed on them with code in Java.

Doubly Linked List Representation

A node in a doubly-linked list consists of three parts, the data, a pointer to the next node of the sequence, and a pointer to the previous sequence node.

As in a singly linked list, a doubly-linked list also has a head pointer that points to the first node of the linked list.

(Node representation of DLL)

A doubly linked list node in Java is represented as follows:

public class Implementation
{
    Node head; // head of the Linked List
    class Node
    {
        int data;
        Node next;  // Pointer to the next node
        Node prev;  // Pointer to previous node
        
        // Constructor for creating a new node
        Node(int value)
        {
            data = value;
            next = prev = null;
        }
    }
}

A doubly linked list consists of a collection of nodes containing an extra pointer, typically called a previous pointer, together with the next pointer and data which are there in the Singly Linked List. A doubly linked list containing three nodes having numbers from 10 to 30 in their data part is shown in the following image.

The previous pointer of the first node and the next pointer of the last node is set to Null.  The previous pointer set to null indicates that this is the first node of the doubly linked list and the next pointer set to null indicates that this is the last node of the doubly linked list.

Basic Operations on Doubly Linked Lists

Following are the basic operations supported by Doubly Linked Lists:

1. Insertion: This operation is used for adding new elements to the list. A new element can be added at the front, at the end of a linked list, or after a given node. The various insertion techniques are discussed below.
2. Deletion: This operation is used to remove elements from the list. The node to be deleted may be the first node, last node, or any node in between the first and last node.
3. Traversal: This operation is used to access each element of the list. The Linked List is traversed when printing the contents of the linked list.

Insertion in Doubly Linked Lists

A Node in a doubly-linked list has a pointer to both the previous and the next node of the linked list. Insertion of a new node in an existing doubly linked list can be done in the following places:

1. Insertion at the Beginning
2. Insertion at the End
3. Insertion after a given Node

Insertion at the Beginning

The head pointer points to the first node of the doubly linked list, and the previous pointer of the first node points to Null. To insert a node at the beginning of the Linked List, the head pointer should point to the new first node, and the next pointer of the new first node must point to the previous first node. This is illustrated in the diagram below

(Diagram illustrating Insertion at Beginning Operation)

The code for insertion of a new node at the beginning of a doubly linked list in Java is given below:

// Function for insertion of a new node at the beginning of
// a doubly linked list

public void insertAtBeginning(int data)
{
    // Making a new node with the given data. Note that the
    // previous and next pointer of this node are null
    Node new_node = new Node(data);
    
    // The next pointer of the new node should point to head of DLL i.e. the original first node
    new_node.next = head;
    
    // The previous pointer of new node should point to Null
    new_node.prev = null;
    
    // Change the previous of the node where the head was initially pointing that 
    // is the original first node
    if(head != null)
    {
        head.prev = new_node;
    }
    
    // Head pointer should point to the new node
    head = new_node;
}

Insertion at the End of DLL

The next pointer of the last node of the DLL points to Null. To insert a new node at the last position of the DLL, three important points need to be taken into consideration:

1. The next pointer of the new node should point to the Null
2. The previous pointer of the new node should point to the old last node.
3. The next pointer of the old last node should point to the new last node.

This is illustrated in the following diagram:

Also, there may be a case where the DLL is initially empty. In that case, the newly created node will become both the first and the last node of the doubly linked list.

The code for insertion of a new node as the last node in Java is given below:

// To insert a node at the end of a Doubly Linked List
public void insertAtLast(int data)
{
    // Creating a new node with the given data
    Node newNode = new Node(data);
    
    // A temporary pointer that will be used for traversing DLL
    Node temp = head;
    
    // Making the next of newNode as Null
    newNode.next = null;
    
    // If DLL is empty then this node will be both the first as
    // well as the last node
    if(head == null)
    {
        newNode.prev = null;
        head = newNode;
        return;
    }
    
    // If DLL is not empty, then traverse till the end of DLL. Make
    // the next pointer of the original last node point to the new
    // last node and the previous of the last node to the original 
    // last node
    
    while(temp.next != null)
    {
        temp = temp.next;
    }  // Now temp points to the original last node
    
    // Illustarted by Blue color in the diagram
    temp.next = newNode;

    // Illstrated by orange color in the diagram
    newNode.prev = temp;
}

Insertion after a given Node

There may be cases wherein a record or data is to be inserted after a given record or data. If the data is stored in a Linked List, the insertion after a given node operation in Linked List is used for such cases.

For inserting a new node after a given node, the following points need to be under consideration:

1. The records next to the previous node should now be linked to the new node to be inserted.
2. The previous node’s next pointer should be linked to the new node, and the new node’s previous pointer should be linked to the previous node.

The process is illustrated in the following diagram.

The code for insertion of a new node after a given previous node in Java is given below.

public void insertAfter(Node prevNode, int data)
{
    // if the previous node is null
    if(prevNode == null)
    {
        System.out.println("The given previous node cannot be null");
        return;
    }
    
    // Create a new node with the given data
    Node newNode = new Node(data);
    
    // The next pointer of this node should point to
    // the next of prevNode
    newNode.next = prevNode.next;
    
    // The next pointer of prevNode should point to the
    // newNode
    prevNode.next = newNode;
    
    // The previous pointer of newNode should point to the
    // prevNode
    newNode.prev = prevNode;
    
    // Change previous of newNode's next node 
    if (newNode.next != null)
        newNode.next.prev = newNode;
}

Printing a Doubly Linked Lists

The Linked Lists is traversed using a temporary pointer that initially points to the head of the linked list. The temporary pointer is incremented, and the contents of the Doubly Linked List are printed.

Following is the code to print a doubly-linked list in Java

/* A utility function to print the contents of 
a doubly linked list. The function takes the head
pointer of the linked list*/
public void printLinkedList(Node head)
{
    if(head == null)
    {
        System.out.println("The List is empty");
        return;
    }
     // A temporary node that will be used for traversal
    Node temp = head;
    
    System.out.println("Traversal of Linked List");
    
    // Traverse the DLL by incrementing the pointer
    while(temp != null)
    {
        System.out.println(temp.data + " --> ");
        temp = temp.next;
    }
    
}

Deletion in Doubly Linked Lists

There are three cases for deletion of a node in a doubly-linked list:

1. If the node to be deleted is the head node

If the node to be deleted is the head node, then the immediate next node will be the new head node. The head pointer will point to the next node.

2. If the node to be deleted is the last node

The second last node will point to Null. All the other nodes will be at their respective positions in the Linked List.

3. If the node to be deleted is in between the first and last node

Traverse the linked list until the node is deleted, change the next and previous pointers of the Linked List.

This is illustrated in the diagram below. The pointer links shown by red color will be deleted, and the pointer links shown by blue color will be created for the deletion of the node with Data 20.

The Java program for the deletion of a node in a doubly-linked list is given below:

/* A utility function to delete a node of 
a doubly linked list. The function takes the pointer 
of the node to be deleted*/

void deleteNode(Node ptr)
{
    // Base case where the List is empty
    if(head == null || ptr == null)
    {
        System.out.println("The List is empty");
        return;
    }
    
    // When the node to be deleted is the 
    // head node
    if(ptr == head)
    {
        // The head pointer will now point to the
        // next node 
        head = ptr.next;
       // Since the head node is to be deleted, then the previous of
       // the new head node has to be null
       if(head != null)
                 head.prev = null;
      
    }
    
    // If node to be deleted is not the last node
    if(ptr.next != null)
    {
        ptr.next.prev = ptr.prev;
    }
    
    // If node to be deleted is not the first node
    if(ptr.prev != null)
    {
        ptr.prev.next = ptr.next;
    }
}

So now you have a clear understanding of the Doubly Linked list and the various operations that can be performed on it. Below is the complete working program to test the above functions

Complete Working Program

public class DoubleLinkedList
{
    Node head;
    class Node
    {
        int data;
        Node next, prev;
        public Node(int value){
            data = value;
            next = prev = null;
        }
    }
// Function for insertion of a new node at the beginning of
// a doubly linked list

public void insertAtBeginning(int data)
{
    Node new_node = new Node(data);
    new_node.next = head;
    new_node.prev = null;
    if(head != null){
        head.prev = new_node;
    }
    head = new_node;
}
// To insert a node at the end of a Doubly Linked List
public void insertAtLast(int data)
{
    Node newNode = new Node(data);
    Node temp = head;
    newNode.next = null;
    if(head == null){
        newNode.prev = null;
        head = newNode;
        return;
    }

    while(temp.next != null){
        temp = temp.next;
    } 
    temp.next = newNode;
    newNode.prev = temp;
}
// Function to insert a node after a given node
public void insertAfter(Node prevNode, int data)
{
    if(prevNode == null){
        System.out.println("The given previous node cannot be null");
        return;
    }
    Node newNode = new Node(data);
    newNode.next = prevNode.next;
    prevNode.next = newNode;
    newNode.prev = prevNode;
    if (newNode.next != null)
        newNode.next.prev = newNode;
}

void deleteNode(Node ptr)
{
    if(head == null || ptr == null){
        System.out.println("The List is empty");
        return;
    }

    if(ptr == head){
        head = ptr.next;
    }
    
    if(ptr.next != null){
        ptr.next.prev = ptr.prev;
    }
    
    if(ptr.prev != null){
        ptr.prev.next = ptr.next;
    }
}

public void printLinkedList(Node head)
{
    if(head == null){
        System.out.println("The List is empty");
        return;
    }
    Node temp = head;
    System.out.println("Traversal of Linked List");
    
    while(temp != null){
        if(temp.next == null){
            System.out.println(temp.data);
            return;
        }
        else{
        System.out.print(temp.data + " -> ");
        temp = temp.next;
        }
    }
    
}

public static void main(String[]args)
{
    DoubleLinkedList dll = new DoubleLinkedList();
    dll.insertAtBeginning(10); // 10 -> Null
    dll.insertAtBeginning(0); // 0 -> 10 -> Null
    dll.insertAtLast(20); // 0 -> 10 -> 20 -> Null
    dll.insertAfter(dll.head.next.next, 30); //  0 -> 10 -> 20 -> 30 -> Null
    dll.insertAtLast(60); // 0 -> 10  -> 20 -> 30 -> 60 -> Null
    dll.printLinkedList(dll.head);
    // Node to be deleted is 20
    dll.deleteNode(dll.head.next.next);
    System.out.println("After deletion operation");
    dll.printLinkedList(dll.head);
}
}

The output of the above program is:

Traversal of Linked List
0 -> 10 -> 20 -> 30 -> 60
After deletion operation
Traversal of Linked List
0 -> 10 -> 30 -> 60

Advantages of Doubly Linked Lists

Following are the main advantages of Doubly Linked Lists:-

1. A DLL can be traversed in both forward and reverse directions
2. A new node can be inserted before a given node quite easily by just changing the pointers.
3. The complete Linked List need not be traversed for deletion operation as in Singly Linked List.

Disadvantages of Doubly Linked Lists

Following are the main disadvantages of Doubly Linked Lists:-

1. Additional memory space is required to store the previous pointer and the next pointer and the data to be stored.
2. All the manipulation operations require both the previous and next pointers to be manipulated, imposing operational overhead.

Frequently Asked Questions

Key Takeaways

This blog clearly explained the Doubly Linked Lists,  the advantages and disadvantages, and various manipulation techniques were discussed and implemented in Java Programming Language.

It is an important topic, and questions related to DLL are frequently asked in almost all the major companies. It would be best if you practiced questions related to the topic to better understand the concepts studied. While this is one of the most important topics, there are other important topics as well. Questions related to various topics are given in a structured manner in Codestudio. There are Guided Paths and Blogs as well !!

Keep Learning and Keep Exploring!!

By: Manvi Chaddha