Fragmentation (The Original Sin)
Every computer science student is taught the same lie:
"Arrays have O(N) insertion. Linked Lists have O(1) insertion."
This statement assumes that finding the location is free. It assumes that memory is a uniform void where all bytes are equidistant.
The machine disagrees.
The Original Sin
A Linked List is a collection of nodes scattered across the heap. To traverse it, you must read a pointer, wait for the data, finding the next address, and jump again.
This is a Pointer Chase. It is the single slowest thing a CPU can do.
A linked list forces strict serialization: you cannot load node N+1 until node N arrives. The CPU cannot overlap work.
The Hidden Tax: Allocation
A Linked List node does not appear for free. It is allocated from the Heap.
Heap allocation is not a pointer increment. It is a negotiated transaction:
- Search free lists
- Update allocator metadata
- Possibly acquire locks
- Pollute caches with allocator state
Even if insertion is logically O(1), its physical cost is orders of magnitude higher than shifting elements inside an array.
Notice the "Cycles" count. The Array is predicted by hardware. The List is a series of cache misses. The difference is often 200x.
The Four Lenses
Let's audit the Linked List.
- Cache Locality (Catastrophic): Every node is likely on a different cache line. You pull in 64 bytes just to read 8 bytes (the next pointer). You waste 87% of your bandwidth.
- TLB Pressure (High): Nodes are scattered across pages. You will thrash the TLB, causing page walks for almost every step.
- Prefetching (Failure): The hardware prefetcher sees random addresses. It cannot help you. It turns off.
- Coherence (Safe but Slow): Lists serialize access. Even without locks, pointer chasing enforces a single-file line through memory.
Why do CPUs hate Linked Lists so much?
Because Linked Lists violate every optimization the CPU depends on: locality, predictability, parallelism, and batching. Arrays let the CPU guess, fetch ahead, and overlap work. Lists force the CPU to wait at every step.
Is "O(1) Insertion" ever true?
Only if you already have the pointer to the location. If you have to search for the spot, it is O(N). And traversing N nodes in a list is hundreds of times slower than traversing N slots in an array.
Why do we use Lists then?
For Intrusive Lists (where the node is the data) or when we must never invalidate pointers (Arrays move data on resize; Lists do not). They are for structural stability, not performance.
What programmers usually get wrong here
They verify their code on small lists (N=100) where everything fits in L1 cache. In production (N=1,000,000), the cache thrashing brings the server to its knees.
A linked list is not slow because it is O(N). It is slow because it forces the CPU to behave like it is O(1) at a time.
This works — until we need to predict. Arrays are predictable. Lists are random. But randomness has a use. Sometimes we accept randomness — not because it is fast, but because it gives us probability instead of certainty.