Data structures: lists, stacks, queues, hash tables

A data structure is a way of laying things out so that exactly the operations you need are fast. There is none that is best at everything.

The most important insight: searching a list of a million elements takes a million comparisons. Looking up in a dictionary of a million keys takes roughly one. The difference is not «a bit faster» — it is the whole difference between the code being runnable and not.

The complexity of the common operations:

* amortised: the list is occasionally regrown, but the cost is spread out.

How a hash table works. A hash function turns the key into a number, and the number points out a slot in an array. Looking up therefore becomes «compute the number, go straight there» — independently of how many elements there are.

Two keys can land in the same slot (a collision). That is solved with chains or with reprobing, and that is why O(1) is an average, not a guarantee. In the worst case it becomes O(n), but with a good hash function that practically never happens.

The price: the keys have to be hashable, that is, immutable. That is why a list cannot be a key in a dict — but a tuple can.

The most common performance error in Python code is searching a list inside a loop:

for x in the_big_list:          # n times
    if x in other_list:         # n comparisons each time  → O(n²)

One line is enough to fix it: other_set = set(other_list) before the loop. With n = 10 000 it goes from about 50 million comparisons to 10 000.

import time
from collections import deque, Counter, defaultdict

n = 200_000
items = list(range(n))
item_set = set(items)

def ms(f):
    t = time.perf_counter(); f(); return (time.perf_counter() - t) * 1000

print(f"list: {ms(lambda: [n - 1 in items for _ in range(100)]):.1f} ms")
print(f"set:  {ms(lambda: [n - 1 in item_set for _ in range(100)]):.1f} ms")
# list: 210.4 ms
# set:    0.0 ms      ← the same question, ~10 000 times faster

# A stack: last in, first out
stack = []
stack.append("a"); stack.append("b")
print(stack.pop())                      # b

# A queue: use a deque, not a list — list.pop(0) is O(n)
queue = deque(["a", "b"])
queue.append("c")
print(queue.popleft())                  # a

# Two dict tools that save a lot of code
words = "one two one three two one".split()
print(Counter(words).most_common(2))    # [('one', 3), ('two', 2)]

groups = defaultdict(list)
for name, form in [("Ada", "7A"), ("Bo", "7B"), ("Cim", "7A")]:
    groups[form].append(name)
print(dict(groups))                     # {'7A': ['Ada', 'Cim'], '7B': ['Bo']}

# The keys have to be hashable
d = {("row", 1): "value"}               # a tuple is fine
try:
    d[["row", 1]] = "value"             # a list is not
except TypeError as e:
    print(e)                            # unhashable type: 'list'