Linked Lists: When They Actually Beat Arrays

The case against the linked list is already on record. Lesson 2 summed the same 17 million integers twice: as an array, a few milliseconds; as a chain of nodes, nearly two full seconds. Every hop a dependent cache miss, the prefetcher blind, ~100 nanoseconds times 17 million. One streams, one commutes. Ever since, the list has served as this course's cautionary tale, the anti-array, the structure we point at to show how expensive memory access can get.

But lesson 2 also made a promise: the list has real wins, and this lesson would weigh them honestly. So here is the verdict up front, because the defense has nothing to hide. The list loses the default case. If you need a sequence to append to, scan, and index, take the array; the whole first module explained why. But there are four specific situations, each running in production right now, where the linked list genuinely beats it. By the end you'll know all four, and the more valuable skill: recognizing when you're standing in one.

First, the defense introduces its client properly. So far you've only seen it as a victim.

The machine: a value and an address

A node is two fields:

struct node:
    value: the element you're storing
    next:  pointer to the next node, or null

The list itself is one more pointer, the head, aiming at the first node. The last node's next is null: end of chain. Each node is allocated separately, so the nodes of one list can be scattered across the entire heap, and in a long-running program they are. That scattering is exactly what cost two seconds in lesson 2.

Two upgrades appear everywhere. Keep a tail pointer to the last node and both ends are reachable in O(1). Give each node a second pointer, prev, and you can walk in either direction: a doubly linked list. The price is worth stating plainly: on a 64-bit machine every pointer is 8 bytes, plus each node pays its own allocator overhead. A doubly linked list of small integers spends more memory on wiring than on cargo, often 3 to 5 times the footprint of the equivalent array. Hold that for the verdict.

Pointer surgery

Everything the list is good at, it does with two pointer writes. Say the chain reads A → B → C and you want X after B:

function insert_after(node, value):
    fresh = allocate node(value)
    fresh.next = node.next        # X points at C first
    node.next  = fresh            # then B points at X

Read the chain now: A → B → X → C. Two writes plus one allocation, and the length of the list is irrelevant. A million nodes after C? None of them were touched. Compare lesson 3: inserting at the front of a million-element array shifts every single element, a million moves to open one slot. The list does the job in O(1), truly, with no amortized asterisk and no resize.

One detail matters more than it looks: the order of those two writes. Point X at C before B points at X. Do it backwards and the moment B.next is overwritten, nothing points at C anymore; the rest of the chain is orphaned. That single ordering mistake is probably the most-written linked list bug in history.

Deletion is the same surgery in reverse: route around the victim.

function delete_after(node):          # singly linked
    victim = node.next
    if victim != null:
        node.next = victim.next
 
function unlink(node):                # doubly linked: the node carries its own map
    node.prev.next = node.next
    node.next.prev = node.prev

In the doubly linked version the node unlinks itself: its prev knows who's behind, its next knows who's ahead, two writes wire them to each other. No walking required.

Now notice what didn't happen in any of these operations. Nothing shifted. Nothing reallocated. No block grew and moved house. Recall lesson 3's sharp edge: one append past capacity and every saved pointer into a vector dangles. The list has no such moment. A node's address is fixed the day it's allocated and stays fixed until it's freed, no matter what happens to its neighbors. File that fact away; it becomes Exhibit A.

The asterisk on O(1)

Now the cross-examination. Ask an array for element 500,000: base plus offset, one multiply, one add, one load. O(1). Ask a list for element 500,000: there is no offset arithmetic. The only way to reach node half-a-million is to start at the head and follow half a million pointers. O(n), and every hop is a dependent miss, the expensive kind.

So look again at "insert is O(1)". True, if you are already holding the node. Getting your hands on the node, by index or by search, costs O(n). That asterisk is the trap that makes naive list code slow, and it has a canonical victim:

for i from 0 to n-1:
    process(list.get(i))      # get(i) walks from the head: i hops

In Java, LinkedList implements the same List interface as ArrayList, so this compiles and looks linear. But get(i) re-walks from the head on every call: 0 hops, then 1, then 2... n²/2 hops total. It's Shlemiel the painter from lesson 4, walking back to the paint can, on a structure people chose because they heard insertion was fast. The honest rule: a linked list earns its keep only when you never ask it for position i. (One more thing a chain can do that an array can't: loop back on itself. A list with a cycle traverses forever; detecting one cheaply is lesson 7's fast/slow pointer trick.)

Sentinels: paying one node to delete the edge cases

One trick of the trade before the exhibits, because every serious implementation uses it. Write delete-by-value naively and the edge cases swarm:

function delete_value(list, target):
    if list.head == null: return              # edge case: empty list
    if list.head.value == target:             # edge case: victim is the head,
        list.head = list.head.next            # nothing before it to route around
        return
    cur = list.head
    while cur.next != null:
        if cur.next.value == target:
            cur.next = cur.next.next
            return
        cur = cur.next

Two special-case branches before the real logic starts, each a place to write a bug. The fix is almost cheeky: allocate one extra node with no meaningful value and park it permanently in front of the head. It's called a sentinel (or dummy node):

function delete_value(list, target):
    dummy = node(ignored, next: list.head)    # sentinel in front of everything
    cur = dummy
    while cur.next != null:
        if cur.next.value == target:
            cur.next = cur.next.next
            break
        cur = cur.next
    list.head = dummy.next

Now the real first element has a node before it like everybody else, and the empty list isn't a special shape, it's a sentinel pointing at null. Every delete is "delete after", one uniform case. Production lists (the kernel's included) go one further and bend the chain into a circle through the sentinel, so even "end of list" stops being special. This trick is also bread-and-butter interview fluency: most "hard" list problems lose half their difficulty the moment a dummy node appears.

Exhibit A: addresses that never move

Open the Linux kernel source and the most used data structure in the codebase is struct list_head: two pointers, next and prev, nothing else. It's used in a way that looks backwards at first. The kernel doesn't put objects into lists; it embeds the list nodes inside the objects:

struct task_struct:                # a process, simplified
    ... hundreds of fields ...
    tasks:    list_head            # links it into the global task list
    children: list_head            # and into its parent's children
    ... more list_heads ...        # scheduler queues, wait queues, timers

This is an intrusive list: the object is the node, no separate allocation, and the same object can sit in five lists at once. It works for one reason, the fact filed away earlier: a kernel object's address never changes, so a pointer to it is good forever, and it can leave any list in O(1) with two pointer writes. An array could never host this. Growth moves elements, and moving an element breaks every other reference to it.

The same idea runs your memory allocator. Freed blocks are threaded into a free list, with the next pointers stored inside the free memory itself, so the bookkeeping costs zero extra bytes and malloc can hand out a block by popping the chain.

Exhibit B: surgery on a node something else found

When another structure hands you the node, the O(n) search disappears and only the O(1) surgery remains. The textbook case, and a real one, is the LRU cache: items live in a doubly linked list ordered by recency, and a hash map points at each item's node. The map jumps straight to the node; the list unlinks it and reattaches it at the front, four pointer writes. O(1) to mark anything freshest, O(1) to evict the stalest from the tail. List and map, each covering the other's weakness. You'll build it, hash map and all, in the patterns course.

The kernel played the same trick for years: the famous O(1) scheduler kept a doubly linked run queue per priority level, so picking, enqueueing, and migrating tasks was all pointer surgery, constant time regardless of how many thousands of processes the machine juggled. The pattern in both: the list is never asked to search. Something else finds the node; the list does the splice.

Exhibit C: flat costs, no spikes

Lesson 1's fine print on amortized analysis: dynamic array appends are O(1) on average, but every so often one append pays for a full copy. Some code is not allowed an unlucky day. An audio callback must fill the next buffer in milliseconds, every time, or the speaker pops; a game frame has a 16ms budget; a trading system can't eat a copy spike mid-message. In those worlds the average is irrelevant and the worst case is the contract.

The list's costs are flat: every insert is one node and two writes, every unlink is two writes, no doubling, no copy storm. One honest caveat: allocating a node per insert has its own jitter, so real-time systems pair the list with Exhibit A's idea, a pre-allocated pool of nodes recycled through a free list. Pool plus intrusive list is quietly one of the most common structures in embedded and real-time code.

Exhibit D: shared tails

The last exhibit comes from the functional world: Erlang, Elixir, Clojure, the Lisp family, where data is immutable. You never modify a list; you make a new one. Prepending to an immutable array means copying all n elements (lesson 4's trenchcoat economics again). Prepending to an immutable list means allocating one node whose next points at the existing list. The old list is untouched, still valid, and shared: the new list and the old differ by exactly one node.

That two-field node is the cons cell Lisp was built on in 1958, and it's why every functional language made the linked list the list ([head | tail] in Erlang and Elixir is its syntax made visible). A thousand versions of a list, each one element longer, occupy roughly the memory of one, because they all share tails. This is structural sharing, and notice it's the same property working yet again: nodes never move and never mutate, so pointing into someone else's list is always safe.

The verdict

Total honesty now. In 2012, Bjarne Stroustrup, the creator of C++, ran a now-famous benchmark on stage: insert random values into a sequence, keeping it sorted, then remove them, comparing std::vector against std::list. Insertion in the middle is supposed to be the list's home turf. The vector won, and the bigger n got, the worse the list lost. The reason is pure lesson 2: before every insert you must find the position, and the find dominates. The vector's search streams through cache lines with the prefetcher running ahead; the list's search commutes, one dependent miss per hop. And the vector's shift, the part we call expensive, is a bulk copy of contiguous memory, the single operation hardware is best at.

Java tells the same story: LinkedList ships in the standard library, and Joshua Bloch, who wrote it, has quipped that he never uses it. The platform defaults agree with him; so should yours.

There are middle grounds, and they often beat both extremes. The deque in C++ and Python is an array of fixed-size chunks: cheap at both ends, no million-element shifts, mostly contiguous inside each chunk. It gets real treatment next lesson. Text editors split the difference with a gap buffer, an array that parks its spare capacity at the cursor, which is one line worth knowing and a rabbit hole worth skipping.

The list, in real code

The videos stay in pseudocode; here is a working singly linked list in the three languages this course carries. The API is the honest one: operations take and return nodes, because that's the contract that makes them O(1).

class ListNode<T> {
  next: ListNode<T> | null = null
  constructor(public value: T) {}
}
 
class SinglyLinkedList<T> {
  head: ListNode<T> | null = null
 
  pushFront(value: T): ListNode<T> {
    const node = new ListNode(value)
    node.next = this.head // new node points at the old chain first
    this.head = node // then the head moves
    return node // hand back the node: the O(1) handle
  }
 
  insertAfter(at: ListNode<T>, value: T): ListNode<T> {
    const node = new ListNode(value)
    node.next = at.next // surgery, in the safe order
    at.next = node
    return node
  }
 
  deleteAfter(at: ListNode<T>): void {
    if (at.next) at.next = at.next.next // route around the victim
  }
 
  *values(): Generator<T> {
    for (let cur = this.head; cur; cur = cur.next) yield cur.value
  }
}

type Node struct {
	Value int
	Next  *Node
}
 
type List struct {
	Head *Node
}
 
func (l *List) PushFront(v int) *Node {
	n := &Node{Value: v, Next: l.Head}
	l.Head = n
	return n
}
 
func InsertAfter(at *Node, v int) *Node {
	n := &Node{Value: v, Next: at.Next}
	at.Next = n
	return n
}
 
func DeleteAfter(at *Node) {
	if at.Next != nil {
		at.Next = at.Next.Next
	}
}
 
func (l *List) Each(f func(int)) {
	for cur := l.Head; cur != nil; cur = cur.Next {
		f(cur.Value)
	}
}

struct Node {
    int value;
    Node* next = nullptr;
};
 
class List {
    Node* head_ = nullptr;
 
public:
    Node* push_front(int v) {
        head_ = new Node{v, head_};
        return head_;
    }
 
    static Node* insert_after(Node* at, int v) {
        at->next = new Node{v, at->next};
        return at->next;
    }
 
    static void delete_after(Node* at) {
        if (Node* victim = at->next) {
            at->next = victim->next; // unlink first
            delete victim;           // then free
        }
    }
 
    ~List() {
        while (head_) {
            Node* next = head_->next;
            delete head_;
            head_ = next;
        }
    }
};

Every mutator returns the node it touched. That's not decoration; callers who keep those handles get O(1) surgery later (the LRU pattern), and callers who throw them away are signing up for O(n) walks.

The Go version compresses the two-step surgery into one line: the struct literal &Node{Value: v, Next: at.Next} reads the old at.Next before the assignment overwrites it, so the safe ordering is built into the expression. The deleted node has nothing pointing at it afterwards, and the garbage collector reclaims it.

C++ has no collector, so ownership is explicit, and two things in that version are worth walking through. delete_after must unlink before freeing; free first and victim->next is a read from freed memory, undefined behavior. And the destructor is a loop, not recursion: a recursive "delete the rest, then me" would build an n-deep call stack and overflow on a long list (the call stack gets its full treatment in lesson 9).

For completeness: C++ ships std::list (doubly linked, sentinel-based) and std::forward_list (singly), and Go ships container/list. All three are well built and rarely the right choice, for every reason in the verdict above. They exist for the exhibits, not for the default.

Closing the case

The ruling, then. The prosecution keeps the default case: for a sequence you append to, scan, and index, the array wins and lesson 2 stands. The defense won four narrow cases, and each has a recognizable shape: addresses that must never move (intrusive kernel lists, allocator free lists), surgery on a node something else already found (the LRU cache), flat worst-case cost (real-time pools), and shared immutable tails (the cons cell). Notice what all four have in common: none of them ever asks the list for element i. The moment you index, you've picked the wrong structure.

Next lesson, the two structures you'll use most weeks of your career: the stack and the queue. The undo button, the call stack, the print queue, the message broker, all one of these two. They're less structures than contracts, push and pop, enqueue and dequeue, and both the array and the list will audition to implement them. The workhorses are next.