09 / 16

Why does the standard library (Java/C#) not heavily feature Linked Lists? (Cache locality issues)

Linked Lists and Cache Locality

  1. 1

    Array-backed structures store elements close together in memory.

  2. 2

    Linked-list nodes can be scattered throughout memory.

  3. 3

    Pointer chasing creates dependent memory accesses and cache misses.

  4. 4

    Object-based linked lists introduce per-node allocation and reference overhead.

  5. 5

    Garbage collection can add additional overhead in managed runtimes.

  6. 6

    Java and .NET do provide linked-list implementations, but they are specialized rather than being the default collection for most workloads.

  7. 7

    Deque or array-backed collections are often better for practical queue and stack workloads.

Difficulty: 4/10

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?