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

📺 Prefer to watch? 90-second YouTube Short · 💬 Telegram Originally published on software-engineer-blog.com. 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 whyappendleft beatslist.insert(0, x) by 477×, and it's the shape most "linked list" wins in production actually take. - Java's ArrayList vsLinkedList : the same story, and the reasonLinkedList is near-universally discouraged in modern Java style guides. - NumPy arrays are genuinely contiguous typed memory - the reason