Arrays: Contiguous Cells Read by Index

An array stores its elements in one unbroken block of memory, each in a cell of the same size, so the position of any element can be worked out from its index. This card covers that layout, why it makes reading by index O(1), and what it costs to insert, delete or search.

A game keeps a player's last six scores. Asking for the fourth score should not mean walking past the first three, and with an array it does not. Suppose the scores sit in cells that start at memory address 1000, where an address is the number that identifies one byte of memory, and each score takes four bytes. Cell i then starts at 1000 + i × 4. Indexes start at 0 because an index is a distance from the first cell: scores[0] sits at 1000 itself.

The trace reads three of the six cells; index marks the cell being read.

Reading or writing a cell by its index is O(1) in the worst case, because the arithmetic is the same whatever the index and however long the array. Two properties make it work: every cell is the same size, and the cells are contiguous, each starting where the last one ends. A Python list keeps that layout one step removed: each cell holds a reference, the address of an object stored elsewhere, so the cells stay the same size whatever the objects are.

Books shelved wherever there is room, each with a note saying where the next one is, have neither property. Finding the fourth means following three notes, so the cost of a read grows with its position. That is the shape of a linked list.

The layout also sets the price of every other operation, for an array of n elements whose size was fixed when it was created:

An array sits underneath many other structures because it finds the element at a position in one step. The price is paid when elements have to move.