Lists Foundations & Memory Mechanics
Master list allocation, reference aliasing, mutation quirks, slicing edge cases, sorting stability, and in-place operations.
Theoretical Mechanics & Memory Architecture
Python lists (PyListObject) are dynamic arrays implemented as contiguous blocks of 64-bit pointers referencing arbitrary PyObject structs allocated across the heap. Rather than resizing the buffer on every append, CPython allocates excess capacity using the geometric growth formula: newsize + (newsize >> 3) + 6. This amortizes append operations to O(1) time complexity, whereas arbitrary insertions or deletions require O(N) memory relocations via the C standard library memmove function.
Because a PyListObject stores memory addresses rather than serialized values, elements can be heterogeneous. When performing slice assignment or slicing (lst[a:b]), CPython allocates a new PyListObject header and copies pointer references rather than duplicating the underlying objects. Mutating a mutable child object within a shallow copy reflects across both references.
Constructing two-dimensional grids with [[0] * 3] * 3 creates an outer list populated with three identical pointer references pointing to the exact same inner list on the heap. Mutating grid[0][0] = 1 updates every row simultaneously. Multi-dimensional matrices must always be instantiated via comprehension: [[0 for _ in range(3)] for _ in range(3)].
Interactive Dry-Run Execution Workspace
The Nested List Multiplication Alias Trap
Trace CPython execution step-by-step and deduce the exact stdout string emitted by this snippet.
a = [[1] * 2] * 2
a[0][0] = 9
print(a)Frequently Asked Questions on Lists Foundations & Memory Mechanics
Why does [[0] * 3] * 3 cause unintended mutations across every row in a grid?
The repetition operator (*) duplicates object references, not object instances. The outer list receives three references pointing to the exact same inner list in heap memory. Modifying any nested element through one row mutates the shared underlying list.
How does CPython achieve amortized O(1) time complexity for list append operations?
CPython allocates extra buffer slots beyond the requested length using geometric growth. Appends fill pre-allocated empty pointer slots in O(1) time. Expensive reallocations and memory copies only occur periodically when all over-allocated slots are exhausted.
What is the memory and performance difference between list.sort() and sorted()?
list.sort() operates in place directly on the PyListObject pointer buffer with O(1) auxiliary space using Timsort. In contrast, sorted() instantiates a brand new PyListObject and copies all elements, incurring O(N) additional memory allocation.