Doubly Linked List in Java

What is Doubly Linked List?

Doubly Linked List is a variation of the linked list. The linked list is a linear data structure that can be described as the collection of nodes. Nodes are connected through pointers. Each node contains two fields: data and pointer to the next field. The first node of the linked list is called the head, and the last node of the list is called the tail of the list.

One of the limitations of the singly linked list is that it can be traversed in only one direction that is forward. The doubly linked list has overcome this limitation by providing an additional pointer that points to the previous node. With the help of the previous pointer, the doubly linked list can be traversed in a backward direction thus making insertion and deletion operations easier to perform.

So, a typical node in the doubly linked list node consists of three fields:

Data represents the data value stored in the node.
Previous represents a pointer that points to the previous node.
Next represents a pointer that points to next node in the list.

Doubly Linked List Representation:

As per the above illustration, the following are the important points to be considered.

Doubly Linked List contains a pointer element called head.
Each node carries a data and two pointer fields called next and prev.
Each node is linked with its next node using its next pointer.
Each node is linked with its previous node using its previous pointer.
The last node carries a pointer as null to mark the end of the list.

Doubly Linked List Implementation in Java:

Java Code

public class DoublyLinkedList {  

//Represent a node of the doubly linked list  

class Node{  
int data;  
Node previous;
Node next;  

public Node(int data) {  
            this.data = data;  
        }  
    }  
  
    //Represent the head and tail of the doubly linked list  
    Node head, tail = null;  
  
    //addNode() will add a node to the list  
    public void addNode(int data) {  
        //Create a new node  
        Node newNode = new Node(data);  
  
        //If list is empty  
        if(head == null) {  
            //Both head and tail will point to newNode  
            head = tail = newNode;  
            //head's previous will point to null  
            head.previous = null;  
            //tail's next will point to null, as it is the last node of the list  
            tail.next = null;  
        }  
        else {  
            //newNode will be added after tail such that tail's next will point 
            //to ne-wNode  
            tail.next = newNode;  
            //newNode's previous will point to tail  
            newNode.previous = tail;  
            //newNode will become new tail  
            tail = newNode;  
            //As it is last node, tail's next will point to null  
            tail.next = null;  
        }  
    }  
  
    //display() will print out the nodes of the list  
    public void display() {  
        //Node current will point to head  
        Node current = head;  
        if(head == null) {  
            System.out.println("List is empty");  
            return;  
        }  
        System.out.println("Nodes of doubly linked list: ");  
        while(current != null) {  
            //Prints each node by incrementing the pointer.  
  
            System.out.print(current.data + " ");  
            current = current.next;  
        }  
    }  
  
    public static void main(String[] args) {  
  
        DoublyLinkedList dList = new DoublyLinkedList();  
        //Add nodes to the list  
        dList.addNode(1);  
        dList.addNode(2);  
        dList.addNode(3);  
        dList.addNode(4);  
        dList.addNode(5);  
  
        //Displays the nodes present in the list  
        dList.display();  
    }  
  }

Output:

Nodes of doubly linked list:
1 2 3 4 5

Advantages of Doubly Linked List

A DLL can be traversed in both forward and backward direction.
The delete operation in DLL is more efficient if pointer to the node to be deleted is given.
We can quickly insert a new node before a given node.

Disadvantages of Doubly Linked List

Every node of DLL Require extra space for an previous pointer(This can be overcome by implementing XOR Linked list)
All operations require an extra pointer previous to be maintained

Time Complexity for doubly linked lists :

Operation	Time Complexity: Worst Case	Time Complexity: Average Case
Insert at beginning or end	O(1)	O(1)
Delete at beginning or end	O(1)	O(1)
Search	O(n)	O(n)
Access	O(n)	O(n)

Space Complexity: 0(1)

Special thanks to Ankit Kumar Das for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article