Mutable Collections: list, dict, set & Pointer Arrays
1Concept
Python lists are variable-length arrays of object pointers (`PyObject**`). When capacity is exceeded, CPython over-allocates extra memory using the formula `new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6) + newsize` to ensure amortized O(1) appends.
2Architecture Diagram
List Growth Pattern: Length: 0 -> Alloc: 0 | Length: 1 -> Alloc: 4 | Length: 5 -> Alloc: 8 | Length: 9 -> Alloc: 16
3Code Example
Python 3.12
import sys
elements = []
print("Length -> Allocated Bytes")
for i in range(10):
elements.append(i)
print(f"Len: {len(elements):2d} -> {sys.getsizeof(elements)} bytes")4Expected Output
Length -> Allocated Bytes Len: 1 -> 88 bytes Len: 2 -> 88 bytes Len: 3 -> 88 bytes Len: 4 -> 88 bytes Len: 5 -> 120 bytes Len: 6 -> 120 bytes Len: 7 -> 120 bytes Len: 8 -> 120 bytes Len: 9 -> 184 bytes Len: 10 -> 184 bytes
5Key Takeaways
- ✓Python lists over-allocate memory to achieve O(1) amortized append operations.
- ✓Dicts in Python 3.7+ preserve insertion order using a split-table indices layout.
- ✓Sets use open addressing hash tables without storing values, offering O(1) lookup.