Linked List
A sequence of nodes each pointing to the next, allowing efficient insertion without contiguous memory.
Definition
A linked list stores elements in nodes, each holding a value and a reference to the next node. Unlike an array, its elements need not be contiguous in memory, so insertion and deletion are cheap once the position is known.
Modern hardware often favors contiguous arrays even for insertion-heavy workloads, because pointer chasing defeats the cache and prefetcher. This is a good example of how theoretical operation counts can mislead when memory access patterns dominate real performance.
The linked list is a teaching classic because it crisply illustrates pointer manipulation and the trade-off between arrays and pointer-based structures. In modern practice, however, contiguous arrays often win even for insertion-heavy work, because chasing pointers scattered through memory defeats the cache. This gap between operation counts and real performance is a recurring lesson: asymptotic analysis guides design, but memory behavior frequently decides the outcome.
Trade-offs
- Fast insert/delete at a known position: O(1).
- No random access; reaching index k costs O(k).
- Extra memory per node for the pointer.
- Poorer cache behavior than arrays.
Why it matters
Linked lists illustrate the fundamental trade-off between arrays (fast access, costly insertion) and pointer-based structures (cheap insertion, slow access). They underlie stacks, queues, and more complex structures, though modern hardware often favors arrays for their cache locality.
Fusion connection
Linked structures manage dynamic particle lists in simulations where particles are frequently created and removed, such as models of ionization.