# Data Structures

## 1. The Four Built-in Containers

| Type | Ordered | Mutable | Duplicates | Indexed by |
|---|---|---|---|---|
| `list` | Yes | Yes | Yes | integer position |
| `tuple` | Yes | No | Yes | integer position |
| `dict` | Yes (insertion) | Yes | keys unique | key (hashable) |
| `set` | No (but stable per-run) | Yes | No | — (membership only) |

```python
lst = [1, 2, 3]
tup = (1, 2, 3)
d = {"a": 1, "b": 2}
s = {1, 2, 3}
```

## 2. Lists — Dynamic Arrays

```python
nums = [3, 1, 2]
nums.append(4)          # O(1) amortized
nums.insert(0, 0)       # O(n) — shifts every element right
nums.pop()               # O(1) — removes/returns the LAST element
nums.pop(0)               # O(n) — removes the FIRST element, shifts everything left
nums.sort()               # O(n log n), in-place, stable (Timsort)
sorted(nums)               # returns a NEW sorted list, leaves nums untouched
nums[1:3]                  # slicing returns a new list (shallow copy of that range)
```

Appending at the end and popping from the end are cheap. Inserting or removing at the front (or anywhere but the end) is expensive because every subsequent element has to shift.

## 3. Tuples — Immutable, Fixed-Size Sequences

```python
point = (3, 4)
x, y = point            # unpacking
point[0] = 5              # TypeError — tuples don't support item assignment

def min_max(values):
    return min(values), max(values)   # implicitly builds and returns a tuple

lo, hi = min_max([3, 1, 4, 1, 5])
```

Tuples are commonly used for fixed-shape records (a coordinate, a database row, multiple return values) and as dict keys — since they're hashable (as long as every element inside is also hashable), unlike lists.

## 4. Dicts — Hash Maps with Insertion Order

```python
config = {"host": "localhost", "port": 8080}
config["port"]              # 8080 — O(1) average lookup
config.get("timeout", 30)    # 30 — default if key missing, doesn't raise
config.setdefault("retries", 3)  # sets AND returns; no-op if key exists

for key, value in config.items():
    print(key, value)   # iterates in INSERTION order (guaranteed since 3.7)

config.pop("port")           # removes and returns the value
"host" in config              # O(1) average — key membership test
```

`dict[key]` raises `KeyError` if the key is absent; `.get()` never raises.

## 5. Sets — Unique Elements, Fast Membership

```python
seen = {1, 2, 3}
seen.add(4)
seen.discard(99)          # no error even if 99 isn't present (.remove() WOULD raise)

a = {1, 2, 3}
b = {2, 3, 4}
a | b   # union: {1, 2, 3, 4}
a & b   # intersection: {2, 3}
a - b   # difference: {1}
a ^ b   # symmetric difference: {1, 4}
```

Sets are the right tool whenever the question is "is X present?" or "what's common/different between these groups?" — membership testing is O(1) average, versus O(n) for a list.

## 6. Choosing the Right Structure

| Need | Use |
|---|---|
| Ordered, duplicates allowed, will change size | `list` |
| Fixed-shape record, or a hashable dict key | `tuple` |
| Key → value lookups | `dict` |
| Unique items, fast membership tests, set algebra | `set` |
| Need both O(1) push AND O(1) pop from the *front* | `collections.deque`, not `list` |

## 7. `collections.deque` — When Lists Aren't Enough

```python
from collections import deque

q = deque([1, 2, 3])
q.appendleft(0)   # O(1) — a plain list.insert(0, ...) would be O(n)
q.popleft()        # O(1)
q.append(4)        # O(1)
```

`deque` is implemented as a doubly-linked list of fixed-size blocks, giving O(1) operations at *both* ends — the trade-off is O(n) random access by index, unlike a `list`'s O(1) indexing.

## 8. Under the Hood: How CPython Actually Implements These

### `list`: an over-allocated array of pointers

A `list` is a `PyVarObject` holding a pointer to a contiguous array of `PyObject*` — not the objects themselves, pointers to them (which is why a Python list can hold mixed types with no fixed element size). Critically, the array's **allocated capacity is usually larger than its current length**. When `append()` exceeds capacity, CPython grows the array by roughly 1.125x plus a small constant (`listobject.c`'s growth pattern), not by exactly one slot — this is what makes repeated `append()` **O(1) amortized** rather than O(n) per call: most appends just write into already-allocated slack space, and the periodic full reallocation+copy is spread thin over many cheap appends.

![A list's over-allocated buffer: length vs allocated capacity, with slack space absorbing future appends](diagrams/01-list-overallocation.svg)

```python
import sys
lst = []
prev = sys.getsizeof(lst)
for i in range(10):
    lst.append(i)
    size = sys.getsizeof(lst)
    if size != prev:
        print(f"len={len(lst)}: buffer grew to {size} bytes")
        prev = size
```

Running this shows the buffer growing in jumps, not once per append — direct evidence of over-allocation.

### `tuple`: no over-allocation, because it can't grow

A `tuple`'s array is allocated at exactly its final size when created — there's no growth strategy because tuples are immutable and their size never changes after construction. This makes tuples slightly more memory-efficient than lists of the same length and is one reason tuple creation for small, fixed collections is marginally cheaper.

### `dict`: an open-addressing hash table, with a parallel insertion-order array

Since Python 3.6 (guaranteed in the language spec since 3.7), CPython's `dict` uses a "compact dict" layout: a sparse table of indices into a dense array of `(hash, key, value)` entries, where the dense array preserves insertion order. Looking up a key hashes it, probes the sparse index table (using open addressing — perturbing the probe sequence on collision, not chaining) to find which slot in the dense array holds that hash, then confirms equality. This split design is *why* dicts got both smaller (the sparse table only needs small integer indices, not full entries) and order-preserving in the same change — the insertion-order property fell out of the dense array's layout, not a separate linked list like some other languages' ordered maps use.

![dict's two-part structure: sparse index table (hash -> slot) plus a dense, insertion-ordered entries array](diagrams/02-dict-compact-layout.svg)

### `set`: literally the same hash table machinery as `dict`, minus the values

CPython's `set` implementation shares its underlying hash-table code with `dict` (both descend from the same probing/resizing logic in the C source), storing only keys with no associated value slot. This is why sets and dicts have matching average-case complexity characteristics for membership/insertion/deletion.

### Complexity summary (average case)

| Operation | `list` | `tuple` | `dict` | `set` | `deque` |
|---|---|---|---|---|---|
| Index access | O(1) | O(1) | — | — | O(n) |
| Append/add | O(1)* | — | O(1)* | O(1)* | O(1) both ends |
| Insert/pop front | O(n) | — | — | — | O(1) |
| Membership (`in`) | O(n) | O(n) | O(1) | O(1) | O(n) |
| Key/value lookup | — | — | O(1) | — | — |

\* amortized, due to over-allocation growth strategy.

## 9. Common Pitfalls

1. **Using `list` for frequent front-insertion/removal** — `.insert(0, x)` and `.pop(0)` are both O(n); use `collections.deque` if you need queue-like behavior at both ends.
2. **Assuming `dict`/`set` iteration order is meaningful across different dicts** — insertion order is guaranteed *within* one dict, but two dicts with the "same" keys inserted in different orders will iterate differently.
3. **Using a mutable object (like a `list`) as a dict key or set element** — raises `TypeError: unhashable type`, because hashability requires the value to never change after being hashed. Use a `tuple` instead if you need a compound, fixed key.
4. **Checking membership with `in` on a `list` in a hot loop** — this is O(n) per check; converting to a `set` first turns repeated membership tests into O(1) average, often a large real-world speedup.
5. **Slicing thinking it's free** — `lst[1:]` allocates and copies a whole new list; doing this repeatedly in a loop is O(n) per slice, not free.

## 10. Quick Reference

```python
lst.append(x); lst.pop()          # O(1) amortized — use the END of a list
lst.insert(0, x); lst.pop(0)       # O(n) — use collections.deque instead
d.get(key, default)                 # never raises KeyError
d.setdefault(key, default)          # get-or-insert in one call
key in d / value in s                # O(1) average — prefer over `in list`
from collections import deque        # O(1) both-end queue
a | b, a & b, a - b, a ^ b           # set algebra: union, intersect, diff, symmetric diff
```