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, and 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 we 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, and why finding that spot is O(n). You'll see why a scattered list crawls even though it's "the same" O(n) as an array — and when that trade is exactly the one you 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 saying where the next one is. That note is a reference, the same 8-byte machine pointer that names use in Volume 1. 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.

Before we count bytes, hold one node in your hand and picture a playlist of three songs: Levels → Wake Me Up → Titanium. Each node is a tiny two-cell box. The first cell holds a reference to its value, the song itself, and the second holds a reference to the next node, the arrow. The Levels node doesn't contain Wake Me Up inside it — it just knows the address where that node lives. The figure below lays the three boxes out at unrelated addresses, and the only thing stitching them into an order is those arrows. Trace them once with your finger before we start pricing them.

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. It's 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, which is 16 bytes of actual pointers. Those sit 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.

Break that 32-byte header open and the tax is easy to audit. Eight bytes hold the reference count, eight more hold the type pointer that says "I'm a Node", and the last sixteen are garbage-collector bookkeeping: 8 + 8 + 16 = 32, and the two useful pointers then push that to 48. And here's the quiet twist. Those 16 GC bytes are themselves two 8-byte pointers, threading this node onto a hidden doubly linked list that the collector keeps — a linked list riding inside every node of your linked list. Hold that thought; we cash it in at the end of the chapter.

Let's make that surcharge concrete at scale, because 40 bytes sounds tiny until you multiply. Say you store a million songs. The array packs them as a million bare references: 1,000,000 × 8 bytes = 8 MB, one clean block. The linked list pays the full node price on each one: 1,000,000 × 48 bytes = 48 MB. Same million songs, and the linked version has eaten an extra 40 MB of RAM to hold nothing but reference counts, type pointers, and arrows. The tax didn't stay small. It grew in lockstep with your data, exactly as "per element" promised.

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.

import time
n, reps = 200_000, 20_000

class Node:
    __slots__ = ('val', 'nxt')
    def __init__(self, val, nxt=None): self.val, self.nxt = val, nxt

L = list(range(n))                            # one contiguous block
head = cur = Node(0)                          # one chain of the same length
for v in range(1, n):
    cur.nxt = Node(v); cur = cur.nxt
held = head
for _ in range(n // 2): held = held.nxt       # walk ONCE, then keep the handle

t = time.perf_counter()
for _ in range(reps): L.insert(n // 2, -1)          # every call slides the tail
print("list.insert(mid)  :", round((time.perf_counter() - t) * 1000, 1), "ms")

t = time.perf_counter()
for _ in range(reps): held.nxt = Node(-1, held.nxt) # two writes, nothing slides
print("splice at held    :", round((time.perf_counter() - t) * 1000, 1), "ms")

list.insert(mid)  : 373.3 ms
splice at held    : 4.1 ms

INPUTimport sys
from dataclasses import dataclass

@dataclass(slots=True)
class Node:
    val: int
    nxt: "Node | None" = None

head = Node(1, Node(2, Node(3)))     # build it inside-out

cur, total, hops = head, 0, 0
while cur is not None:               # the ONLY way through a chain
    total += cur.val
    hops += 1
    cur = cur.nxt
print("summed", total, "in", hops, "hops")
print("one node  :", sys.getsizeof(head), "bytes  (slots=True)")
print("repr(head):", repr(head))

OUTPUTsummed 6 in 3 hops
one node  : 48 bytes  (slots=True)
repr(head): Node(val=1, nxt=Node(val=2, nxt=Node(val=3, nxt=None)))

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.

One quiet detail decides whether that splice works or corrupts the list: the order of the two writes. You must set X.next to B first, while A.next still points at B and can tell you where B is. Then, and only then, set A.next to X. Do it the other way round and you overwrite A.next before you've read it. Now B's address is gone, and the whole tail of the list after A has fallen off into the void. Same two writes, opposite outcome. When you re-wire pointers, the sequence you read and overwrite them in is part of the algorithm, not a detail.

Let's put addresses on it so the ordering isn't abstract. Say node A lives at address 200, B at 350, and the new node X at 500. Right now A.next holds 350, pointing straight at B. First we set X.next = 350, so X now knows where B is. Only then do we set A.next = 500, so A points at X instead. Read the chain from A and you get 200 → 500 → 350, exactly A → X → B. Reverse the two writes and A.next becomes 500 before anyone saved 350 — so B's address is lost, and everything past it leaks away.

The widget below makes it literal. Slide to pick where the new node goes, and watch what each side has to do. The linked list always writes exactly two pointers, no matter where you drop the node. The array beside it must shift a different number of elements depending on where you cut. And the further left you insert, the more it copies.

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), 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.)

Put a clock on a single hop and the O(n) gets vivid. Nine milliseconds is 9,000,000 nanoseconds, spread across the half-million hops the walk makes: 9,000,000 / 500,000 ≈ 18 nanoseconds per hop. That's the cost of one link followed — read the node, grab its next, move on. The array pays this zero times: it computes an address and lands in a single shot. So the linked list's bill for reaching the middle isn't one slow step, it's half a million ordinary steps with nothing to skip them. There is no arithmetic shortcut when order lives in the arrows.

Here's the arithmetic behind that walk. Reaching index k costs exactly k hops, so index 0 is free and the last index costs the whole list. Average that over every position and a random lookup runs about n/2 hops. On a million-node list that's 500,000 pointer hops for one index, every single time. An array answers any of them with one multiplication. That distance between 500,000 and 1 is what O(n) versus O(1) means in hardware, not on paper.

Drive the walk yourself. Slide the target index and watch the current pointer crawl out from the head, one hop per node. Count them as they go, because the hop count is the index — that equality is the whole cost of a linked-list seek.

from dataclasses import dataclass

@dataclass(slots=True)
class Node:
    val: str
    nxt: "Node | None" = None

def walk(head):                       # yields the nodes themselves, in order
    cur = head
    while cur is not None:
        yield cur
        cur = cur.nxt

def reverse(head):
    prev, cur = None, head
    while cur is not None:
        nxt = cur.nxt        # 1. remember the way forward, or you lose the tail
        cur.nxt = prev       # 2. turn this arrow around
        prev, cur = cur, nxt # 3. shuffle both walkers one node along
    return prev              # cur fell off the end; prev is the new head

head = Node("Levels", Node("Wake Me Up", Node("Titanium")))
before_ids = [id(n) for n in walk(head)]
print("before:", [n.val for n in walk(head)])

head = reverse(head)
after_ids = [id(n) for n in walk(head)]
print("after :", [n.val for n in walk(head)])

print("same node objects, reversed order:", after_ids == before_ids[::-1])
print("nodes created during reverse     :", len(set(after_ids) - set(before_ids)))

# before: ['Levels', 'Wake Me Up', 'Titanium']
# after : ['Titanium', 'Wake Me Up', 'Levels']
# same node objects, reversed order: True
# nodes created during reverse     : 0

# READ THE LAST TWO LINES. Every id() came back, in the opposite order, and
# nothing new was allocated. The three song strings never moved, the three
# nodes never moved -- three assignments to .nxt reversed the whole sequence.
# An array reversal has to write every slot. This wrote the arrows and left
# the data exactly where the allocator first put it.
# The one line that carries the whole algorithm is nxt = cur.nxt. Delete it
# and cur.nxt = prev overwrites the only pointer to the rest of the list,
# so the loop ends after one node and the tail is unreachable forever.

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, and pulls a 64-byte line only to use 8 bytes of it. Then it hops somewhere else and pays the whole price over 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.

Here's the same story counted in fetches, so the 8× stops feeling like magic. A cache line is 64 bytes, which is 64 / 8 = 8 references. To sum two million array elements, the CPU streams the block in 2,000,000 / 8 = 250,000 line fetches, and every fetch delivers eight useful values. The scattered linked list can't share a line between nodes, so it pays up to 2,000,000 fetches, one per hop, and throws away 56 of every 64 bytes it drags in. Roughly eight times the memory traffic for the identical arithmetic. That ratio is the 8× you measured, and it was hiding in the geometry all along.

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). There's 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.

Picture three nodes A ⇄ B ⇄ C and say you want B gone. Standing on B, you read its two neighbours: B.prev is A, B.next is C. Two writes finish the job — set A.next = C, then C.prev = A. Now A and C point straight at each other, B is unreachable, and the reference count that kept it alive falls to zero. No walk from the head, no shifting of neighbours: O(1), decided entirely by the two pointers you were already holding.

Watch the reference count do the cleanup for you — this is where Volume 1's memory model pays off. While B sat in the chain, two live pointers from inside the list named it: A.next and C.prev. So its structural refcount was 2. The moment you rewire both — A.next = C, then C.prev = A — those two references vanish, and the count drops 2 → 1 → 0. Once your own local handle on B is gone too, CPython reclaims its 56 bytes on the spot (Volume 1, chapter 4); you never call anything like free. Unlinking a node and freeing its memory are the same event, and both are O(1).

Where does a two-way or circular list actually earn its extra pointer? Wherever you need to step backward or loop forever. A media player's previous-track button wants prev, so pressing it is one hop, not a walk from the start. An operating system's run queue of ready processes is often circular. The scheduler hands each one a time slice, then follows next to the following process, and the tail loops back to the head so the rotation never ends. No beginning, no end, no special case for "wrap around". The extra 8 bytes per node buys exactly that freedom of movement.

from dataclasses import dataclass
import time, tracemalloc

@dataclass(slots=True)
class Node:
    val: int
    nxt: "Node | None" = None

def chain(n, joins_at):          # n nodes; the tail links back to index joins_at (-1 = ends at None)
    ns = [Node(i) for i in range(n)]
    for i in range(n - 1):
        ns[i].nxt = ns[i + 1]
    if joins_at >= 0:
        ns[-1].nxt = ns[joins_at]
    return ns[0]

def has_cycle(head):             # Floyd -- two names, whatever the chain's length
    slow = fast = head
    while fast is not None and fast.nxt is not None:
        slow = slow.nxt          # one hop
        fast = fast.nxt.nxt      # two hops
        if slow is fast:         # fast has caught slow inside the loop
            return True
    return False                 # fast ran off the end: no loop

def where_it_joins(head):        # phase two: WHICH node the loop closes back onto
    slow = fast = head
    while fast is not None and fast.nxt is not None:
        slow, fast = slow.nxt, fast.nxt.nxt
        if slow is fast:         # met somewhere inside the loop
            slow = head          # send slow back to the head; now BOTH step by one
            while slow is not fast:
                slow, fast = slow.nxt, fast.nxt
            return slow          # they meet exactly at the join
    return None

def has_cycle_seen(head):        # the referee: obviously right, and it pays in memory
    seen, cur = set(), head
    while cur is not None:
        if id(cur) in seen:
            return True
        seen.add(id(cur))
        cur = cur.nxt
    return False

N = 1_000_000
looped, straight = chain(N, 600_000), chain(N, -1)

print("looped   chain -> Floyd", has_cycle(looped),   "| referee", has_cycle_seen(looped))
print("straight chain -> Floyd", has_cycle(straight), "| referee", has_cycle_seen(straight))
print("the loop closes back onto node", where_it_joins(looped).val)

for name, fn in (("seen-set", has_cycle_seen), ("Floyd   ", has_cycle)):
    t = time.perf_counter(); fn(straight); ms = (time.perf_counter() - t) * 1000
    tracemalloc.start(); fn(straight)                  # memory measured on its own pass
    peak = tracemalloc.get_traced_memory()[1]; tracemalloc.stop()
    print(name, "walked 1,000,000 nodes in", round(ms), "ms, peak extra memory",
          round(peak / 1e6, 1), "MB")

looped   chain -> Floyd True | referee True
straight chain -> Floyd False | referee False
the loop closes back onto node 600000
seen-set walked 1,000,000 nodes in 160 ms, peak extra memory 70.5 MB
Floyd    walked 1,000,000 nodes in 15 ms, peak extra memory 0.0 MB

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. That job is 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 with node identities that stay valid while the structure changes around them.

Here's the one that surprises people: CPython itself runs on linked lists. Every container object the garbage collector tracks is threaded onto a doubly linked list, and that threading lives inside the 32-byte header we metered back in section 02. The collector walks that list to hunt unreachable cycles, and it splices objects on and off it in O(1) as they're created and freed. So the pointer tax from section 02 wasn't pure overhead — part of it was buying exactly this. You've been leaning on a linked list on every line of Python you've ever run, one level down.

One more thing only a linked structure gives cheaply: reversal. Flip every node's arrow so it points at the one behind it, and the whole sequence runs backward with no data copied — just pointers turned around. In an array you'd have to move every element to a new slot. Here you touch nothing but the links. 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. →