Inside Python Lists
Dynamic arrays.
A Python list looks simple, but there's a clever structure underneath, called a dynamic array. Knowing how it works tells you exactly which list operations are fast, and which ones are slow.

- Lists look simple
- A dynamic array underneath
- Know what's fast, and what's slow
An array in memory
An array is a row of boxes, side by side in memory, each one numbered from zero. Because the boxes are the same size and next to each other, the computer can jump straight to box number five, without looking at the others. That's why indexing is O of one. A dynamic array also keeps some spare empty boxes at the end, ready for new items.
Watching a list grow
Sys dot get size of shows how many bytes a list uses. We append items one at a time, and print the size only when it changes. Run it. The size doesn't grow with every append. It jumps in steps. Each time the spare boxes run out, Python moves the list to a bigger block of memory, with room to spare. Because that's rare, append is O of one on average.
import sys
items = []
last = sys.getsizeof(items)
print(f"{len(items):>2} items: {last} bytes")
for i in range(20):
items.append(i)
size = sys.getsizeof(items)
if size != last:
print(f"{len(items):>2} items: {size} bytes")
last = size0 items: 56 bytes 1 items: 88 bytes 5 items: 120 bytes 9 items: 184 bytes 17 items: 248 bytes
Summary
A list is a dynamic array, a row of boxes with spare room at the end. Indexing is O of one, and append is O of one on average. Next, the cost of every common list operation.
Key takeaways- Boxes side by side
- Indexing is O(1)
- append grows in jumps