Why arrays beat linked lists in practice

Arrays are faster than linked lists in most real programs because they store elements next to each other in memory, which lets the CPU cache and prefetcher do their jobs. Linked lists scatter nodes across the heap, so every step of a traversal risks a cache miss that costs more than a hundred arithmetic instructions.

That is the whole answer, compressed. The rest of this essay is the argument behind it: why adjacency matters so much on modern hardware, what the benchmarks actually look like, and the honest list of situations where a linked list is still the right call. If you have ever chosen a data structure from a Big-O table and been surprised by the profiler, this one is for you.

Why are arrays faster than linked lists?

Because memory does not arrive one value at a time. It arrives by the pallet. When your program reads a single 8-byte integer, the CPU does not fetch 8 bytes from RAM; it fetches an entire cache line, typically 64 bytes, and keeps it in a small, fast cache close to the core. Think of RAM as a warehouse that refuses to ship individual items. Ask for one screw and a full pallet lands on your dock. If the next seven things you need are on that same pallet, they are effectively free. If each of them sits in a different aisle of the warehouse, you pay full shipping every single time.

An array is a request list sorted by aisle. Eight 8-byte elements share each 64-byte line, so a linear scan pays for one memory fetch and gets seven successors at cache speed. Better still, the access pattern is predictable, and the hardware prefetcher notices. It starts pulling the next lines before you ask for them, hiding the latency almost completely. A traversal of a large array runs close to the speed the memory bus allows.

A linked list is the same request list in shuffled order. Each node was allocated separately, wherever the allocator found room, and the address of node i+1 is stored inside node i. The CPU cannot begin loading the next node until the current one arrives, because it does not know the address yet. This is called pointer chasing, and it defeats both the cache and the prefetcher at once. Main-memory latency is on the order of 100 nanoseconds; a modern core can execute hundreds of instructions in that time. A list traversal can spend the overwhelming majority of its wall-clock time waiting, not computing.

Notice that none of this appears in the complexity analysis. Both traversals are O(n). The contract is satisfied; the constant factor is not, and the constant factor is a factor of ten or more. I wrote at length about this gap in Complexity is a contract: Big-O tells you how cost scales, and says nothing about what one step costs.

But isn't linked list insertion O(1)?

Yes, and the claim is narrower than it looks: insertion is O(1) only after you are already holding the insertion point. Read the fine print on that contract. To insert in the middle of a list you must first walk to the position, which is an O(n) pointer chase of exactly the expensive kind described above. The array you were trying to beat does its O(n) insertion by shifting elements, but the shift is a sequential sweep over contiguous memory, the pattern hardware loves most. In practice, memmove on a few thousand elements routinely beats a cold-cache walk over the same count of list nodes.

The list also pays two quieter taxes. First, space: every node carries one or two pointers of overhead, so a doubly linked list of 8-byte values spends two thirds of its memory on structure rather than data, which means fewer useful elements fit in cache. Second, allocation: one heap allocation per node costs time on insert, costs time again in the allocator's bookkeeping, and fragments the heap so future traversals scatter even further. A dynamic array amortises one allocation across many appends, which is why its append is O(1) amortised and, unusually, the practical performance is even better than the contract suggests.

How much faster are arrays in practice?

Enough that the difference is visible without a microscope. The sketch below shows the shape of results I get benchmarking 1,000,000 8-byte integers in C++ (vector vs. a node-per-element doubly linked list) on a typical laptop core. Treat the numbers as ratios, not gospel: your hardware, allocator, and element size will move them, and you should rerun them yourself before quoting them in a design review.

Two rows deserve attention. The fragmented-traversal row shows the same list twice as its nodes age: after churn, allocation order stops matching traversal order and the miss rate climbs. Data structures do not just have costs; they have costs that degrade. And the held-iterator row is the list's one genuine victory, which brings us to the fair part of the comparison.

When do linked lists actually win?

They win when you never search and always splice. If an external structure hands you the node directly, so no walk is needed, then O(1) insertion and removal is real and an array cannot match it. The classic example is an LRU cache: a hash map stores pointers straight into a doubly linked recency list, and every touch is an unlink and a relink, two pointer swaps with no traversal anywhere. Operating system schedulers and allocator free lists use the same trick, often with intrusive nodes embedded in objects that already exist, which also cancels the allocation tax.

Lists also win when elements must never move. A vector reallocates as it grows and invalidates every pointer into it; a list node stays at one address for its whole life. If other subsystems hold long-lived references into the collection, stability can outrank speed.

What should you default to? An array, without much anguish. Measure before reaching for anything else. My rule after years of writing both: the linked list is a specialist tool you select for splice-heavy, search-free workloads, not a general-purpose sequence. The interview canon agrees with the hardware here; the list problems worth practising, like reversing a list in place, are really tests of pointer discipline, not endorsements of the structure.

Frequently asked questions

Should I still learn linked lists for coding interviews?

Yes. Interviewers use them to test whether you can mutate pointers without losing nodes, a skill that transfers to trees and graphs. Knowing when not to use one in production is a separate, equally examinable judgement.

Do dynamic arrays waste memory when they grow?

Some. A growth factor of 2 leaves up to half the buffer unused in the worst moment, and a quarter on average. A doubly linked list of small values spends more than that on pointers alone, so the array usually still comes out ahead.

Is a linked list ever faster for iteration?

Practically never. Iteration is the list's worst case because every step is a dependent load. If your workload is mostly iteration, the array is not just faster; it is faster by an order of magnitude or more.

The deeper lesson is that data structure choice is a hardware question wearing an algorithms costume. Start with the Arrays and Sequences module to see what contiguity buys, then read the Linked Lists module for the pointer patterns that make the specialist cases work.