An array stores a sequence of elements in contiguous memory locations. If each element occupies the same number of bytes, the address of element $i$ can be calculated directly from the base address and index.

Indexed access

This regular layout gives constant-time random access under the usual machine model:

$$\text{address}(i)=\text{base}+i\cdot\text{element size}.$$

Dynamic arrays

A dynamic array keeps a contiguous buffer with a current length and a capacity. When the buffer fills, it can allocate a larger region and move the existing elements.

Appending is therefore occasionally expensive, but geometric growth makes repeated append operations have amortized constant cost.

Insertion and deletion

Inserting or deleting near the middle generally requires shifting later elements, giving linear work in the number of moved elements.

Why layout matters

Contiguous storage also gives neighboring elements neighboring addresses. Sequential traversal can therefore make effective use of cache lines and hardware prefetching.

Arrays are both an abstract sequence structure and a concrete memory layout, which makes them central to later performance comparisons.