Linked Lists Explained: Nodes, Pointers, In-Place Reversal, and Floyd's Cycle Detection

You’re four articles deep into some late-night rabbit hole. You tap the back button — the previous page snaps in. Tap again — the one before that. Tap forward — you glide back the way you came. Your browser never renumbered those pages or packed them into a neat row. It just kept each page holding a small arrow to the one before it and the one after it, so back and forward are each a single hop, no matter how deep you’ve wandered.

That chain of pages, each holding an arrow to its neighbours, is a linked list — and because it remembers both directions, it’s a doubly linked one. By the end of this article you and I will have built one together, reversed it in place, and caught it chasing its own tail — and you’ll know exactly why some jobs it finishes in a single step while others make it walk the whole way there.

Let's start nowhere near a computer

I stick a folded note on your fridge. It doesn’t hold the prize — it holds one line: “look in the mailbox.” You walk out to the mailbox and find another note: “under the doormat.” Under the doormat: “the old oak in the yard — dig here.” You dig, and there’s the treasure.

Three things about that hunt are the entire data structure:

1. Each clue knows only the next spot. There’s no master map, no list of all locations. The fridge note has never heard of the oak tree.
2. You cannot skip to clue three. To reach the oak you must pass through the mailbox and the doormat, in order. There’s no way to jump straight to the end.
3. The spots are scattered. Fridge, mailbox, doormat, yard — nowhere near each other. It doesn’t matter one bit: the notes hold the hunt together, not the geography.

Now contrast that with a row of numbered lockers. To open locker 3 you walk straight to it — you don’t open lockers 1 and 2 first. That’s the difference between a linked list and an array in one image: the array has house numbers; the linked list has clues.

Here’s the same shape as a train. Each carriage is coupled to the next. To walk from the engine to carriage eight you pass through one to seven — reaching a spot is a stroll. But to add a carriage between four and five, the yard crew unclips one coupling and clips two new ones; every other carriage stays exactly where it is. Splicing is cheap; reaching a position is a walk. Hold on to that sentence — it’s the whole trade.

The same idea, all over your day

Once you see the treasure hunt, you spot the chain everywhere:

• Undo and redo. Ctrl+Z hops to the previous document state, Ctrl+Y to the next — a doubly linked chain of snapshots.
• Your music queue. Next track and previous track are one hop each in either direction.
• A blockchain. Every block stores the previous block’s hash, so it’s literally a linked list you can’t reorder without rebuilding everything after the change — which is exactly the point of it.
• Inside the standard library. ArrayDeque and LinkedList back your queues and stacks, and a hash map resolves collisions by chaining entries into tiny linked lists inside each bucket.

But the place that really rewards understanding the chain is the humble LRU cache: a doubly linked list glued to a hash map, so the moment you touch an item it can be yanked to the front in a single hop. We’ll build to exactly that trick — and there’s a whole thread-safe LRU cache walkthrough waiting once this clicks.

What a linked list actually looks like

Let’s store three values — 7, 3, 9 — and draw them the way the machine actually holds them.

Read it left to right. A head reference points at the first node. Each node is two things: a value, and a next pointer aimed at the following node. The last node’s next is null — the end of the line. That is the entire singly linked list; there is nothing else to it.

A doubly linked node adds exactly one pointer, prev, aimed backward. That single extra arrow is the only structural difference between singly and doubly linked — but it’s what makes back as cheap as forward, and what lets you delete a node you’re standing on without first hunting down the one before it.

Let's build one, step by step

We’ll assemble it in small pieces and finish with a complete, tested class you could whiteboard from memory.

Step 1: the node

Every box in that diagram needs its value and its outgoing pointer(s). That’s the whole node.

// singly linked: a value and a pointer to the next node
static final class Node {
    int value;
    Node next;
}
 
// doubly linked: one more pointer, aimed backward
static final class DNode {
    int value;
    DNode prev;
    DNode next;
}

Here’s the part beginners skip: a node has no idea what index it is, how long the list is, or where it sits in memory. It knows one neighbour (singly) or two (doubly), full stop. Everything a linked list can do is built from that tiny amount of knowledge — which is exactly why the next step hurts.

Step 2: no random access — the price of scattered nodes

This is the trade that defines the structure. Line the same six values up two ways.

An array is one contiguous block, so the index is an address: arr[3] sits at base + 3 × elementSize, one multiply-and-add away. That’s O(1) random access — reach any slot in a single step.

A linked list puts its nodes wherever the allocator happened to have room — scattered across the heap, joined only by pointers. There is no arithmetic that jumps to “the fourth node,” because the fourth node could be anywhere. The only way to reach it is to start at head and follow next four times. That’s O(n), and it isn’t a bug — it’s the direct, unavoidable cost of giving up the contiguous block.

So why would anyone give it up? Because of the flip side, which is the next step.

Step 3: splicing — rewire two pointers, in the right order

Reaching a node is the slow part. Once you’re holding one, inserting or deleting next to it is a couple of pointer assignments — no shifting a million elements, no copying. To slip a new node X in after A (which currently points at B), you rewire two links. But the order matters, and getting it wrong is the classic first bug.

If you point A.next at X first, you’ve just overwritten the only reference to B — and everything from B onward floats off, unreachable. The garbage collector eats the rest of your list. The fix is to save the successor before you clobber it: point X.next at B first, then repoint A.next at X.

// ✗ WRONG: overwrite A.next first, and B is already lost
a.next = x;      // the only pointer to B is gone
x.next = a.next; // a.next is x now, so X points at itself — B leaked
 
// ✓ RIGHT: read A.next into X before overwriting it
x.next = a.next; // X points at B  (A.next still holds B here)
a.next = x;      // now A points at X

Deletion is the mirror image: to remove B, point A.next straight past it at B.next. And here’s where the extra pointer earns its keep — in a doubly linked list you don’t even need to know A, because the node carries its own prev:

node.prev.next = node.next; // the one before now skips over node
node.next.prev = node.prev; // the one after now points back past it

Two lines, O(1), and you never had to search for the previous node. That’s the whole reason back is as cheap as forward.

Step 4: the sentinel trick — delete the edge cases, literally

Try to write removeFirst on a bare list and you’ll immediately trip over the ends. Remove the only node? You must set head to null. Remove the head? You must reassign head to the second node. Empty list? Half your pointers are null and every method needs a guard. The ends are special, and special cases are where bugs breed.

The fix is almost cheeky: add two permanent nodes that never hold data — a HEAD sentinel before the first real node and a TAIL sentinel after the last. Now the list is never empty (it always has its two guards), every real node always has a real node on both sides, and there is no head variable to reassign. Adding to the front becomes “splice after HEAD.” Removing the last real node becomes “unhook TAIL.prev.” Every operation collapses into the same two-line splice, with zero null checks.

private void insertBetween(E value, Node<E> before, Node<E> after) {
    Node<E> node = new Node<>(value);
    node.prev = before;
    node.next = after;
    before.next = node;
    after.prev = node;
}
// addFirst(v)  ==  insertBetween(v, head, head.next)
// addLast(v)   ==  insertBetween(v, tail.prev, tail)

How fast is this, really?

Line the doubly linked list up against its obvious rival, the dynamic array (ArrayList), and the picture is not “one is better” — it’s “they’re good at opposite things.”

Read the “held node” row twice, because it hides the catch. The O(1) splice is only O(1) if something already handed you the node. If you have to search for it first, you’ve paid O(n) to get there and the splice’s speed was moot. So a linked list wins precisely when another structure hands you the node for free — an iterator parked on it, or a hash map pointing straight at it (again, the LRU cache).

And there’s a quieter cost the big-O column can’t show. Those scattered nodes are murder on the CPU cache: walking a linked list is a series of unpredictable jumps all over the heap, while scanning an array marches through contiguous memory the prefetcher loves. Two structures can share an O(n) and still differ by 10× in wall-clock, and this is why — in practice, an array’s scan often beats a list’s even when their complexity is identical. Reach for a linked list for its O(1) splices, not to “make traversal faster.”

The complete implementation

Everything above, assembled into one class with sentinels doing the heavy lifting.

package dev.fiveyear.linkedlist;
 
import java.util.ArrayList;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.Objects;
 
public final class DoublyLinkedList<E> {
 
    private static final class Node<E> {
        E value;
        Node<E> prev;
        Node<E> next;
 
        Node(E value) {
            this.value = value;
        }
    }
 
    private final Node<E> head = new Node<>(null); // sentinel — never holds data
    private final Node<E> tail = new Node<>(null); // sentinel — never holds data
    private int size;
 
    public DoublyLinkedList() {
        head.next = tail;
        tail.prev = head;
    }
 
    public int size() {
        return size;
    }
 
    public boolean isEmpty() {
        return size == 0;
    }
 
    /** Splice a new value between two already-adjacent nodes. O(1). */
    private void insertBetween(E value, Node<E> before, Node<E> after) {
        Node<E> node = new Node<>(value);
        node.prev = before;
        node.next = after;
        before.next = node;
        after.prev = node;
        size++;
    }
 
    /** Add to the front — a splice just after the head sentinel. O(1). */
    public void addFirst(E value) {
        insertBetween(value, head, head.next);
    }
 
    /** Add to the back — a splice just before the tail sentinel. O(1). */
    public void addLast(E value) {
        insertBetween(value, tail.prev, tail);
    }
 
    /** Unhook a real node from its two neighbours. O(1). */
    private E unlink(Node<E> node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
        node.prev = null;
        node.next = null;
        size--;
        return node.value;
    }
 
    public E removeFirst() {
        if (isEmpty()) {
            throw new NoSuchElementException("empty list");
        }
        return unlink(head.next);
    }
 
    public E removeLast() {
        if (isEmpty()) {
            throw new NoSuchElementException("empty list");
        }
        return unlink(tail.prev);
    }
 
    /** Remove the first node whose value matches. O(n) to find, O(1) to splice. */
    public boolean remove(E value) {
        for (Node<E> n = head.next; n != tail; n = n.next) {
            if (Objects.equals(n.value, value)) {
                unlink(n);
                return true;
            }
        }
        return false;
    }
 
    public List<E> toList() {
        List<E> out = new ArrayList<>(size);
        for (Node<E> n = head.next; n != tail; n = n.next) {
            out.add(n.value);
        }
        return out;
    }
}

And here it is doing the things we drew:

DoublyLinkedList<String> list = new DoublyLinkedList<>();
list.addLast("b");
list.addFirst("a");
list.addLast("c");
list.toList();       // [a, b, c]
 
list.removeFirst();  // returns "a"
list.removeLast();   // returns "c"
list.toList();       // [b]
 
list.addFirst("x");
list.addLast("y");   // x, b, y
list.remove("b");    // true  — unhooks the middle node in O(1)
list.toList();       // [x, y]

That’s the sturdy, boring, correct list. Now for the two moves that make linked lists fun — and that show up in interviews constantly.

Reversing a list in place

You can’t reverse a linked list the way you’d reverse an array, swapping the ends inward — there are no indices to swap. All you can do is walk it once and flip each next pointer to face the other way. The catch: the instant you flip a node’s next, you’ve destroyed your only route forward. So you save the route before you flip.

That takes three pointers walking together: prev (the part already reversed, behind you), curr (the node you’re flipping right now), and ahead (the saved rest, so you never lose the way forward).

public static Node reverse(Node head) {
    Node prev = null;
    Node curr = head;
    while (curr != null) {
        Node ahead = curr.next; // remember the rest before we overwrite the link
        curr.next = prev;       // flip this link backward
        prev = curr;            // prev advances to the node we just handled
        curr = ahead;           // curr advances into the saved rest
    }
    return prev;                // prev is the last node we touched — the new head
}

Walk one turn of the loop and it clicks: save ahead so the tail survives, flip curr.next to point at prev, then slide prev and curr one step to the right. When curr finally walks off the end and becomes null, prev is sitting on the old last node — which is now the head. O(n) time, and O(1) extra space, because you rewired the list you already had and allocated nothing.

Fast and slow pointers: the trick that feels like cheating

Here’s the move worth slowing down for. Two questions look like they each need a second pass or a set of visited nodes — find the middle and is there a cycle? — and a single idea answers both with neither. Walk two pointers at different speeds: slow takes one step, fast takes two.

For the middle, that’s almost obvious once you say it out loud. Fast covers twice the ground, so when fast reaches the end, slow has covered exactly half — it’s standing on the middle. One pass, no counting the length first.

For a cycle, the same two pointers do something lovely. If the list actually ends, fast runs off the edge and hits null — no cycle. But if there’s a loop, fast can never fall off; it’s trapped going round and round. And here is the part that feels like magic: once both pointers are inside the loop, fast must eventually crash into slow.

Why must they meet? Think about the gap between them, measured as the number of steps fast is behind slow around the loop. Every tick, slow moves 1 and fast moves 2, so fast closes that gap by exactly 1 each step. A gap that starts at some finite size and shrinks by exactly one every step can’t leap over zero — it has to land on zero. And a gap of zero means they’re on the same node. That’s the entire proof: no hash set of visited nodes, no marking, just O(1) memory and a gap that can’t help but close.

public static boolean hasCycle(Node head) {
    Node slow = head;
    Node fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;      // one step
        fast = fast.next.next; // two steps
        if (slow == fast) {
            return true;       // the hare lapped the tortoise
        }
    }
    return false;              // fast fell off the end — no cycle
}
 
public static Node middle(Node head) {
    Node slow = head;
    Node fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow; // for an even length, the second of the two middles
}

Now the encore, and this is the genuinely deep bit — finding where the loop begins. Let the straight tail before the loop have length a, let the pointers first meet b steps into a loop of length L. Slow travelled a + b to get there; fast travelled twice that, and also went some whole number of extra laps, so fast’s distance is a + b + k·L. Setting those equal:

2(a + b) = a + b + k·L, which tidies up to a + b = k·L, so a = k·L − b.

Read that last equation out loud. The distance from the head to the loop’s start (a) is the same as the distance from the meeting point onward to the loop’s start (a whole number of laps, k·L, minus how far in you met, b). So if you park one walker back at the head, leave the other at the meeting point, and step both one node at a time, they arrive at the loop’s first node together.

public static Node cycleStart(Node head) {
    Node slow = head;
    Node fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {              // they met somewhere inside the loop
            Node walker = head;
            while (walker != slow) {     // now step both one at a time
                walker = walker.next;
                slow = slow.next;
            }
            return walker;               // they meet again exactly at the loop's start
        }
    }
    return null;
}

That’s not a coincidence to memorise — it falls straight out of a = k·L − b. Understand that one line and you never have to relearn the algorithm.

The interview corner

Before you write a line, ask:

• Singly or doubly linked? It decides whether you can delete a node in place and whether you can walk backward at all.
• Is there a sentinel/dummy head, or a raw head I have to special-case? It decides how many null checks you owe.
• Can the list be empty, and can the input contain a cycle? It decides your loop guards — and whether a naive traversal ever terminates.

The follow-up ladder — each rung a new scenario, not a re-run of the last:

1. “Reverse only between positions m and n.” Walk to the node before m, reverse that segment with the three-pointer dance, then stitch the two dangling ends back on. The whole trick is bookkeeping the four boundary nodes.
2. “Detect the cycle and return its start.” Floyd to the meeting point, then the head-and-meeting-point walk from a = k·L − b.
3. “Find the k-th node from the end in one pass.” Two pointers k apart: advance the leader k steps first, then move both until the leader hits null — the follower is on your answer.
4. “Merge two sorted lists.” A dummy head plus a tail cursor; splice the smaller front node each step. O(n + m) time, O(1) extra — the sentinel earns its keep again.
5. “Do two lists intersect (share a tail)?” Walk both; when one ends, restart it at the other’s head. After a + b + c steps both pointers land on the join (or on null together). No length math, no set.

Mistakes that fail the round:

• Overwriting next before saving it — the Step 3 orphan bug. You lose the tail of the list and don’t notice until a later test.
• Ignoring the empty and single-node cases. These are the exact inputs sentinels exist to erase; without them, your removeFirst NPEs on the interviewer’s first edge case.
• Dereferencing fast.next.next without guarding fast != null && fast.next != null. On an even-length list fast lands on null and your cycle check crashes — the one line everyone forgets.

Where to go from here

You now own the core idea: scattered nodes, joined by pointers; cheap to splice where you stand, slow to reach. Three natural next stops:

• Skip lists — a linked list with express lanes stacked on top, buying back O(log n) search. It’s the structure behind Redis sorted sets, and a gentler cousin of the balanced tree.
• The thread-safe LRU cache — a doubly linked list married to a hash map so every operation is O(1), then made safe under concurrent access. It’s the payoff for everything here.
• Unrolled and XOR linked lists — memory tricks that pack several values per node or store prev ⊕ next in one field, trading a little clarity for the cache-friendliness we flagged in the trade-offs. Great for appreciating why arrays quietly win so many real benchmarks.

Next time you tap the back button and the previous page just appears, you’ll know there was never a map — only a node, quietly holding the address of the one before it, the way a good clue holds the next spot in the hunt.