Arrays and Lists

Collections and Indexed Access

Programs rarely handle one value at a time; they process collections. An array (or list) stores an ordered sequence of values in a single named structure, accessed by index: a position number.

The defining feature is indexed access: element $a[i]$ is retrieved directly by its position in constant time, without scanning from the start. Multi-dimensional arrays (arrays of arrays) represent matrices and grids, indexed by row and column.

Zero-Based Indexing

Most languages use zero-based indexing: the first element is at index 0, and the last of an $n$-element array is at index $n - 1$ (not $n$).

Accessing index $n$ is out of bounds: an error, and a frequent source of off-by-one bugs. For a list of length 5, valid indices are 0, 1, 2, 3, 4.

Arrays pair perfectly with loops: iterating an index from 0 to $n - 1$ visits each element exactly once.

Common pitfall: Forgetting zero-based indexing and going out of bounds. Using $n$ instead of $n-1$, or starting at 1 instead of 0, triggers an out-of-bounds error.