Why does the standard library (Java/C#) not heavily feature Linked Lists? (Cache locality issues)
Linked Lists and Cache Locality
Although linked lists have attractive theoretical insertion and deletion complexity, real-world performance is often limited by poor cache locality, pointer chasing, object allocation overhead, and memory fragmentation. Modern CPUs process contiguous memory very efficiently, so array-backed collections frequently outperform linked lists even for workloads where both have similar asymptotic complexity.
- 1
Array-backed structures store elements close together in memory.
- 2
Linked-list nodes can be scattered throughout memory.
- 3
Pointer chasing creates dependent memory accesses and cache misses.
- 4
Object-based linked lists introduce per-node allocation and reference overhead.
- 5
Garbage collection can add additional overhead in managed runtimes.
- 6
Java and .NET do provide linked-list implementations, but they are specialized rather than being the default collection for most workloads.
- 7
Deque or array-backed collections are often better for practical queue and stack workloads.
Follow-up Questions
- What is CPU cache locality?
- Why can O(1) linked-list insertion still be slower than array operations?
- What collection would you use for a high-throughput queue?