Doubly Linked List

A Doubly Linked List is a more complex variation of a linked list in which each node contains a reference to both the next node and the previous node in the sequence.

Node Structure

Advantages

• Allows traversal in both directions (forward and backward).
• Deletion of a given node in O(1) if a pointer to the node is given (unlike singly linked list where you need the previous node).

Implementation in Java

public class DoublyLinkedList {

    class Node {
        int data;
        Node prev;
        Node next;

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

    private Node head, tail;

    public void add(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = tail = newNode;
            return;
        }
        tail.next = newNode;
        newNode.prev = tail;
        tail = newNode;
    }

    public void displayForward() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " <-> ");
            current = current.next;
        }
        System.out.println("null");
    }
    
    public void displayBackward() {
        Node current = tail;
        while (current != null) {
            System.out.print(current.data + " <-> ");
            current = current.prev;
        }
        System.out.println("null");
    }

    public static void main(String[] args) {
        DoublyLinkedList dll = new DoublyLinkedList();
        dll.add(10);
        dll.add(20);
        dll.add(30);

        dll.displayForward();  // 10 <-> 20 <-> 30 <-> null
        dll.displayBackward(); // 30 <-> 20 <-> 10 <-> null
    }
}