Arrays Beat Linked Lists in Practice Due to CPU Cache Behavior
Computer science courses teach that linked lists outperform arrays for insertions, citing O(1) versus O(n) complexity, but real-world benchmarks tell a different story. A test iterating over 10 million integers showed a contiguous array completing in 0.53 seconds compared to 1.53 seconds for a linked list — nearly three times slower despite identical operation counts. The gap stems from how modern CPUs handle memory: a single 64-byte cache line fetch delivers eight array elements at once, while each linked list node requires a separate memory trip. This phenomenon, known as pointer chasing, forces the processor to wait for the current node's data before it can determine the next memory address, eliminating any chance of prefetching. As a result, cache efficiency — not algorithmic complexity — is often the dominant factor in real hardware performance.