Dynamic Arrays
Your shelf is full and another book arrives. You cannot stretch the shelf, so you buy one twice the size and carry every book across. It is a big effort — but you only do it occasionally, so averaged over many books it stays cheap.
Outgrowing the shelf
step 1 / 30A shelf with room for 4 books, holding 0. Capacity and length are different numbers.
How the growth trick actually works
A dynamic array keeps two numbers: length (slots used) and capacity (slots allocated). Append fits? O(1). Array full? Allocate a bigger block, copy everything across — O(n) for that one append — then appends are cheap again. Because each expensive copy buys proportionally many cheap appends, the AVERAGE stays O(1): that is amortized analysis, formalised in Module 4.
CPython list growth — the real numbers
| fact | value | consequence |
|---|---|---|
| growth factor | ~1.125× (+ constant) | gentler than doubling — wastes less memory, copies a bit more often |
| empty list | 56 bytes, capacity 0 | the first append always allocates |
| append | O(1) amortized | list.append is THE idiomatic accumulator |
| pop() from end | O(1) | shrinks capacity only when 1/2 empty |
| pop(0) / insert(0, x) | O(n) | front operations shift everything — use collections.deque instead |
| preallocating | [0] * n | one allocation instead of n growth steps |
See it yourself
import sys
xs = []
last = 0
for i in range(60):
xs.append(i)
size = sys.getsizeof(xs)
if size != last: # capacity jumped -> a copy happened
print(f"len={len(xs):2} bytes={size}")
last = size
# jumps land at 1, 5, 9, 17, 26, 36, 47... — the ~1.125x staircase# CPython list append, in essence:
def append(self, v):
if self.length == self.capacity:
self.capacity = self.capacity * 2 # O(n) copy
self.buf = self.buf + [None] * self.capacity
self.buf[self.length] = v # O(1)
self.length += 1
# amortised O(1) because capacity DOUBLESAmortised cost of appending to a dynamic array?
append_all(arr, items) returns a NEW list with items appended — the "grow by copying" a dynamic array does when full.