Linked Lists

If arrays are the sprinters of data structures — fast, predictable, cache-friendly — then linked lists are the acrobats. They sacrifice sequential access speed for the ability to insert and remove elements anywhere in constant time, without shifting a single neighbor. This flexibility makes linked lists the backbone of many higher-level structures (LRU caches, adjacency lists, free lists in memory allocators) and a staple of technical interviews.

Linked list problems test your pointer manipulation skills under pressure. Lose track of a single reference and you corrupt the entire structure. The problems in this chapter train you to handle references with surgical precision.

Singly Linked List: Node Design in Java 25

A linked list node holds data and a reference to the next node. Java 25 records provide a compact, immutable way to express this — but since list operations require mutation, you will use a mutable class for the working implementation and save records for immutable scenarios.

// Mutable node for general linked list operations
public class ListNode<T> {
    T val;
    ListNode<T> next;

    ListNode(T val) {
        this.val = val;
        this.next = null;
    }

    ListNode(T val, ListNode<T> next) {
        this.val = val;
        this.next = next;
    }
}

For immutable linked lists (functional-style, useful in concurrent contexts), Java 25 records work beautifully:

// Immutable node using sealed interface + records
public sealed interface ImmutableList<T> {
    record Nil<T>() implements ImmutableList<T> {}
    record Cons<T>(T head, ImmutableList<T> tail) implements ImmutableList<T> {}
}

With pattern matching, you can process this list elegantly:

public static <T> int length(ImmutableList<T> list) {
    return switch (list) {
        case ImmutableList.Nil<T> _ -> 0;
        case ImmutableList.Cons<T>(var _, var tail) -> 1 + length(tail);
    };
}

This sealed hierarchy guarantees exhaustive pattern matching — the compiler verifies that you handle every case.

Basic Operations: Insert and Delete

Insert at Head — O(1)

public ListNode<T> insertAtHead(ListNode<T> head, T val) {
    var newNode = new ListNode<>(val);
    newNode.next = head;
    return newNode; // New head
}

No traversal needed. The new node points to the old head, and the new node becomes the head.

Insert at Tail — O(n) Without Tail Pointer

public ListNode<T> insertAtTail(ListNode<T> head, T val) {
    var newNode = new ListNode<>(val);
    if (head == null) return newNode;

    var current = head;
    while (current.next != null) {
        current = current.next;
    }
    current.next = newNode;
    return head;
}

You traverse the entire list to find the last node. Maintaining a tail pointer reduces this to O(1) — an optimization worth mentioning in interviews.

Delete a Node by Value — O(n)

public ListNode<T> delete(ListNode<T> head, T val) {
    if (head == null) return null;
    if (head.val.equals(val)) return head.next;

    var current = head;
    while (current.next != null) {
        if (current.next.val.equals(val)) {
            current.next = current.next.next;
            return head;
        }
        current = current.next;
    }
    return head;
}

The deletion logic requires tracking the predecessor of the target node, because you need to update the predecessor’s next pointer. This is where the dummy node technique (covered below) eliminates the special case for deleting the head.

Doubly Linked List: Bidirectional Traversal

A doubly linked list adds a prev pointer to each node. This enables O(1) deletion when you have a reference to the target node (no need to find the predecessor) and supports backward traversal.

public class DoublyLinkedNode<T> {
    T val;
    DoublyLinkedNode<T> prev;
    DoublyLinkedNode<T> next;

    DoublyLinkedNode(T val) {
        this.val = val;
    }
}

Sentinel Head and Tail Nodes

Production-quality doubly linked lists use sentinel nodes — dummy head and tail nodes that never hold real data. Sentinels eliminate null checks at the boundaries:

public class DoublyLinkedList<T> {
    private final DoublyLinkedNode<T> head; // Sentinel
    private final DoublyLinkedNode<T> tail; // Sentinel
    private int size;

    public DoublyLinkedList() {
        head = new DoublyLinkedNode<>(null);
        tail = new DoublyLinkedNode<>(null);
        head.next = tail;
        tail.prev = head;
        size = 0;
    }

    public void addFirst(T val) {
        var node = new DoublyLinkedNode<>(val);
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
        size++;
    }

    public void addLast(T val) {
        var node = new DoublyLinkedNode<>(val);
        node.prev = tail.prev;
        node.next = tail;
        tail.prev.next = node;
        tail.prev = node;
        size++;
    }

    public void remove(DoublyLinkedNode<T> node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
        size--;
    }
}

Notice how remove works without any null checks or edge cases. The sentinel nodes guarantee that node.prev and node.next are never null. This is the power of sentinels — they eliminate an entire category of bugs.

LRU cache implementations (a high-frequency interview question) rely on exactly this doubly linked list with sentinels, combined with a hash map for O(1) lookups.

Memory Comparison with Arrays

Aspect	Array	Singly Linked List	Doubly Linked List
Element overhead	0 bytes	8 bytes (one pointer)	16 bytes (two pointers)
Cache behavior	Excellent (sequential)	Poor (scattered)	Poor (scattered)
Memory allocation	One contiguous block	Per-node heap allocation	Per-node heap allocation
GC pressure	Low (one object)	High (n objects)	High (n objects)

In Java, each ListNode is a separate heap object with its own object header (typically 12–16 bytes). For an int-valued linked list, the overhead per element exceeds the data itself. This is why java.util.LinkedList is rarely the right choice for performance-sensitive Java code — and why interviewers probe whether you understand this trade-off.

Classic Problem: Cycle Detection — Floyd’s Tortoise and Hare

Problem: Given a linked list, determine if it contains a cycle. If it does, find the node where the cycle begins.

Floyd’s algorithm uses two pointers moving at different speeds:

public ListNode<Integer> detectCycle(ListNode<Integer> head) {
    var slow = head;
    var fast = head;

    // Phase 1: Detect whether a cycle exists
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;

        if (slow == fast) {
            // Cycle detected. Phase 2: Find the entry point.
            var entry = head;
            while (entry != slow) {
                entry = entry.next;
                slow = slow.next;
            }
            return entry; // Cycle starts here
        }
    }

    return null; // No cycle
}

Why Phase 2 works: When the fast pointer catches the slow pointer inside the cycle, the meeting point is a specific distance from the cycle’s entry. That distance equals the distance from the head to the cycle’s entry. Moving two pointers — one from the head, one from the meeting point — at the same speed guarantees they converge at the cycle’s entry.

Mathematical proof sketch: Let d be the distance from head to cycle entry, c be the cycle length, and k be the distance from cycle entry to the meeting point. When they meet, slow has traveled d + k steps, and fast has traveled 2(d + k) steps. The difference d + k is a multiple of c. Therefore d = mc - k for some integer m, meaning a pointer starting at the head and one at the meeting point will meet at the cycle entry after d steps.

Complexity: O(n) time, O(1) space. No hash sets, no marking.

Classic Problem: Reverse a Linked List

One of the most common interview questions across all companies. You need both the iterative and recursive approaches.

Iterative Reversal

public ListNode<Integer> reverseIterative(ListNode<Integer> head) {
    ListNode<Integer> prev = null;
    var current = head;

    while (current != null) {
        var nextTemp = current.next; // Save the next node
        current.next = prev;         // Reverse the link
        prev = current;              // Advance prev
        current = nextTemp;          // Advance current
    }

    return prev; // prev is the new head
}

The three-variable dance: At each step, you maintain three pointers: prev, current, and nextTemp. You reverse the current.next pointer to point backward, then slide all three pointers forward. After the loop, prev points to the last node processed — the new head.

Recursive Reversal

public ListNode<Integer> reverseRecursive(ListNode<Integer> head) {
    if (head == null || head.next == null) {
        return head;
    }

    var newHead = reverseRecursive(head.next);
    head.next.next = head; // The node after head now points back to head
    head.next = null;       // Remove the old forward pointer
    return newHead;
}

The recursion unwinds from the tail, and at each return, the node after head has already been reversed. You reverse the single link between head and head.next, then clear the forward pointer.

Complexity: Both approaches are O(n) time. Iterative uses O(1) space; recursive uses O(n) stack space.

Interviewers overwhelmingly prefer the iterative version. Demonstrate the recursive one only if asked, and mention the stack overflow risk on very long lists.

Classic Problem: Merge Two Sorted Lists

Problem: Given two sorted linked lists, merge them into one sorted list. Return the head of the merged list.

public ListNode<Integer> mergeTwoLists(ListNode<Integer> l1, ListNode<Integer> l2) {
    var dummy = new ListNode<>(0); // Sentinel to simplify logic
    var current = dummy;

    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) {
            current.next = l1;
            l1 = l1.next;
        } else {
            current.next = l2;
            l2 = l2.next;
        }
        current = current.next;
    }

    // Attach the remaining non-empty list
    current.next = (l1 != null) ? l1 : l2;

    return dummy.next; // Skip the sentinel
}

The dummy node technique shines here. Without it, you need separate logic to determine which list provides the first node of the merged result. The dummy node acts as a placeholder head — you build the merged list behind it, then return dummy.next.

Complexity: O(n + m) time, O(1) space (reuses existing nodes, no new allocations beyond the dummy).

Classic Problem: Find the Middle Node

Problem: Given a linked list, return the middle node. If the list has an even number of nodes, return the second middle node.

public ListNode<Integer> findMiddle(ListNode<Integer> head) {
    var slow = head;
    var fast = head;

    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }

    return slow;
}

When fast reaches the end, slow is at the midpoint. This two-speed pointer pattern is a building block — you use it inside merge sort on linked lists, palindrome checks, and other algorithms.

Classic Problem: Remove Nth Node from End

Problem: Remove the nth node from the end of a linked list in one pass.

public ListNode<Integer> removeNthFromEnd(ListNode<Integer> head, int n) {
    var dummy = new ListNode<>(0);
    dummy.next = head;
    var ahead = dummy;
    var behind = dummy;

    // Advance 'ahead' by n+1 steps to create the gap
    for (int i = 0; i <= n; i++) {
        ahead = ahead.next;
    }

    // Move both pointers until 'ahead' reaches the end
    while (ahead != null) {
        ahead = ahead.next;
        behind = behind.next;
    }

    // 'behind' is now one node before the target
    behind.next = behind.next.next;

    return dummy.next;
}

The gap technique: By advancing one pointer n + 1 steps ahead, you ensure that when it reaches null, the trailing pointer sits one node before the target. The dummy node handles the edge case where you need to remove the head itself.

Complexity: O(L) time where L is the list length, O(1) space. Truly single-pass.

The Dummy Node Technique

You have seen the dummy node in merge and remove-nth problems. It deserves explicit attention because it eliminates an entire class of bugs.

The problem it solves: When an operation can modify the head of the list (insertion at the front, deletion of the head), you need special-case logic to update the head reference. This creates branching code that is easy to get wrong under interview pressure.

The solution: Create a dummy node whose next points to the real head. Perform all operations relative to the dummy. Return dummy.next as the new head.

Rule of thumb: If a linked list problem involves potential head modification, start with a dummy node. It costs one extra object allocation and saves you from multiple conditional branches.

Operations Complexity Table

Operation	Singly Linked	Doubly Linked	Notes
Access by index	O(n)	O(n)	Must traverse from head
Search	O(n)	O(n)	Sequential scan
Insert at head	O(1)	O(1)	Update head pointer
Insert at tail	O(n) / O(1)*	O(1)	*O(1) with tail pointer
Insert after node	O(1)	O(1)	Given reference to node
Delete head	O(1)	O(1)	Update head pointer
Delete tail	O(n)	O(1)	Singly linked must find predecessor
Delete given node	O(n) / O(1)†	O(1)	†If you can copy successor’s data
Reverse	O(n)	O(n)	Full traversal required

Edge Cases and Interviewer Tips

Edge cases to test:

• Empty list (null head) — Every function should handle this without throwing.
• Single node — Reversal should return the same node. Cycle detection should return null.
• Two nodes — The minimum size where pointer manipulation becomes non-trivial.
• Cycle at the head — The last node points back to the head.
• Cycle at the tail — The last node points to a middle node.

Interviewer tips:

• Always clarify: “Is the list singly or doubly linked?” This changes your approach.
• Draw the pointer state before and after each operation. Visual reasoning prevents bugs.
• Mention the dummy node technique proactively — it shows you have a systematic approach to edge cases.
• If asked about java.util.LinkedList, note that it is a doubly linked list with sentinel nodes, and that ArrayList outperforms it for nearly all common operations due to cache locality.

Linked lists test your ability to think in references rather than indices. The patterns in this chapter — fast-slow pointers, iterative reversal, dummy nodes, and the gap technique — recur across dozens of interview variations. Drill them until the pointer manipulations feel as natural as array indexing. Next, you shift to a restricted version of the linked list that unlocks a powerful class of problems: the stack.