Dynamic Arrays (How Python Lists Work)

A Python list is a dynamic array: elements stored back-to-back in memory (contiguous), able to grow as you append.

Core terms

• Element: one stored value. Index: its position, counting from 0.
• Length (size): how many elements are stored.
• Capacity: how many the reserved memory block could hold (usually larger than length; the spare slots absorb future appends).
• Big-O: how cost grows with size n. O(1) = constant, independent of n. O(n) = linear.

Why indexing is O(1)

• Contiguous layout means any element’s address is pure arithmetic: start_address + i * element_size.
• No searching, no walking. Same cost for 10 or 10 million elements.

Growth by doubling

• When length reaches capacity, an append must grow: reserve a bigger block, copy all n elements over (O(n)), then add the new value.
• The array multiplies capacity (classic model: double it; CPython grows ~1.125x).
• Multiplying means expensive copies happen rarely.

append: a    b    c    d    e
cap:    1    2    4    4    8
        [a] [ab] [abc_] [abcd] [abcde___]
             ^grow ^grow  ^free  ^grow

Amortized O(1) append

• A single append is usually O(1) (drop into a free slot); occasionally O(n) (grow).
• Amortized cost = total work over many operations, divided by the count.
• Copy costs at sizes 1 + 2 + 4 + ... + n < 2n, i.e. O(n) total for n appends -> constant each on average.
• Space is O(n) (up to ~2n reserved is still O(n)).

Complexity summary

Pitfalls

• Valid indices are 0 to len(xs)-1; xs[len(xs)] is an error.
• Do not add/remove while iterating; build a new list instead.
• insert(0, x) and pop(0) are O(n); use collections.deque for both ends.
• len(xs) is length, not capacity; you never manage capacity in Python.