Doubly Linked List in Java | Full Example Code & Explanation

Doubly Linked List in Java – Full Example with Step-by-Step Explanation

Introduction

A Doubly Linked List (DLL) allows navigation forward and backward. Each node has data, a prev pointer to the previous node, and a next pointer to the next node. This makes insertion and deletion faster than Singly Linked List in the middle of the list.

Java Code with Step-by-Step Explanation

// Node class for DLL
class Node {
    int data;   // Stores node value
    Node prev;  // Reference to previous node
    Node next;  // Reference to next node

    Node(int data) { // Constructor
        this.data = data;
        this.prev = null;
        this.next = null;
    }
}
    

Step: We define the node structure. Each node knows its data, prev and next.

// DLL class
class DoublyLinkedList {
    Node head; // start of the list

    // Insert at end
    public void insertAtEnd(int data) {
        Node newNode = new Node(data); // Create new node

        if(head == null){ 
            head = newNode; // First node becomes head
            return;
        }

        Node temp = head;
        while(temp.next != null){ // Traverse to last node
            temp = temp.next;
        }
        temp.next = newNode; // Link last node to new
        newNode.prev = temp; // Link new node back
    }

    // Insert at beginning
    public void insertAtBeginning(int data) {
        Node newNode = new Node(data);
        if(head == null){
            head = newNode;
            return;
        }
        newNode.next = head; // New node points to current head
        head.prev = newNode; // Head points back to new node
        head = newNode;      // Update head
    }

    // Display forward
    public void displayForward() {
        Node temp = head;
        System.out.print("Forward: ");
        while(temp != null){
            System.out.print(temp.data + " ");
            temp = temp.next;
        }
        System.out.println();
    }

    // Display backward
    public void displayBackward() {
        if(head == null) return;
        Node temp = head;
        while(temp.next != null){ // Move to last node
            temp = temp.next;
        }
        System.out.print("Backward: ");
        while(temp != null){
            System.out.print(temp.data + " ");
            temp = temp.prev;
        }
        System.out.println();
    }
}
    

Step: We create a DLL class with methods to insert at the beginning and end. Display methods show the list forward and backward. Each line of code is commented above.

// Main class to test DLL
public class Main {
    public static void main(String[] args){
        DoublyLinkedList dll = new DoublyLinkedList();

        dll.insertAtEnd(10);       // Insert 10 at end
        dll.insertAtEnd(20);       // Insert 20 at end
        dll.insertAtBeginning(5);  // Insert 5 at start
        dll.insertAtEnd(30);       // Insert 30 at end

        dll.displayForward();      // Output: 5 10 20 30
        dll.displayBackward();     // Output: 30 20 10 5
    }
}
    

Step: We test the DLL. Insertions are done at start and end. Forward and backward displays show correct traversal. You can delete nodes similarly using the logic described above.

Conclusion

The Doubly Linked List allows efficient forward and backward traversal. It uses extra memory for prev but makes operations like insertion, deletion, and reverse traversal much easier than Singly Linked List. Next, we will learn about Circular Linked List.

← Previous: Singly Linked List Next: Circular Linked List →