Arrays, Lists, and Memory Layout

Two Ways to Store a Sequence

The two fundamental sequence structures differ in one thing — memory layout — and everything about their performance follows from it.

An array stores elements in a single contiguous block of memory. Because the elements are adjacent and equally sized, the address of element $i$ is computed directly (base address + $i \times$ element size), giving $O(1)$ random access — jump to any index instantly. The cost is rigidity: inserting or removing in the middle requires shifting all following elements, which is $O(n)$, and a fixed array cannot grow beyond its allocated size.

A linked list stores each element in a separate node that also holds a pointer to the next node. The nodes may sit anywhere in memory; the chain is held together by the pointers. This makes insertion or removal at a known position $O(1)$ — just relink a couple of pointers, no shifting — and the list can grow freely. The cost is that there is no direct indexing: to reach element $i$ you must follow the chain from the start, which is $O(n)$ access.

The choice is a direct trade-off: arrays for fast indexing and cache-friendly scanning; linked lists for cheap insertion/removal and flexible size.

Common pitfall: assuming linked lists are always "faster" because insertion is $O(1)$. That $O(1)$ insertion assumes you already hold the position; finding it is still $O(n)$, and arrays' contiguous layout makes scanning far more cache-friendly in practice. Neither structure is universally better — it depends on which operations dominate.