2. Python's Built-in Collections

Python ships with excellent data structures. Before building anything custom, know these well.

---

2.1 list — Dynamic Array

A contiguous block of memory. Index-based access. The most versatile collection.

# Creation
nums = [1, 2, 3, 4, 5]
empty = []
from_range = list(range(10))    # [0, 1, 2, ..., 9]

# Access — O(1)
first = nums[0]     # 1
last  = nums[-1]    # 5
sub   = nums[1:4]   # [2, 3, 4] — creates a NEW list (O(k) where k = slice length)

# Modification
nums.append(6)         # O(1) — add to end
nums.insert(0, 0)      # O(n) — insert at position (shifts everything right)
nums.pop()             # O(1) — remove from end
nums.pop(0)            # O(n) — remove from front (shifts everything left)
nums.remove(3)         # O(n) — remove first occurrence of value

# Searching
idx = nums.index(4)    # O(n) — raises ValueError if not found
found = 4 in nums      # O(n) — linear scan

# Sorting
nums.sort()            # O(n log n) — in-place
sorted_copy = sorted(nums)  # O(n log n) — returns new list

# Length
n = len(nums)          # O(1)

Use a list when: you need ordered, index-accessible items and mostly append/pop from the end.

---

2.2 dict — Hash Map

Maps keys to values. Lookups, insertions, and deletions are $O(1)$ average.

# Creation
user = {"name": "Alice", "age": 30, "role": "engineer"}
empty = {}
from_keys = dict.fromkeys(["a", "b", "c"], 0)   # {'a': 0, 'b': 0, 'c': 0}

# Access
name = user["name"]                   # O(1) — raises KeyError if missing
name = user.get("name", "Unknown")    # O(1) — safe, returns default

# Modification
user["age"] = 31                      # O(1) — update or insert
del user["role"]                      # O(1) — delete key

# Iteration
for key in user:                      # iterate keys
    print(key, user[key])

for key, value in user.items():       # iterate key-value pairs
    print(f"{key}: {value}")

# Membership
if "name" in user:                    # O(1) — always check this way (not .keys())
    print(user["name"])

# defaultdict — auto-creates missing keys
from collections import defaultdict
word_count: dict[str, int] = defaultdict(int)
for word in ["hello", "world", "hello"]:
    word_count[word] += 1    # no KeyError even on first access
# {'hello': 2, 'world': 1}

Use a dict when: you need to map one thing to another, count frequencies, or cache computed results.

---

2.3 set — Unordered Unique Collection

Like a dict but only keys — no values. $O(1)$ membership test.

# Creation
fruits = {"apple", "banana", "cherry"}
unique_nums = set([1, 2, 2, 3, 3, 3])   # {1, 2, 3}

# Operations — all O(1)
fruits.add("date")
fruits.remove("banana")     # raises KeyError if missing
fruits.discard("banana")    # safe — no error if missing
found = "apple" in fruits   # O(1) — much faster than list!

# Set math
a = {1, 2, 3, 4}
b = {3, 4, 5, 6}
print(a | b)   # union:        {1, 2, 3, 4, 5, 6}
print(a & b)   # intersection: {3, 4}
print(a - b)   # difference:   {1, 2}
print(a ^ b)   # symmetric diff: {1, 2, 5, 6}

Use a set when: you need fast membership testing or want to remove duplicates.

---

2.4 tuple — Immutable Sequence

Like a list but cannot be modified after creation. Hashable (can be used as a dict key).

point = (3, 7)
x, y = point           # unpacking

# Tuples as dict keys (lists can't be dict keys!)
grid = {(0, 0): "start", (3, 7): "end"}
current = grid[(0, 0)]

# Named tuples — self-documenting
from collections import namedtuple
Point = namedtuple("Point", ["x", "y"])
p = Point(3, 7)
print(p.x, p.y)   # more readable than p[0], p[1]

Use a tuple when: the data should not change (coordinates, RGB colours, database rows) or when you need a hashable sequence.

---

2.5 deque — Double-Ended Queue

Efficient $O(1)$ append and pop from both ends. Use instead of list when you need a queue.

from collections import deque

q = deque()
q.append(1)        # add to right  — O(1)
q.appendleft(0)    # add to left   — O(1)
q.pop()            # remove right  — O(1)
q.popleft()        # remove left   — O(1) ← list.pop(0) is O(n), deque is O(1)!

# Fixed-size sliding window (keep last k items)
recent = deque(maxlen=5)
for i in range(10):
    recent.append(i)   # automatically drops oldest when full
print(recent)  # deque([5, 6, 7, 8, 9])

Use a deque when: you need a queue (FIFO), a double-ended buffer, or a fixed-size rolling window.

---

2.6 Counter — Frequency Map

A dict subclass specialised for counting.

from collections import Counter

words = ["the", "cat", "sat", "on", "the", "mat", "the"]
freq = Counter(words)
# Counter({'the': 3, 'cat': 1, 'sat': 1, 'on': 1, 'mat': 1})

freq.most_common(2)     # [('the', 3), ('cat', 1)] — top 2
freq["missing_word"]    # 0 — no KeyError for unseen keys

# Arithmetic
a = Counter(["a", "b", "a"])   # Counter({'a': 2, 'b': 1})
b = Counter(["a", "c"])        # Counter({'a': 1, 'c': 1})
print(a + b)   # Counter({'a': 3, 'b': 1, 'c': 1})
print(a - b)   # Counter({'a': 1, 'b': 1})  — drops zero/negative

---

Quick Reference

Container	Access	Insert	Delete	Search	Use for
list	$O(1)$	$O(1)$ end / $O(n)$ mid	$O(1)$ end / $O(n)$ mid	$O(n)$	Ordered, index-based
dict	$O(1)$	$O(1)$	$O(1)$	$O(1)$	Key→value mapping
set	—	$O(1)$	$O(1)$	$O(1)$	Membership, dedup
tuple	$O(1)$	immutable	immutable	$O(n)$	Immutable records
deque	$O(n)$ mid	$O(1)$ ends	$O(1)$ ends	$O(n)$	Queue, sliding window

---