Contiguous vs. Linked Memory Layout¶

The fundamental choice between storing elements in adjacent memory locations (enabling arithmetic addressing) versus storing them via pointers (enabling flexible topology) underlies all data structure design.

Tension Addressed¶

Access Speed vs. Modification Speed

Recognizable As¶

Arrays/vectors vs. linked lists in any language; buffer-based vs. node-based implementations; "growable array" patterns that amortize reallocation

Canonical Sources¶

Knuth, The Art of Computer Programming Vol. 1 (1968); Stroustrup, "Why you should avoid Linked Lists" talk (2012)

Transfers To¶

Memory Management (allocation strategies), Database Design (row stores vs. column stores), Network Protocols (packet buffers vs. linked frames)

The cache hierarchy of modern processors dramatically amplifies this distinction - contiguous structures benefit from prefetching while pointer-chasing incurs cache misses. This physical reality makes the choice consequential beyond theoretical complexity.