Data structures (arrays, maps, heaps, tradeoffs)

Data structures organize values so common operations become cheap—arrays for index access, trees for sorted order, heaps for extremes. Picking the wrong structure is the main source of accidental quadratic code.

Why this shows up in the real world

Databases are B-trees and hash indexes under the hood. Game worlds spatial-hash moving entities.

Core idea (explained for students)

Know tradeoffs: dynamic array vs linked list for locality; dict vs sorted container; when to pay O(log n) insert for O(log n) later queries.

Try this in Python

from collections import deque

q: deque[int] = deque([1, 2, 3])
q.append(4)
print(q.popleft(), list(q))

Common mistakes

• Using a list as a set for membership—linear scans.
• Assuming dict preserves order older than Python 3.7 when reasoning about portability.

Key takeaways

• Keep a cheat sheet of op costs for structures you use weekly.
• Default to dict/list until a proven bottleneck.