Arrays and Lists

Sequences of Values

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.

A near-universal convention trips up newcomers: most languages use zero-based indexing — the first element is at index 0, the second at 1, and the last of an $n$-element array at index n - 1 (not n). So a list of length 5 has valid indices 0, 1, 2, 3, 4. Accessing index 5 (or n) is out of bounds — an error, and a frequent source of the off-by-one bugs from the loops lesson.

Common operations on lists:

• Access / update a[i] — read or overwrite the element at position i.
• Length — the number of elements.
• Append / insert / remove — add or delete elements (with different costs depending on where).
• Traverse — visit every element, usually with a loop, to sum, search, or transform.

Arrays pair perfectly with loops: iterating an index from 0 to n - 1 visits each element exactly once. Many mathematical objects — a vector, a sequence, a row of data — are naturally represented as arrays, so array manipulation is the bread and butter of turning mathematics into code. Multi-dimensional arrays (arrays of arrays) represent matrices and grids, indexed by row and column.

Common pitfall: forgetting zero-based indexing and going out of bounds. In most languages the first element is a[0] and the last is a[n-1], so a loop or access that reaches index n is one past the end — an out-of-bounds error. Off-by-one mistakes at the array boundary (using n instead of n-1, or starting at 1 instead of 0) are among the most common bugs; always mind that valid indices run 0 to n-1.