Memory and dynamic arrays

An array is a row of equal-sized slots, side by side in memory. That one fact explains why reading any position is instant, why inserting at the front is slow, and why appending is usually fast.

Slots side by side

Computer memory is a long row of numbered bytes. The number of a byte is its address. An array takes one unbroken stretch of that row and splits it into slots of the same size. If the array starts at address s and each slot is w bytes, then slot i starts at:

address of a[i] = s + i × w

One multiplication and one addition find any slot. The computer does not walk past the slots before it. That is why a[i] is O(1) for every i. It is also why indexes start at 0: index 0 is the start itself.

What a Python list holds

A Python list can hold values of different types and sizes: [3, "BCT", [1, 2]]. Its slots cannot all be the size of the largest value. So each slot holds a reference: the address of the value, which is stored somewhere else. All references are the same size, so the address formula still works.

Two things follow:

• Reading a[i] takes two hops: one to the slot, and one to the value. It is still O(1).
• Copying a list copies the references, not the values. b = a[:] makes a new list whose slots point at the same objects. This is called a shallow copy.

Inserting and deleting in the middle

The slots must stay side by side, with no gaps. To insert at index i, every value from i to the end moves one slot to the right first. To delete at index i, every later value moves one slot to the left. Step through the second version of the figure.

So a.insert(i, x), a.pop(i) and del a[i] cost O(n − i). At the end of the list they are O(1); at the front they are O(n).

a.append(x)       # O(1) amortised
a.pop()           # O(1)
a.insert(0, x)    # O(n): everything moves right
a.pop(0)          # O(n): everything moves left

If you need to add or remove at both ends, use collections.deque (BIGO-8). If you need to insert in the middle often, an array is the wrong structure, and the LINK and BALT stations offer others.

Dynamic arrays

A plain array has a fixed size. A Python list is a dynamic array: it keeps some spare slots at the end, and when they run out it moves to a bigger block. BIGO-7 proves that if the block grows by a fixed factor, appending costs O(1) on average.

You can see the spare room with sys.getsizeof(a), which grows in jumps rather than by one slot at a time. If you know the final size in advance, [0] * n makes the whole list in one step.