Dict, List & Set CPython Internals & Complexity

Mastering Python core collections requires looking inside their C structs (PyDictObject, PyListObject, PySetObject). From compact dict layouts (PEP 468/469) to list over-allocation formulas and set dummy tombstone sentinels, understanding CPython data structure internals enables writing optimal $O(1)$ algorithms and avoiding performance anti-patterns.

This chapter details PyDictObject compact array architecture, PyListObject over-allocation math, PySetObject probing sentinels, and the Big-O Time/Space Complexity Matrix.

---

1. PyDictObject Compact Memory Layout (PEP 468 / PEP 469)

Since Python 3.6, CPython uses a Compact Dictionary design that separates hash lookup indices from payload entries:

CPython Compact Dictionary Memory Architecture:

Indices Array (dk_indices):  [ -1,  0, -1,  1, -1, -1,  2, -1 ]
                              (Sparse hash index array)
                                |   |         |
                                v   v         v
Entries Array (dk_entries):  [ [hash0, key0, val0],  <-- Entry 0
                               [hash1, key1, val1],  <-- Entry 1
                               [hash2, key2, val2] ] <-- Entry 2
                              (Dense contiguous array preserving insertion order!)

Key Architectural Benefits:

1. Preserves Insertion Order: Entries are appended sequentially into dk_entries, guaranteeing insertion order iteration by default.
2. 60% Memory Footprint Reduction: The sparse table is a small array of 1-byte integers (dk_indices), while large 24-byte entry structs (hash, key, val) are stored compactly in a dense array.

---

2. PyListObject Over-Allocation & Resize Math

A PyListObject is an array of PyObject* pointers managed by a growth formula:

PyListObject Growth Formula:

new_allocated = N + (N >> 3) + (N < 9 ? 3 : 6)

List Append Resizing Sequence:

Capacity:  [ Ptr0 | Ptr1 | Ptr2 | Ptr3 |  Unallocated Slots (Over-allocated)  ]
                                       ^
                                       |
                   Appending new item consumes next free slot in O(1) amortized time!
                   Resizes array ONLY when capacity is completely full!

• append(): $O(1)$ amortized time (consumes over-allocated slots).
• insert(0, item): $O(N)$ linear time! Forces CPython to shift every existing pointer in the array 1 slot right via memmove(). Use collections.deque for $O(1)$ double-ended pop/push operations.

---

3. PySetObject & Dummy Tombstone Sentinels (Py_Dummy)

PySetObject is a hash table containing keys without values.

Deletion Tombstones (Py_Dummy):

When an element is deleted from a set (s.remove(item)), CPython cannot simply wipe the hash slot to NULL because doing so would break perturbation probe chains for other colliding keys!

Instead, CPython replaces deleted keys with a special Py_Dummy tombstone sentinel. Tombstones allow open-addressing probes to pass through during lookups, but are recycled as empty slots during subsequent insertions.

---

4. Master Data Structure Complexity Matrix

Operation	list	dict	set	collections.deque
Search / Lookup	$O(N)$	$O(1)$ avg / $O(N)$ worst	$O(1)$ avg / $O(N)$ worst	$O(N)$
Append / Push Right	$O(1)$ amortized	$O(1)$ avg	$O(1)$ avg	$O(1)$
Prepend / Push Left	$O(N)$ Linear	N/A	N/A	$O(1)$ Constant
Delete Item	$O(N)$	$O(1)$ avg	$O(1)$ avg	$O(N)$ middle / $O(1)$ ends
Memory Layout	Contiguous Ptr Array	Compact Index/Entry	Open-Address Table	64-Elem Block Doubly-Linked

# ❌ ANTI-PATTERN: Using list.insert(0) for Queue Processing
queue = []
for item in data:
    queue.insert(0, item)  # BAD: O(N^2) quadratic performance due to array shifting!

# ✅ PRODUCTION PATTERN: O(1) Deque for Double-Ended Queues
from collections import deque

queue = deque()
for item in data:
    queue.appendleft(item)  # SAFE: Constant O(1) time allocation across block arrays!