Arrays: one block of memory

You keep a million scores in a list. Asking for score number 700,000 comes back at once, as fast as asking for the first. Putting a new score at the front of the list takes about a million moves. Adding one at the end is quick again, even though the list sometimes has to move house to fit it.

All three come from one fact: an array keeps its elements side by side in a single block of memory. Once you can see that block, you can tell which operations are cheap and which are not, and why.

index

An element's position, counted from 0. A[0] is the first element and A[n − 1] the last of n.

contiguous

The cells sit next to each other in memory, all the same size, with no gaps between elements.

length and capacity

Length is how many elements the array holds; capacity is how many cells its block has. The cells past the length are spare.

dynamic array

An array that grows when it is full by moving to a bigger block, like a Python list, a Java ArrayList or a C++ vector.

amortised cost

The cost per operation averaged over a long run of them, so a rare expensive step is shared by the many cheap ones.

This array holds 7, 23, 4, 42 and 15 in a block of 8 cells. Read an element, then insert one at the front, and watch how many cells each operation touches.

Reading is cheap because of where the cells are. Each cell is the same size, so cell i starts at base + i × cellSize. The array works out that address and reads that one cell, whether i is 3 or 3,000,000. Inserting is expensive for the same reason: the elements must stay side by side, so making room at index i means moving every element from i to the end.

The end has one catch. When length reaches capacity there is no spare cell, and the memory just after the block may belong to something else, so the array can't simply stretch. It allocates a block twice the size, copies every element across and frees the old one.

Before each operation, predict how much work it does: how many cells a get reads, how many elements an insert or delete shifts, and whether an append must grow the array first. Try a get, an insert near the front, a delete and an append.

Here is insert-at-the-front written out. It makes room with one spare cell at the end, then walks backwards, copying each element one place to the right, and finally writes the new value into cell 0.

def insert_front(a, x):
    a.append(None)
    for j in range(len(a) - 1, 0, -1):
        a[j] = a[j - 1]
    a[0] = x

scores = [7, 23, 4, 42]
insert_front(scores, 99)
print(scores)

Appending is different. Most appends drop the value into a spare cell, and only an append into a full array copies everything. Because the block doubles, each copy buys as many cheap appends as it moved elements.

• An array is one block of equal-sized, side-by-side cells, so A[i] lives at base + i × cellSize: get and set are O(1).
• Inserting or deleting at index i shifts every later element: O(n − i). The front is the worst place, the end the best.
• A full dynamic array grows by moving to a block twice the size. That append is O(n), but append is O(1) amortised.
• Length is what you use; capacity is what you have. The spare cells are what make most appends cheap.
• Next: stacks and queues, built on arrays and rings, and linked lists, which give up O(1) indexing so that inserting next to a node you already hold is cheap. To try more operations yourself, open the array visualiser.