Doubly Linked list in Java

Doubly Linked List In Java

Doubly Linked List in Java is a mutated version of Linked List.

Similar to a Linked List Doubly Linked List also stores data elements of homogeneous data type in a linear format

Doubly Linked List in Java Example

Structure of a Doubly Linked List

The difference between a Linked List and a Doubly Linked is that singly linked list just has reference to the next node in the chain while doubly linked list has reference to both previous and next node in the chain

Components of doubly linked list are –

  • Data
  • Reference to the Next node
  • Reference to the Previous node

Doubly Linked List allows traversal in both forward and backward direction as for any node both previous and next nodes are known.

The first node is referred to as the head and the last node is referred to as the tail node.

Doubly Linked List in Java
// Node Class
class Node{
    int data;
    Node next, prev;

    Node(int x) // parameterized constructor
    {
        data = x;
        next = null; 
        prev = null;     
    }
}

Lorem ipsum dolor sit amet, consectetur adipiscing elit. Ut elit tellus, luctus nec ullamcorper mattis, pulvinar dapibus leo.

Advantages of Doubly Linked List

Merits of Doubly Linked List

  • A Doubly Linked List can be traversed in any given Direction Since it has pointers to both the next and the previous Node of the List.
  • It is easier to reverse a Doubly Linked List.
  • Both Deletion and Insertion and easier in a Doubly Linked List.
Disadvantages of Doubly Linked List

Demerits of Doubly Linked List

  • Every operation on a Doubly Linked List requires an extra step to perform calculations on that extra address stored with each node.
  • Every Node requires extra space in the memory to store that one extra address.

Operations on a Doubly Linked List

Following operations can be performed on a doubly linked list:-

  • Insertion
    • Insertion at the beginning.
    • Insertion at the end.
    • Insertion at a specific position.
  • Deletion
    • Deletion from the beginning.
    • Deletion from the end.
    • Deletion from a specific position.

In our examples, we will focus on insertion/deletion at beginning

Code for Adding a Node in Doubly Linked List

This method uses class instances to call functions.

Run
import java.lang.*;

class DoublyLinkedList {
    Node head;

    // Node Class
    class Node {
        int data;
        Node next, prev;

        Node(int x) // parameterized constructor
        {
            data = x;
            next = null;
            prev = null;
        }
    }

    // inserts at first position
    public void insertNode(int data) {
        // Creating newNode memory & assigning data value
        Node newNode = new Node(data);

        newNode.next = head;
        newNode.prev = null;

        // if DLL had already >=1 nodes
        if (head != null)
            head.prev = newNode;

        // changing head to this
        head = newNode;
        System.out.println(newNode.data + " inserted");
    }

    public void display() {
        Node node = head;
        Node end = null;
        //as linked list will end when Node reaches Null

        System.out.print("\nIn forward: ");
        while (node != null) {
            System.out.print(node.data + " ");
            end = node;
            node = node.next;
        }
        System.out.print("\nIn backward: ");

        while (end != null) {
            System.out.print(end.data + " ");
            end = end.prev;
        }
        System.out.println("\n");
    }

}
class Main{
    public static void main(String args[])
    {
        DoublyLinkedList dll = new DoublyLinkedList();

        dll.insertNode(26);
        dll.insertNode(25);
        dll.insertNode(24);

        dll.display();

        dll.insertNode(23);
        dll.insertNode(22);
        dll.insertNode(21);
        dll.insertNode(20);

        dll.display();
    }
}

Output

26 inserted
25 inserted
24 inserted

In forward: 24 25 26 
In backward: 26 25 24 

23 inserted
22 inserted
21 inserted
20 inserted

In forward: 20 21 22 23 24 25 26 
In backward: 26 25 24 23 22 21 20 

This method uses static methods to call functions.

Run
import java.lang.*;

// Node Class
class Node {
    int data;
    Node next, prev;

    Node(int x) // parameterized constructor
    {
        data = x;
        next = null;
        prev = null;
    }
}

class Main
{
    static Node insertNode(Node head, int data)
    {
        // Creating newNode memory & assigning data value
        Node newNode = new Node(data);

        newNode.next = head;
        newNode.prev = null;

        // if DLL had already >=1 nodes
        if(head !=null)
            head.prev = newNode;

        // changing head to this
        head = newNode;
        System.out.println(newNode.data + " inserted");

        return head;
    }


    static void display(Node node) {

        Node end = null;
        //as linked list will end when Node reaches Null

        System.out.print("\nIn forward: ");
        while(node!=null)
        {
            System.out.print(node.data + " ");
            end = node;
            node = node.next;
        }
        System.out.print("\nIn backward: ");

        while (end != null) {
            System.out.print(end.data + " ");
            end = end.prev;
        }
        System.out.println("\n");
    }

    public static void main(String args[])
    {
        Node head = null;
        head = insertNode(head,26);
        head = insertNode(head,25);
        head = insertNode(head,24);

        display(head);

        head = insertNode(head,23);
        head = insertNode(head,22);
        head = insertNode(head,21);
        head = insertNode(head,20);

        display(head);

    }
}

Output

26 inserted
25 inserted
24 inserted

In forward: 24 25 26 
In backward: 26 25 24 

23 inserted
22 inserted
21 inserted
20 inserted

In forward: 20 21 22 23 24 25 26 
In backward: 26 25 24 23 22 21 20 

Code for Deleting a Node in Doubly Linked List

Let us look at the code for deletion, we will for now focus on deletion from the start which is the default nature in a linked list. Which will require the following –

  • Checking if the doubly linked list is empty
    • No deletion possible
  • Checking if the doubly Linked list has a single node
    • Changing the head to null
  • Otherwise, moving the head node to next node and changing previous of new head to null

This method uses class instances to call functions.

Run
import java.lang.*;

class DoublyLinkedList {
    Node head;

    // Node Class
    class Node {
        int data;
        Node next, prev;

        Node(int x) // parameterized constructor
        {
            data = x;
            next = null;
            prev = null;
        }
    }

    // inserts at first position
    public void insertNode(int data) {
        // Creating newNode memory & assigning data value
        Node newNode = new Node(data);

        newNode.next = head;
        newNode.prev = null;

        // if DLL had already >=1 nodes
        if (head != null)
            head.prev = newNode;

        // changing head to this
        head = newNode;
    }

    public void deleteNode(){
        Node temp = head;

        // if DLL is empty
        if(head == null){
            System.out.println("Linked List Empty, nothing to delete");
            return;
        }

        // if Linked List has only 1 node
        if(temp.next == null){
            System.out.println(temp.data + " deleted");
            head = null;
            return;
        }

        // move head to next node
        head = head.next;
        // assign head node's previous to NULL
        head.prev = null;

        System.out.println(temp.data + " deleted");
    }

    public void display() {
        Node node = head;
        Node end = null;
        //as linked list will end when Node reaches Null

        System.out.print("\nIn forward: ");
        while (node != null) {
            System.out.print(node.data + " ");
            end = node;
            node = node.next;
        }
        System.out.print("\nIn backward: ");

        while (end != null) {
            System.out.print(end.data + " ");
            end = end.prev;
        }
        System.out.println("\n");
    }

}
class Main{
    public static void main(String args[])
    {
        DoublyLinkedList dll = new DoublyLinkedList();

        dll.insertNode(26);
        dll.insertNode(25);
        dll.insertNode(24);
        dll.insertNode(23);
        dll.insertNode(22);
        dll.insertNode(21);
        dll.insertNode(20);

        dll.display();

        dll.deleteNode();
        dll.deleteNode();
        dll.deleteNode();

        dll.display();

    }
}

Output

In forward: 20 21 22 23 24 25 26 
In backward: 26 25 24 23 22 21 20 

20 deleted
21 deleted
22 deleted

In forward: 23 24 25 26 
In backward: 26 25 24 23

This method uses static methods to call functions.

Run
import java.lang.*;

// Node Class
class Node {
    int data;
    Node next, prev;

    Node(int x) // parameterized constructor
    {
        data = x;
        next = null;
        prev = null;
    }
}

class Main
{
    // inserts a node at the first position
    static Node insertNode(Node head, int data)
    {
        // Creating newNode memory & assigning data value
        Node newNode = new Node(data);

        newNode.next = head;
        newNode.prev = null;

        // if DLL had already >=1 nodes
        if(head !=null)
            head.prev = newNode;

        // changing head to this
        head = newNode;
        return head;
    }

    // deletes the first node in doubly linked list
    public static Node deleteNode(Node head)
    {
        Node temp = head;

        // if DLL is empty
        if(head == null){
            System.out.println("Linked List Empty, nothing to delete");
            return head;
        }

        // if Linked List has only 1 node
        if(temp.next == null){
            System.out.println(temp.data + " deleted");
            head = null;
            return head;
        }

        // move head to next node
        head = head.next;
        // assign head node's previous to NULL
        head.prev = null;

        System.out.println(temp.data + " deleted");

        return head;
    }
    static void display(Node node) {

        Node end = null;
        //as linked list will end when Node reaches Null

        System.out.print("\nIn forward: ");
        while(node!=null)
        {
            System.out.print(node.data + " ");
            end = node;
            node = node.next;
        }
        System.out.print("\nIn backward: ");

        while (end != null) {
            System.out.print(end.data + " ");
            end = end.prev;
        }
        System.out.println("\n");
    }

    public static void main(String args[])
    {
        Node head = null;
        head = insertNode(head,26);
        head = insertNode(head,25);
        head = insertNode(head,24);
        head = insertNode(head,23);
        head = insertNode(head,22);
        head = insertNode(head,21);
        head = insertNode(head,20);

        display(head);

        head = deleteNode(head);
        head = deleteNode(head);
        head = deleteNode(head);

        display(head);

    }
}

Output

In forward: 20 21 22 23 24 25 26 
In backward: 26 25 24 23 22 21 20 

20 deleted
21 deleted
22 deleted

In forward: 23 24 25 26 
In backward: 26 25 24 23 
Quiz time

Fun Fact

Doubly Linked List in Real Life can be seen implemented in back and forward buttons in a browser navigation. Also the undo and redo buttons are a great example of application of Doubly Linked List.