50The linked list — data joined by pointers

In Chapter 49 we built the array: one contiguous block, where order is nothing but adjacency. Element 5 sits right after element 4, and "next" means a few bytes further along. The linked list is its exact opposite. I want to take the trade slowly, because it's the cleanest example in the whole volume of buying one power by selling another. Here's the plan. We scatter each element into its own little object on the heap — a node — and hand every node a pointer to where the next one lives. Order stops being about addresses and starts being about arrows. The whole way through, we keep asking the one question that decides everything: if the sequence lives in the pointers instead of the layout, what does that make almost free, and what does it make ruinously expensive? By the end you'll know why splicing into a linked list is O(1) when you already hold the spot, why finding that spot is O(n), and why a scattered list crawls even though it's "the same" O(n) as an array. You'll also know when that trade is the one you actually want.

01Order without neighbours

Let's start with how an array keeps order, because the linked list is defined entirely by rejecting it. An array keeps order by adjacency: element 5 sits right after element 4 in one block, so "next" just means "8 bytes further along" (Volume 1, chapter 8). A linked list throws that rule out. It scatters its elements anywhere the heap has room. Each element carries a note — a reference, the same 8-byte machine pointer that names use in Volume 1 — saying where the next one is. The container remembers just one thing: a head reference to the first node. Follow the notes and the sequence unspools, even though no two nodes need sit anywhere near each other in memory.

Read that slowly, because it's the whole idea, and everything else in the chapter falls straight out of it: logical order lives in the pointers, not in the addresses. Two nodes that are "adjacent" in your playlist can sit on opposite ends of RAM. That one decision buys the linked list its superpower: you can rearrange the sequence without moving a single byte of data. It also saddles the list with its curse: you can't jump to the middle, because there's no address to compute. Let's watch it happen in memory first.

If order is just arrows, rearranging the playlist should be almost free — no block to shift. Let's cash that in. But first: what does one node actually cost? →

02The pointer tax

Nothing is free, and the linked list's bill comes due in bytes. In an array (a Python list), each element is stored as one bare 8-byte reference, packed shoulder-to-shoulder in a shared block. The object header is paid once for the whole list. A linked list can't do that. Every element is its own heap object, so every element pays the full Python object tax again. I measured a minimal node on CPython 3.12 — a class with __slots__, so it carries no per-instance dictionary:

import sys

class Node:
    __slots__ = ('value', 'next')      # no per-instance __dict__
    def __init__(self, value):
        self.value = value             # a reference to the song
        self.next  = None              # a reference to the next node (or None)

a = Node("Levels"); b = Node("Wake Me Up"); c = Node("Titanium")
a.next = b; b.next = c                  # a -> b -> c -> None
print(sys.getsizeof(a))                 # 48   bytes per node

48 bytes. The node holds only two useful references — 16 bytes of actual pointers — wrapped in 32 bytes of Python machinery: the reference count, the type pointer, and the garbage-collector bookkeeping every tracked object carries (Volume 1, chapter 4). So to store one element's worth of sequence, an array spends 8 bytes and a linked list spends 48. That's a 6× memory tax — 40 extra bytes on every single node. That surcharge is what buys the flexible arrows, and it is never free.

The tax is per element, so it never stays small; it scales with your data. Drive the count up and watch the same numbers cost three wildly different amounts of memory, decided by nothing but how you wrap them. Watch, too, where each layout spills out of cache.

So a node is heavy but its arrows are flexible. Now spend that flexibility — insert a song mid-playlist and count what actually moves. →

03Insertion is two pointers — given the node

Here's the linked list's marquee trick. To insert a new node X between two existing nodes A and B, you do exactly two things: point X.next at B, then point A.next at X. Two reference writes. Nothing else in the entire structure is read or moved — not the million nodes before A, not the million after B. Compare an array, where inserting at position i must shift every element from i onward one slot down to open a gap (Volume 1, chapter 8). That's O(n) copies. The linked list splice is O(1), and here's the beautiful part: it stays O(1) no matter where in the sequence you splice, because the cost doesn't depend on position at all. Order is arrows, and you're just re-drawing two of them.

The widget makes it literal. Slide to pick where the new node goes and watch. The linked list always writes two pointers, while the array beside it must shift a different number of elements depending on where you cut.

Which raises the obvious question: if I only have an index — "give me the 500th song" — how does a linked list find it? →

04…but finding it is a walk

Ask an array for element 500 and it does one multiplication: base + 500 × 8, jump straight there, done. That's O(1), the reward for living in one block (Volume 1, chapter 8). A linked list can offer nothing like it. There is no base address and no arithmetic, because the nodes are scattered and only the arrows know the order. To reach index k you must start at head and follow next k times, node by node. Reaching the 500th node means visiting the other 500 first. That's O(n), and it's baked into the layout — the price of trading adjacency for arrows.

I measured the gap on a million-node list. Walking to the middle took about 9 milliseconds; the array's lst[k] took about 0.1 microseconds — the O(n) walk versus the O(1) address computation. Most of those 9 ms is simply the half-million pointer hops the walk is forced to make. The array never hops at all. (Wall-clock numbers vary by machine; the O(n)-vs-O(1) shape does not.)

Drive the walk yourself. Slide the target index and watch the current pointer crawl from the head, one hop per node. The hop count is the index.

O(n) to walk, O(n) to scan — the same big-O as an array. So a full pass over a linked list and a full pass over an array should take the same time, right? Time them and prepare for a shock. →

05Same O(n), wildly different speed

This is the section that separates people who know Big-O from people who know the machine. Summing a linked list and summing an array are both O(n): n additions, one per element. Big-O says they should scale identically, and they do. But wall-clock time is a different story, and the reason is the memory hierarchy from Volume 3. The CPU never fetches one value from RAM. It fetches a whole cache line — 64 bytes, eight references' worth — and keeps it in fast on-chip memory. An array is one contiguous block, so a single fetch pulls in the next eight elements for free. The scan streams: fetch a line, use eight, fetch the next. This is called spatial locality, and hardware is built to reward it.

A linked list has none of it. Its nodes are scattered wherever the allocator found room, so following next lands you at an unrelated address every time. Each hop is a fresh cache miss: the CPU stalls, waits a hundred-odd cycles for RAM, pulls a 64-byte line to use just 8 bytes of it, then hops somewhere else and does it again. This is pointer-chasing, and it's the linked list's hidden tax. I measured a two-million-element sum three ways:

array sum (contiguous)                     49 ms   (24 ns/elem)
linked list sum (nodes in alloc order)     55 ms   (28 ns/elem)
linked list sum (nodes shuffled in RAM)   407 ms  (204 ns/elem)

Same n, same additions, same O(n). Yet the scattered linked list ran roughly 8× slower than the array on that run, and about 6× on a second run. (It's a cache effect, so the exact ratio drifts with the machine and memory state, but it's always a large constant, never 1×.) Look closely at the middle row. A linked list whose nodes happen to be allocated in order is nearly as fast as the array, because consecutive nodes land near each other and the scan stays cache-friendly. It's the scattering that kills it, not the linking. Two structures, one complexity class, an order-of-magnitude difference in the only number the user feels.

If it's heavier and slower to scan, why does the linked idea sit at the heart of some of the most-used software on your machine? Because there's a job only it can do. →

06Two-way streets, and where this really lives

Add one more pointer to each node — a prev reference back to the previous node — and you get a doubly linked list. Now you can walk either direction. More importantly, you can delete a node in place when you're standing on it: reach both neighbours through prev and next, wire them to each other, and the node is gone in O(1), with no need to have walked from the head to find the one before it. My measurement puts a doubly linked node at 56 bytes versus the singly node's 48: one extra 8-byte pointer, the fee for two-way travel. Link the tail's next back to the head and it becomes circular — no beginning, no end, useful for round-robins.

You almost never type class Node in Python. The built-in list and deque (Chapter 53) cover the common needs faster, thanks to their block layout. The linked list's real importance is that the idea is everywhere underneath, doing the one job it owns: rearranging a sequence, or splicing and unsplicing elements, in O(1) when you hold a handle to the spot. It does this with no reallocation, and node identities stay valid while the structure changes around them.

One more thing only a linked structure gives cheaply: reversal. Flip every node's arrow and the sequence runs backward — no data copied, just pointers turned around. Watch it move only pointers:

def reverse(head):
    prev = None
    cur  = head
    while cur is not None:
        nxt = cur.next     # remember where we were going
        cur.next = prev    # flip this node's arrow backward
        prev = cur         # advance the two walkers
        cur = nxt
    return prev            # prev is the new head

# a -> b -> c  becomes  c -> b -> a
# before: ['Levels', 'Wake Me Up', 'Titanium']
# after : ['Titanium', 'Wake Me Up', 'Levels']

Line by line: prev trails behind and cur leads. Each turn of the loop stashes the forward link in nxt, or we'd lose the rest of the list the instant we overwrite it. Then it flips cur.next to point backward at prev, and shuffles both walkers one step forward. When cur runs off the end, prev is left holding the last node — the new head. I ran it on Levels → Wake Me Up → Titanium and got Titanium → Wake Me Up → Levels. Not a single value object moved in memory; only the arrows turned. That is the linked list's whole personality in eight lines: cheap to re-wire, and it never touches the data.

The next chapter does exactly that. Take a list, forbid every operation except push and pop at one end, and you get the stack — the simplest container there is, and the one quietly running your program's function calls right now. →