Linked Lists

Arrays are contiguous memory — every slot is a calculated offset from the head. Linked lists are the opposite: each element (a node) lives wherever the allocator dropped it, and it carries a pointer to the next node so you can chase your way down the list. That one change — "you reach the next element through a pointer, not an index" — is the entire difference, and it ripples into everything: insertion cost, cache behaviour, traversal style, failure modes. Linked lists are a pedagogical touchstone long after arrays won the real-world contest.

Node anatomy

A singly-linked list node is two fields:

• value — the payload the list is carrying (an int, a struct, whatever).
• next — a pointer to the next node, or null at the tail.

A doubly-linked list adds one more field:

• prev — a pointer to the previous node. The head's prev is null; the tail's next is null.

That's it. No block of memory. No contiguous slots. The "list" is whatever you can reach by chasing next from the head. A list with a cycle is just a list whose tail's next happens to point back into itself — the data shape is identical; the difference is only whether the walker terminates.

Variant	Fields per node	Good at	Bad at
Singly-linked	value, next	Cheap (one pointer), forward-only walks	Can't walk backward without traversing from head
Doubly-linked	value, next, prev	O(1) unlink of a known node, bidirectional walks	2× pointer overhead per node
Circular	tail's next → head	Round-robin schedulers, ring buffers	Iteration needs a sentinel or bound

Why you'd use one over an array

Linked lists were the default "it's a list" structure for decades. The textbook pitch:

• O(1) insert/delete at a known node. Splicing a new node between two existing ones is three pointer writes. In an array, inserting in the middle shifts everything right — O(n).
• No up-front sizing. You grow one node at a time, paying one allocation each. Arrays grow by doubling and occasionally pay an O(n) copy.
• O(1) concatenation. Stitch two lists by pointing one's tail at the other's head.

Those are all real — and they all matter less than the one property linked lists don't have:

• Bad cache locality. Each node is a separate allocation, often nowhere near the previous node in memory. Walking the list is a series of cache misses — every node fetch is a ~100ns trip to main memory on modern hardware, where walking a contiguous array is ~1ns per element.

For small-to-medium n (say, n < 10,000) and sequential access, a plain array beats a linked list on almost every workload — including insert/delete in the middle, because the cache wins pay for the memmove. "Choose the data structure that matches your dominant operation" is the textbook answer; in practice, pick the array unless you have a specific reason not to.

A quick rule of thumb when benchmarking:

n	Array walk	List walk	Roughly
100	~1µs	~10µs	10× slower on list
10,000	~50µs	~1ms	20× slower on list
1,000,000	~5ms	~100ms	20× slower on list

The constant factors are brutal. Big-O says both are O(n), but the memory-latency penalty dominates.

Where linked lists genuinely earn their keep

Three real places to look for them in production code:

• LRU caches. The classic "hash map + doubly-linked list" combo: map keys to nodes for O(1) lookup; keep the linked list in recency order so bumping a key to the front is three pointer writes. Linux's kernel page cache, Redis' LRU eviction, Memcached, and functools.lru_cache in Python all use this pattern.
• Free-list allocators. A pool of same-size blocks, threaded onto a linked list — allocation pops the head, free pushes the node back. Used inside kernels, inside garbage collectors, inside custom slab allocators.
• Intrusive lists in C/C++. When the node owns both the data and the next pointer (via embedded link fields), you get O(1) unlink-anywhere without a separate map. The Linux kernel's list_head is the canonical example; thousands of subsystems use it.

Common anti-patterns: "linked list of ints". A List<Integer> in Java or a List[int] in Python-like languages is almost always slower than an array for small ints — you've paid one allocation per element and blown the cache, and you can't gain the theoretical O(1) insert unless you're already holding the node.

(Debunk one myth: the DOM NodeList is not a linked list. It's array-like — indexed access, .length, and internally stored as a collection, not a chain. Just because the word "list" appears doesn't mean anyone thought about this.)

Floyd's tortoise-and-hare

The single most famous linked-list algorithm is Floyd's cycle-detection trick, also called the "tortoise and hare" after Aesop. Two walkers start at the head:

• Slow advances one node per step.
• Fast advances two nodes per step.

Two surprisingly useful results pop out:

Finding the middle. When fast reaches the end (null), slow is at the midpoint — because slow walked at half the speed. For an odd-length list, slow lands on the single middle node; for an even-length list, it lands on the upper of the two middle nodes (position ⌊n/2⌋).

Detecting a cycle. If the list has a cycle, fast eventually laps slow inside the loop and they meet. If the list has no cycle, fast falls off the end first. No auxiliary memory, no hash set of visited nodes — just two pointers.

The proof-sketch for why cycle detection works: once both pointers enter the cycle, the gap between them shrinks by one node per step (fast gains ground at 2-vs-1), and the cycle length is finite, so they meet within at most L steps where L is the cycle length.

Three classic gotchas

Null-pointer walks. while (curr.next.next !== null) is a segfault waiting to happen the moment the list has fewer than three nodes. Every dereference should be guarded by the same iteration condition that guaranteed the node exists.

Infinite loops on cycles. A naive while (curr !== null) walk on a cyclic list never terminates. Either bound your walk explicitly (a maxIter counter) or use Floyd. This is the number-one bug in interview-style linked-list code.

Reverse that mutates vs returns new. "Reverse the list" is ambiguous: do you flip pointers in place, or allocate a new list? The idiomatic iterative reverse (shown in the code panel) mutates — it returns the new head, but the nodes themselves are the same objects with their next pointers rewritten. If callers still hold references to the old head, they now hold a reference to the new tail. Document this in the type signature.

Playground

Pick an op (reverse / find-middle / detect-cycle), give it a list, and watch the pointer dance frame by frame. Reverse paints prev / curr / next above the nodes they point at; Floyd's traces paint slow / fast. On a cycle-detect run, the meeting frame flashes the terminal result.

Visualizer

The Linked List Animator renders each frame as a row of node boxes with arrows between them and pointer labels floating above the current nodes. It's driven off the same pure Frame sequence the playground plays — the visualization and the playhead share no state, just a data structure.