Arrays and memory layout

Overview

Explains how arrays store elements contiguously and why indexing is constant time.

An array reserves a single block of memory. Because every element is the same size and the elements are adjacent, the address of element i is the base address plus i times the element size, which the processor computes in one step.

Contiguity also means that scanning an array in order is friendly to the CPU cache, which is one reason arrays often outperform linked structures in practice even when the asymptotic cost is the same.