Arrays vs Linked Lists: Why the Textbook Winner Loses on Real Hardware

Prefer to watch? ▶ The full 14-minute episode ⚡ The 2-minute version ✈ Telegram

Every data-structures course teaches the same table. Array: insert O(n), because you have to shift everything. Linked list: insert O(1), because you just repoint two pointers. Conclusion: if you insert a lot, use a linked list.

Then you write both, measure them, and the array wins anyway.

Here is the measurement that starts the whole story. Ten million integers, held as one contiguous array and as ten million linked nodes. Walk each one, summing as you go — the same operation count, the same complexity class, O(n) both:

contiguous array: 0.53 seconds (52.6 ns per element)
linked nodes: 1.53 seconds (153.3 ns per element)

2.9× apart, and nothing in the code explains it. Both loops do one add per element. Big-O says they're identical. The machine disagrees, and the reason is not in the code at all — it's in where the data physically sits.

Four ideas explain the whole gap: contiguity, the 64-byte cache line, the prefetcher, and pointer chasing.

The library, before the hardware

Imagine you need to read a hundred books.

In the array version, all hundred sit in order on one shelf. You walk up once, and you can grab an armful at a time. Your arms hold eight books, so a hundred books is about thirteen trips.

In the linked list version, each book sits on its own stand, somewhere in the building. Inside each book is a slip of paper telling you where the next one is. You cannot grab an armful, because you don't know where book two is until you've opened book one. A hundred books is a hundred separate walks — and you can't even start walking to the next stand until you've finished reading the current book.

That's the entire performance story. The rest is just naming the hardware that plays the role of "arms" and "walk."

The two structures, in code

# layout.py — the same 10,000,000 numbers, held two ways

data = list(range(10_000_000))    # ONE block: slot i sits beside slot i+1

class Node:
    __slots__ = ('val', 'next')   # 48 bytes, and no spare __dict__

def sum_array(data):              # walk the row
    total = 0
    for i in range(len(data)):
        total += data[i]
    return total

def sum_linked(head):             # follow next
    total, node = 0, head
    while node is not None:
        total += node.val
        node = node.next          # the next address lives INSIDE
    return total                  # the node you just finished reading

Look at the last line of sum_linked. The address of the next node is stored inside the node you are currently reading. You cannot know where to go next until the current fetch has completed. That single property is what costs you 2.9×, and it has a name: pointer chasing.

Where the data actually sits

The CPU never reads one integer from memory. It reads a cache line — 64 bytes, always, minimum. That's the "armful."

For a contiguous array of 8-byte values, one 64-byte fetch brings back eight useful values. You pay one trip to memory and get seven more elements for free. Walking a million elements costs you roughly 125,000 trips, not a million.

For scattered linked nodes, each node is its own allocation, sitting wherever the allocator happened to put it. One 64-byte fetch brings back one useful value — the rest of the line is that node's other fields and whatever unrelated bytes happen to be adjacent. Eight values cost eight full trips.

And the price of a trip is not a rounding error:

follow one pointer, already in L1 cache: 1.26 ns
follow one pointer, out in main memory: 81.5 ns

That's 65×. Not the folklore "a cache miss costs ~100×" — measured on this machine, it's 65. (The only ~100×-shaped real number here is 132×, and that's random pointer chase versus sequential streaming, which is a different comparison — keep that framing attached whenever you quote it.)

Then there's the prefetcher, which is the part most people never account for. When the CPU notices you walking memory in a predictable forward pattern, it starts fetching lines before you ask for them. Walking a contiguous 1 GiB array in order costs 0.62 ns per element — faster than a single L1 pointer hop, because the memory traffic is happening in the background while you compute. The prefetcher cannot help a linked list at all: it can't guess an address that hasn't been loaded yet.

What the hardware does	Contiguous array	Scattered linked nodes
Values per 64-byte fetch	8	1
Can the prefetcher help?	Yes — address is predictable	No — next address is unknown until the current load lands
Memory per 1,000,000 elements	8.2 MB (`array.array`)	80 MB
Walk 10,000,000, measured	0.53 s	1.53 s

The proof: an experiment with no linked list in it

Everything above is a story about why the linked list is slower. It could be wrong. Maybe the gap is really about node objects, or attribute lookup, or allocation count — plenty of things differ between those two loops.

So here's the experiment that isolates the cause. Take the same array. Do the same additions. Same class, same code, same object count. Change exactly one thing: the order in which you touch the elements.

walking in order: 44.4 ns per operation
walking the identical data in shuffled order: 265.8 ns per operation

~6× slower, with no linked list anywhere in the experiment. Nothing changed but the access pattern. That's the cache effect, measured on its own, with every other variable held down.

There's a matching version on the allocation side: keep the linked list, keep the class, keep the code, and shuffle only the order the nodes were allocated in. That alone is 2.1× slower — pure layout, no algorithmic difference at all.

This is the section to remember. The linked list isn't slow because it's a linked list. It's slow because it is the data structure most likely to scatter your data, and scattered data defeats every memory optimization your CPU has.

What Big-O counts, and what it never counts

Big-O is not wrong here. It's answering a different question.

Big-O counts operations, and it deliberately throws away constant factors — that's the whole point of the abstraction, and it's why it survives across machines and decades. What it throws away includes: how far the data travelled, whether the fetch hit L1 or DRAM, and whether the prefetcher was able to work ahead.

Two O(n) walks can be 2.9× apart. Two O(1) operations can be 65× apart. Big-O tells you how the cost grows; it says nothing about what one unit of that cost actually is on real silicon. For large asymptotic gaps — O(n) vs O(log n) — the growth term dominates and Big-O decides. For comparisons within the same class, it's silent, and the memory hierarchy does the deciding.

The honest other half: where linked structures genuinely win

Now the fair fight, because there is a real case here and it deserves real numbers.

Front insertion. Inserting at the head of an array means shifting every element. Inserting at the head of a linked list means writing one pointer:

array, N = 1,000,000: 572,255 ns
linked, N = 1,000,000: 243 ns

That's a genuine, enormous, structural win. It is not a rounding error and it doesn't go away on better hardware.

But that O(1) has a precondition that almost every textbook drops: you must already hold the node. Splicing after a node you have in hand is genuinely O(1). Finding that node first is not.

# insert_middle.py — the O(1) everyone quotes, with its precondition put back

def splice_after(node, value):     # O(1) — TRUE, but only if you HOLD node
    node.next = Node(value, node.next)

def insert_at(head, k, value):     # what you actually have to write
    node = head
    for _ in range(k):             # and this is not a memmove.
        node = node.next           # it is k dependent cache misses, one at a time.
    splice_after(node, value)

Measured at N = 1,000,000, inserting in the middle:

list.insert(mid, x): 255,486 ns
linked: traverse + splice: 63,488,013 ns — 249× slower

The array's O(n) shift is a memmove: one tight, prefetcher-friendly, sequential sweep that the hardware is exceptionally good at. The linked list's O(k) traversal is k dependent cache misses in a row, each one waiting on the last. Same complexity class, wildly different machine.

So the rule is not "linked lists are slow." It's: a linked structure wins when you already hold the position.

Operation, N = 1,000,000	Array / list	Linked	Winner
Walk everything	0.53 s	1.53 s	Array, 2.9×
Insert at front	572,255 ns	243 ns	Linked, huge
Insert in middle, position not held	255,486 ns	63,488,013 ns	Array, 249×
`deque.appendleft` vs `list.insert(0,x)`	25,434 ns	53.3 ns	Linked, 477×
Remove a node you already hold vs `del lst[i]`	13,692 ns	335 ns	Linked, 41×

Linked structures also give you stable references: a node's address doesn't move when its neighbours change, so pointers held elsewhere stay valid. Arrays give you no such guarantee. That property — not raw speed — is why linked structures show up inside allocator free lists, LRU caches, and intrusive kernel lists.

What your language already chose for you

Most of this decision was made for you, and it's worth knowing what you actually have:

A Python list is a contiguous array — but of pointers. The integers themselves are separate heap objects scattered elsewhere, which is why a million elements costs ~40 MB rather than 8.2 MB. You get contiguity of the references, not of the values.
array.array('q') is the true contiguous case: the 8-byte integers really do sit side by side. That's the 8.2 MB row.
collections.deque is a doubly-linked list of blocks, not of single elements. Each block holds many items contiguously, so it gets cache-friendly iteration and O(1) ends. That hybrid is why appendleft beats list.insert(0, x) by 477×, and it's the shape most "linked list" wins in production actually take.
Java's ArrayList vs LinkedList: the same story, and the reason LinkedList is near-universally discouraged in modern Java style guides.
NumPy arrays are genuinely contiguous typed memory — the reason numeric Python is fast at all.

Notice the pattern: the winning structures are blocked — contiguous runs, linked at a coarse granularity. You get sequential access inside a block and cheap restructuring between blocks.

The same rule, one layer up: why this shows up in LLM serving

If you work on inference rather than data structures, you have met this exact tradeoff wearing a different hat.

Serving an LLM means holding a KV cache — the keys and values for every token in every active sequence. Naively you allocate one contiguous buffer per sequence, sized to the maximum possible length. That's the array choice: perfectly sequential, prefetcher-friendly reads during attention, and enormous waste, because most sequences never reach the maximum and you cannot hand the slack to anyone else.

The obvious fix is to allocate per token and link them. That's the linked-list choice, and it fails for exactly the reason above: attention would then walk a pointer chain per token, turning the hottest loop in the system into dependent cache misses.

What production engines actually do — PagedAttention in vLLM being the well-known case — is the deque answer: a linked list of fixed-size blocks. Each block holds many tokens contiguously, so attention reads run sequentially inside a block, while a per-sequence block table lets memory be allocated, freed, and even shared between sequences at block granularity. Contiguity where you iterate, indirection where you restructure.

The batching story is the same shape. Continuous batching wins partly because it keeps the tensors that the GPU streams through contiguous and predictable; every gather or scatter you introduce is the shuffled-access experiment from earlier, running on far more expensive hardware. Data locality is not a CPU-era detail you've outgrown — the memory wall is wider on a GPU, not narrower.

Five questions worth being able to answer

Two O(n) loops over the same data are 3× apart. Why? Memory layout: cache lines and prefetching. Big-O counts operations, not the cost of a fetch.
When is a linked list's O(1) insert actually O(1)? Only when you already hold the node. Reaching position k first costs k dependent cache misses.
Why is an array's O(n) shift often faster than a linked list's O(k) traversal? The shift is a sequential memmove the hardware loves; the traversal is serialized misses it can't predict.
Why is deque.appendleft fast without being slow to iterate? It's a linked list of blocks — contiguous within, linked between.
When would you genuinely choose a linked structure? When you hold positions and need stable references under mutation: LRU caches, allocator free lists, intrusive kernel lists.

The verdict

Default to the contiguous array — a Python list, a Java ArrayList, a Vec, a NumPy array. It's what your hardware was built for, and the prefetcher works for free.

Reach for a linked structure when you already hold the position you're mutating and need references to stay stable while the structure changes around them.

When you need both, use the blocked hybrid — a deque, a rope, a chunked list. That's the answer nearly every production system converges on, from collections.deque to a paged KV cache.

And when a measurement disagrees with the complexity table, the measurement is not wrong. Big-O just wasn't answering that question.

Every number in this post was executed on the recording machine before it was drawn: Intel Core i5-9400F @ 2.90 GHz, L1d 32 KB/core, L2 256 KB/core, L3 9 MB shared, 64-byte cache line, CPython 3.10.12.

Watch the full 14-minute episode for the memory-row diagrams, all four code walkthroughs, and the isolation experiment step by step — or the 2-minute version if you just want the shape of it.