Arrays, Lists, and Memory Layout

Memory Layout & Arrays

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

An array stores elements in a single contiguous block of memory. Because elements are adjacent and equally sized, the address of element $i$ is computed directly as $\text{base address} + (i \times \text{element size})$, giving $O(1)$ random access to jump to any index instantly.

The cost is rigidity: inserting or removing in the middle requires shifting all following elements, which takes $O(n)$ time, and a fixed array cannot grow beyond its allocated size.

Linked Lists & Trade-offs

A linked list stores each element in a separate node holding a pointer to the next node. Nodes sit anywhere in memory; the chain is held together by pointers.

Common pitfall: assuming linked lists are faster because insertion is $O(1)$. That $O(1)$ insertion assumes you already hold the position; finding it takes $O(n)$, and arrays are far more cache-friendly.