Doubly Linked List Operations

A doubly linked list node contains:

• An integer data
• A next pointer to the next node
• A prev pointer to the previous node

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

    // Full constructor
    public Node(int data, Node next, Node prev) {
        this.data = data;
        this.next = next;
        this.prev = prev;
    }

    // Constructor for creating a standalone node (e.g., the last or only node)
    public Node(int data) {
        this(data, null, null);
    }
}

The LinkedList class itself is just a thin wrapper — the operations below are built around the Node structure above.

Inserting Before the Head

Given the head of a doubly linked list and a value, insert a new node before the current head. The new node becomes the new head.

1. Create a new node with the given value.
2. Set its next to point to the current head.
3. Update the prev of the current head to point to the new node.
4. Return the new node as the new head.

public Node insertBeforeHead(Node head, int val) {
    Node newHead = new Node(val, head, null);
    if (head != null) {
        head.prev = newHead;
    }
    return newHead;
}

Inserting Before the Tail

Given the head of a doubly linked list, insert a new node just before the tail.

1. Traverse the list to find the tail (the last node).
2. Identify the penultimate node (tail.prev).
3. Create a new node, with its next pointing to the tail and its prev pointing to the penultimate node.
4. Update the tail’s prev and the penultimate node’s next to link to the new node.

public Node insertBeforeTail(Node head, int val) {
    if (head == null || head.next == null) {
        // List is empty or has only one node; inserting before tail is same as inserting before head
        return insertBeforeHead(head, val);
    }

    Node current = head;
    while (current.next != null) {
        current = current.next;
    }

    Node tail = current;
    Node penultimate = tail.prev;

    Node newNode = new Node(val, tail, penultimate);
    penultimate.next = newNode;
    tail.prev = newNode;

    return head;
}

Deleting the Last Node

Given the head of a doubly linked list, delete the last node (the tail).

1. If the list is empty (head == null), return null.
2. If the list contains only one node, deleting it makes the list empty — return null.
3. Traverse the list to find the last node (tail).
4. Identify the second-last node (tail.prev).
5. Set the second-last node’s next to null, removing the tail.
6. Disconnect tail.prev to break the backward reference.
7. Return head (which may or may not have changed).

public Node deleteTail(Node head) {
    if (head == null) return null; // Empty list
    if (head.next == null) return null; // Only one node

    Node current = head;
    while (current.next != null) {
        current = current.next;
    }

    Node tail = current;
    Node penultimate = tail.prev;

    penultimate.next = null;
    tail.prev = null; // Optional: helps with garbage collection

    return head;
}

Reversing the List

Given the head of a doubly linked list, reverse it in place so the head becomes the tail and vice versa.

1. If the list is empty or has only one node, it’s already reversed — return the same head.
2. Initialize current to the head and prev to null.
3. Traverse the list, swapping each node’s next and prev, and moving current forward by following the new prev pointer (which was originally next).
4. After traversal, prev holds the last node visited; its prev field (the old next of the last node) points to the new head.
5. Return prev.prev as the new head.

public Node reverse(Node head) {
    if (head == null || head.next == null) return head;

    Node current = head;
    Node prev = null;

    while (current != null) {
        // Store original prev
        prev = current.prev;

        // Swap next and prev pointers
        current.prev = current.next;
        current.next = prev;

        // Move to the next node (which is current.prev after the swap)
        current = current.prev;
    }

    // After the loop, prev holds the last node we visited
    // Its prev is the new head
    return prev.prev;
}

Reversing the List (Brute Force)

Reverse a doubly linked list without modifying the links, by only changing the data values.

1. If the list is empty or has only one node, it’s already reversed — return the same head.
2. Initialize current to the head and a Stack<Integer> to hold values.
3. Traverse the list once, pushing every node’s data onto the stack.
4. Re-initialize current to the head.
5. Traverse again, popping a value off the stack and assigning it to current.data each time.
6. Return the head — the structure is unchanged, but the data values are reversed.

public Node reverseBruteForce(Node head) {
    if (head == null || head.next == null) return head;

    Stack<Integer> stack = new Stack<>();
    Node current = head;

    // First pass: push all data into the stack
    while (current != null) {
        stack.push(current.data);
        current = current.next;
    }

    // Second pass: replace node data with values from the stack
    current = head;
    while (current != null) {
        current.data = stack.pop();
        current = current.next;
    }

    return head;
}