Python Data Structures

Post three goes under the hood. The cover frames the promise: the speed and the quirks of Python's containers stop being magic once you see the two underlying mechanisms — the resizable array and the hash table. Almost every behavior you'll ever observe traces back to one of those two implementations.

The aim is to replace memorized rules ('append is fast, insert is slow') with the mechanical reason behind them, so you can predict behavior you've never specifically learned.

A list is implemented as a contiguous array of pointers — references to objects living elsewhere on the heap. The array itself holds only addresses, all the same size, laid out back to back. That uniformity is why indexing is instant: the location of element i is just base address plus i times the pointer size, a single arithmetic step.

This also explains why a list can hold mixed types: each slot is just a pointer, indifferent to what it points at. The values' actual sizes don't affect the array's layout at all.

The stack diagram visualizes the list as slots holding pointers, with extra capacity at the end. Showing the spare slots explicitly is the key to the next slide: that headroom is what makes append cheap most of the time. When the spare slots run out, Python allocates a larger block and copies the pointers over — an occasional expensive step amortized across many cheap ones.

Seeing pointers rather than values in the slots also clarifies that the list's memory cost is the pointers plus the objects, which matters when reasoning about large collections.

Append is amortized O(1) because it usually drops a pointer into an already-allocated spare slot; the occasional resize-and-copy averages out to constant time. Insert at the front is fundamentally different: every existing pointer must shift up one position to make room, which is linear in the list's length. pop(0) has the same problem in reverse.

When a workload needs fast operations at both ends — a queue, a sliding window — collections.deque is the right tool, implemented to give O(1) appends and pops on either side.

This snippet makes the asymmetry tangible. append and insert(0) look like sibling operations but have completely different costs, and deque's appendleft shows the alternative. Running this on a large list, the front insert is visibly slower while the deque stays flat.

The lesson generalizes: when you catch yourself doing repeated insert(0) or pop(0) on a list, that's the signal to switch containers. The behavior is dictated by the array layout, not by anything you can tune away.

Dicts and sets are both hash tables. A hash table stores entries in an array of slots, and the slot for a key is chosen by computing hash(key) and reducing it modulo the table size. To find a key later, Python recomputes the hash and goes straight to that slot — no scanning involved. That direct addressing is the source of the average O(1) lookup.

A set is essentially the same machinery as a dict but storing only keys, no associated values. Understanding them as one mechanism explains why they share the same performance profile and the same hashability requirement.

The pipeline diagram traces a key through the hash-table machinery: the key is hashed into a large integer, that integer is reduced modulo the table size to pick a slot, and the value is stored there. Retrieval runs the same path and lands in the same slot. Visualizing this makes 'O(1) lookup' concrete rather than a claimed fact.

It also previews the two complications: different keys can land in the same slot (collisions), and the key must produce a stable hash — which is why mutability matters for keys.

This snippet demonstrates the hashability rule directly. A tuple, being immutable, has a stable hash and works fine as a dict key. A list is mutable — its contents can change, which would change its hash and break the table — so Python refuses to hash it, raising 'unhashable type: list.'

Catching the TypeError and printing it turns an abstract rule into an observed behavior. The practical upshot: when you need a composite key, reach for a tuple, never a list.

Collisions are inevitable because many possible keys map to a finite number of slots. Python resolves them with probing — checking nearby slots until it finds the right entry or an empty slot — so lookups stay correct, with cost staying near-constant as long as the table isn't too full. Python grows the table to keep it sparse.

Order is the other consequence to internalize: sets track no order at all, while dicts have preserved insertion order since 3.7 as a language guarantee. Even so, dict access is by key, not position — the order is for iteration, not indexing.

The tips consolidate the mechanics into predictive rules. Because a list is an array of pointers, indexing is O(1) but front insertion is O(n). Because dicts and sets are hash tables, lookup is O(1) and keys must be hashable. Because hash tables place entries by hash, sets are unordered while dicts merely preserve insertion order.

The value of learning the mechanism rather than the rules is that you can now reason about operations you were never explicitly taught — the implementation tells you what will be cheap.

The closing caution refines the O(1) claim so you don't overtrust it. Hash-table lookup is constant on average, but adversarial keys or heavy collisions can degrade it, and — more practically — mutating an object after using it as a key corrupts the table, because its hash no longer points to where it was stored.

The rule that protects you is simple: keep keys immutable. Honoring it preserves both the correctness of the table and the performance guarantee you're relying on.

The CTA hands off to the hands-on post. With the mechanics understood, it's time to build muscle memory — the everyday operations and patterns on each container. Post four is deliberately code-heavy so the syntax becomes automatic rather than something you look up each time.