Linked Lists

“Reverse a linked list” is the single most-asked warm-up question in Indian product-company interviews — not because anyone reverses lists at work, but because it exposes in 90 seconds whether you can hold three pointers in your head without dropping one. This module is about that skill: pointer discipline. And the one place linked lists genuinely run in production — the LRU cache inside Redis — is built from exactly the moves you learn here.

The Goal

By the end of this module you can:

• Explain what a node really is — an object on the heap holding a value and a reference — and draw it
• Implement a ListNode class and basic list operations in Java from scratch, no library
• Reverse a list with the prev/curr/next dance, narrating every pointer move out loud
• Solve middle-of-list and cycle-detection with fast/slow pointers, and explain WHY Floyd’s algorithm must work
• Use a dummy head node to delete every edge-case if from insert/delete code
• Explain honestly when arrays beat lists and why real Java code almost always uses ArrayList

The Lesson

A node is just an object on the heap

You already have the mental picture from how Java runs: frames on the stack, objects on the heap, arrows between them. A linked list is nothing new — it’s heap objects pointing at each other.

flowchart LR
    S["head reference on the stack"] --> A["Node val 10"]
    A --> B["Node val 20"]
    B --> C["Node val 30"]
    C --> N["null"]

Each node is one object holding two things: a value, and a reference to the next node. The last node’s next is null. The variable head in your method is just an arrow into the heap — lose that arrow and the whole chain is garbage-collected out from under you. That single fact causes most linked-list bugs.

Build ListNode from scratch

There is no magic. The entire data structure is this:

public class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(10);       // one object on the heap
        head.next = new ListNode(20);           // second object, first one points at it
        head.next.next = new ListNode(30);      // chain of arrows

        ListNode curr = head;                   // walking = following arrows
        while (curr != null) {
            System.out.print(curr.val + " -> ");
            curr = curr.next;
        }
        System.out.println("null");
    }
}

Run it. 10 -> 20 -> 30 -> null. That while (curr != null) walk is the heartbeat of every linked-list problem — you will type it a hundred times this week.

In JS terms: { val: 10, next: { val: 20, next: null } } — objects holding references to objects.

Arrays vs linked lists — the honest version

Now the honesty. That table makes linked lists look competitive. In practice, on real hardware, ArrayList wins almost everything — contiguous memory means the CPU cache pre-loads your next elements for free, while a linked list’s scattered nodes cause a cache miss on nearly every hop. That cache-locality gap is so large that even “linked list should win” workloads often lose.

So why learn this at all? Two reasons. One: interviews use linked lists as a pointer-discipline test — can you mutate a structure through references without losing pieces of it? Two: the idea of chained nodes runs inside real systems (LRU caches, allocators, undo stacks) even when nobody types new ListNode. In your actual Java job, you’ll reach for ArrayList by default — and you’ll understand exactly what you’re trading.

Core move 1 — reversal (the prev/curr/next dance)

The classic. You walk the list once and flip every arrow to point backwards.

static ListNode reverse(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    while (curr != null) {
        ListNode next = curr.next;   // 1. save the rest of the list FIRST
        curr.next = prev;            // 2. flip this arrow backwards
        prev = curr;                 // 3. drag prev forward
        curr = next;                 // 4. drag curr forward
    }
    return prev;                     // curr fell off the end; prev is the new head
}

Walk it pointer by pointer on 10 -> 20 -> 30:

Return prev (node 30). The list is 30 -> 20 -> 10 -> null. Line 1 inside the loop is sacred: save next before you touch curr.next, or steps 2 onward have nothing left to walk. This exact dance is what the visualizer below animates.

Core move 2 — fast/slow pointers

Two runners on the same track. slow moves one node per step, fast moves two.

static ListNode middle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;                     // when fast hits the end, slow is at the middle
}

When fast reaches the end, slow has covered exactly half the distance — the middle, in one pass, without ever counting the length.

Same trick detects a cycle (Floyd’s algorithm):

static boolean hasCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;   // same OBJECT, not same value
    }
    return false;                        // fast found a null - no loop exists
}

The WHY, because interviewers ask: if there’s no cycle, fast hits null and you’re done. If there IS a cycle, both runners eventually enter it and circle forever. Inside the loop, fast gains exactly one node on slow every step — so the gap between them shrinks by one each step, and a shrinking gap must hit zero. The fast runner must lap the slow one. No lapping is possible without a loop; a loop makes lapping inevitable.

Note the check slow == fast compares references — are these the same heap object — exactly the stack/heap arrow picture again.

Core move 3 — the dummy head node

Insert or delete at the head of a list and your code sprouts special cases: “if the list is empty…”, “if it’s the first node…”. The dummy head kills all of them — one fake node parked in front, so every real node has a predecessor.

static ListNode deleteValue(ListNode head, int target) {
    ListNode dummy = new ListNode(-1);   // fake node in front of the real head
    dummy.next = head;
    ListNode curr = dummy;
    while (curr.next != null) {
        if (curr.next.val == target) {
            curr.next = curr.next.next;  // unlink - works even when target is the head
        } else {
            curr = curr.next;
        }
    }
    return dummy.next;                   // the real head, whatever it is now
}

No if (head == null), no “is it the first node” branch. Deleting the head is now the same code as deleting any node. Any time a problem inserts or deletes near the front, reach for a dummy.

Merge two sorted lists

Dummy head’s signature use. You’re zipping two sorted chains into one:

static ListNode merge(ListNode a, ListNode b) {
    ListNode dummy = new ListNode(-1);
    ListNode tail = dummy;
    while (a != null && b != null) {
        if (a.val <= b.val) { tail.next = a; a = a.next; }
        else                { tail.next = b; b = b.next; }
        tail = tail.next;
    }
    tail.next = (a != null) ? a : b;     // one list ran dry - attach the rest of the other
    return dummy.next;
}

No nodes created (besides the dummy), no values copied — you’re just rewiring arrows. O(n + m) time, O(1) extra space. This is also the beating heart of merge sort.

The classic traps

Brute-force comparison, so the win is on record: detecting a cycle naively means storing every visited node in a HashSet — O(n) extra memory. Floyd’s does it with two pointers — O(1). Finding the middle naively means walking once to count, then walking again — fast/slow does it in one pass.

See It Move

Watch the three arrows — prev, curr, next — and how exactly one list arrow flips per step. This is the reversal dance from above, animated.

Step through it and notice:

• next is always saved before the arrow flips — pause at that moment; everything right of curr hangs off next alone
• After each flip there are briefly two chains: the reversed part behind prev, the untouched part ahead of next
• When curr hits null the loop is over, and prev — not head — is standing on the new front
• Run it twice narrating each pointer move out loud; if you can narrate it, you can code it cold

Spot The Pattern

Where It Runs In Real Life

LRU caches — this is how Redis evicts. The famous one. An LRU cache pairs a HashMap (O(1) “do we have this key?”) with a doubly linked list ordered by recency. On every access, unlink the node and splice it to the front — two arrow rewires, O(1). When memory is full, evict the back node. Redis’s approximated-LRU eviction and Java’s own LinkedHashMap (access-order mode) are built on exactly this. “Design an LRU cache” is a top-five interview question at fintech and product companies for this reason.

Undo history. Every editor keeps your actions as a chain of states — undo walks one arrow back, redo walks forward, and a new edit after undo snips the forward chain off. Linked structure, because you only ever move to a neighbor and splice.

Music players and job queues. A playlist where you can drag a song from position 40 to position 2 is a splice — O(1) once you hold the node, versus shifting 38 array slots. Same shape inside OS schedulers and message queues that constantly insert and remove at known positions.

The free-list inside memory allocators. When a program frees memory, allocators (like the one under malloc, and inside the JVM’s own native layers) thread the freed blocks into a linked list — each free block stores a pointer to the next free block inside itself. Allocation pops the head. Zero extra memory to manage memory: the chain lives in the gaps.

Build This

You’re building ListLab — your own list with reversal, middle, and a cycle you create on purpose.

1. Create ListLab.java and type this (don’t paste):

public class ListLab {

    static class Node {
        int val;
        Node next;
        Node(int val) { this.val = val; }
    }

    static Node fromArray(int[] vals) {
        Node dummy = new Node(-1);
        Node tail = dummy;
        for (int v : vals) {
            tail.next = new Node(v);
            tail = tail.next;
        }
        return dummy.next;
    }

    static void print(Node head) {
        for (Node c = head; c != null; c = c.next) System.out.print(c.val + " -> ");
        System.out.println("null");
    }

    static Node reverse(Node head) {
        Node prev = null, curr = head;
        while (curr != null) {
            Node next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }

    static Node middle(Node head) {
        Node slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    static boolean hasCycle(Node head) {
        Node slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) return true;
        }
        return false;
    }

    public static void main(String[] args) {
        Node head = fromArray(new int[]{10, 20, 30, 40, 50});
        print(head);
        System.out.println("middle: " + middle(head).val);
        head = reverse(head);
        print(head);
        System.out.println("cycle: " + hasCycle(head));
    }
}

2. Compile and run: javac ListLab.java then java ListLab. You should see the list, middle 30, the reversed list, and cycle: false.

3. Break it — lose the list. In reverse, move Node next = curr.next; to AFTER curr.next = prev;. Recompile, run. The output list is one node long — you flipped the first arrow before saving the rest, and the chain behind it became unreachable. Stare at this; it’s the number-one linked-list bug. Fix it back.

4. Break it — build a real cycle. In main, after creating the list, walk to the tail and wire it back: find the last node with a loop and set tail.next = head.next;. Call hasCycle — it prints true. Now call print on it and watch it run forever (Ctrl+C to kill it). That infinite print is exactly what an undetected cycle does to production code. Remove the wiring.

5. Extend it. Add merge(Node a, Node b) using the dummy-head template from the lesson, build two sorted lists in main, merge, print. Then add removeValue(Node head, int target) with a dummy head and prove it can delete the first node without a special case.

Problems To Solve

The rule: solve until you can write the reversal and dummy-head templates from memory. If stuck 25 minutes, read the approach, close it, re-solve from scratch.

Check Yourself

1. What two things does a node hold, and where in memory does the node itself live?
2. In the reversal loop, why must next = curr.next happen before curr.next = prev?
3. Reversal finishes when curr is null. Which variable is the new head, and why?
4. Why must Floyd’s fast pointer eventually land on the slow pointer if a cycle exists?
5. Why does hasCycle compare slow == fast instead of slow.val == fast.val?
6. What problem does a dummy head node solve, in one sentence?
7. A linked list inserts at the front in O(1) and an ArrayList takes O(n) — so why does ArrayList still win most real benchmarks?
8. Which two structures combine to make an LRU cache, and what does each contribute?

Explain it out loud: Draw 10 -> 20 -> 30 as boxes and arrows on paper, then reverse it by re-drawing one arrow per step while narrating prev, curr, and next at each move — as if teaching someone who has never seen a pointer. If you hesitate on which arrow flips, redo the See It Move section.

Still Unclear?

Copy-paste any of these into Claude — they deepen understanding, they don’t solve for you:

I'm learning linked lists in Java. Don't write code. I'll describe the reversal
loop from memory step by step, and you stop me at the FIRST wrong pointer move,
tell me which node just became unreachable, and make me restate that step.

Explain why Floyd's cycle detection cannot fail: walk me through the gap-shrinks-
by-one argument, then give me a list with a cycle starting at node 3 and make me
trace slow and fast positions by hand until they meet. Check my trace.

I know linked lists beat arrays on paper for insertions, but everyone says use
ArrayList in real Java. Explain CPU cache locality to a beginner, and where the
linked-list IDEA still wins in real systems even when the class itself loses.

Why AI Can’t Do This For You

AI writes a flawless reverse() in one second. But the interviewer isn’t buying code — they’re watching whether you can hold three moving references in your head and narrate them without dropping the chain. That’s done live, marker in hand, with no autocomplete. Pointer discipline is a performance skill, and performance skills only come from reps.

And in production, the bug is never “reverse a list.” It’s a reference someone overwrote two services away, a cache that evicts the wrong entry, an object graph with an accidental cycle that hangs serialization. AI can’t see your heap. The engineer who has burned in the boxes-and-arrows picture reads those bugs straight off the symptoms.

Module done? Add it to today’s tracker