Core data structures
Arrays, linked lists, stacks, queues and the hash table behind every dict.
Create a free account Try part of it here
Why it matters
A data structure is a way of laying data out in memory so some operations are cheap. Choose well and code is fast and simple. Choose badly and no amount of clever code saves it. Every system you'll build on, from a web server's request queue to a vector database's index to the KV cache inside a transformer, is a data structure chosen for the job.
What you'll be able to do
- Explain what lists, stacks, queues and linked lists are good and bad at, in Big O terms
- Use a stack to match brackets and a queue to process work in order
- Explain how a hash table turns a key into a slot, and what happens on a collision
- Build a working hash map class with resizing
What it covers
- Arrays: what a Python list really is
- Queues: first in, first out
- Hash tables: the engine inside dict and set
- Why keys must not change
- Choosing a structure
- Collisions are normal
Arrays: what a Python list really is
Picture a long row of numbered seats in a theater. If your ticket says seat 5,000, you can walk straight to it. You don't have to count from the start. A Python list is an array like that: a block of memory slots in a row, each pointing at one item. Because the slots sit side by side, the computer can jump to slot 5,000 directly. It works out the address with one multiplication. So reading or changing items[i] is O(1).
Adding to the end is cheap too. Python keeps spare slots at the end, and when they run out it moves everything to a bigger block. That move is rare, so append is O(1) on average.
Inserting at the front is different. Everyone in the row has to shift one seat over to make room, which is O(n). The same goes for pop(0), which shifts everything left.
| operation on a list | cost |
|---|---|
items[i], items[i] = x | O(1) |
items.append(x), items.pop() | O(1) on average |
items.insert(0, x), items.pop(0) | O(n) |
x in items | O(n) |
Stacks: last in, first out
A stack is like a pile of plates: you add to the top and take from the top. A Python list does this well with append and pop. Undo buttons are stacks, and so is the call stack that keeps track of which function called which.
A classic use is checking brackets. Each opener goes on the stack, and each closer must match the opener on top:
PAIRS = {")": "(", "]": "[", "}": "{"}
def balanced(text):
stack = []
for ch in text:
if ch in "([{":
stack.append(ch)
elif ch in PAIRS:
if not stack or stack.pop() != PAIRS[ch]:
return False
return not stack
print(balanced('{"tags": ["a", "b"]}'))
print(balanced("(1 + [2 * 3)]"))Code editors run this exact check to highlight a missing bracket.
stack = [] stack.append("a") stack.append("b") print(stack.pop())
Show the answer
b
Last in, first out: pop returns what you added most recently, which is b.
Show the answer
C, then B
Last in, first out: C was added last, so it comes off first, then B.
Queues: first in, first out
A queue is a line at a shop: the first to arrive is served first. Web servers queue requests, and background workers queue jobs.
A list makes a poor queue, because pop(0) shifts every remaining item. Imagine everyone in line taking one step forward each time someone is served, on a line of a million people. Use collections.deque (said "deck", a double-ended queue). It adds and removes at both ends in O(1):
from collections import deque jobs = deque() jobs.append("send welcome email") jobs.append("resize photo") jobs.append("score lead") while jobs: job = jobs.popleft() # O(1), unlike list.pop(0) print("doing:", job)
Linked lists
A treasure hunt works differently from a row of seats. Each clue can be anywhere, and it tells you where the next clue is. A linked list stores each item in its own small object, a node, along with a pointer to the next node. The nodes can live anywhere in memory.
Adding at the front is O(1): make a node that points at the old first node. But reaching item 5,000 means following 5,000 pointers, so indexing is O(n). In Python you'll rarely write one, but the idea of "nodes pointing at nodes" is everywhere: trees, graphs and the chain of blocks in a deque.
Each new node points at the old head, so adding at the front never moves anything. Notice the printed order: the last item added comes first.
Hash tables: the engine inside dict and set
How can d["tent"] be O(1) when the dict holds a million keys? With a hash table. Think of a wall of pigeonholes in a mailroom, and a rule that turns any name into a pigeonhole number. To file or find something, you apply the rule and walk straight there.
- A hash function is that rule: it turns the key into a big number. The same key always gives the same number. Python's is called
hash. - The table is an array of slots called buckets, the pigeonholes. The bucket for a key is
hash(key) % number_of_buckets: the remainder after dividing, so it always fits. - To store or find a key, go straight to its bucket.
Two keys can land in the same bucket. That's a collision. A simple fix is to keep a short list of key and value pairs in each bucket, then search that little list.
buckets = 8 for key in ["tent", "mug", "boot", "lantern", "stove"]: print(key.ljust(8), "-> bucket", hash(key) % buckets)
Your bucket numbers will differ from someone else's. Python mixes a random value into string hashes each time it starts, which makes some attacks harder.
As the table fills, buckets get crowded and searches slow down. So hash tables track their load factor, the number of items divided by the number of buckets. When it passes a limit, often 0.75, the table doubles its buckets and puts every key in its new place, like building a bigger wall and refiling all the mail. Resizing is O(n), but it happens rarely, so each insert is still O(1) on average.
In plain words: a hash table replaces "search everywhere" with "work out where it must be, and look there".
Note: Python's real dict uses a cleverer layout called open addressing, with no lists inside buckets. The idea is the same: hash, jump, handle collisions, resize when full.
Why keys must not change
Dict and set keys have to be hashable: their hash can never change. Lists can change, so they can't be keys. Tuples can't change, so they can.
prices = {("tent", "large"): 249}
print(prices[("tent", "large")])
try:
bad = {["tent", "large"]: 249}
except TypeError as err:
print("TypeError:", err)If a key could change after it was stored, its hash would change too. The table would then look in the wrong bucket and never find it. Python refuses up front: lists are "unhashable". Tuples, strings and numbers are fine.
Show the answer
The load factor becomes 4 / 4 = 1.0, so it doubles to 8 buckets and re-places every key
4 items in 4 buckets is a load factor of 1.0, over the limit. The table grows and every key moves to its bucket in the bigger table.
Choosing a structure
Each structure makes something cheap and something else expensive. So start from what your code does most:
| you need to... | use | because |
|---|---|---|
| keep items in order and read by position | list | O(1) indexing |
| take from the end you added to (undo, nesting) | list as a stack | O(1) append and pop |
| process work in arrival order | deque | O(1) at both ends |
| look things up by key | dict | O(1) average lookup |
| check "have I seen this?" | set | O(1) average membership |
| always get the smallest item next | heap (heapq) | O(log n) push and pop |
The last row is a heap, which keeps the smallest item on top. It's a bit like a hospital waiting room, where the next person seen isn't the first to arrive but the most urgent. It's how schedulers pick the next job and how search engines keep the top 10 results while scanning millions.
Show the answer
A set, for fast membership checks
A set is a hash table: checking membership takes about the same time however big it gets. A list scan grows with its length.
Collisions are normal
Put 30 people in a room and two of them probably share a birthday. Two keys landing in one bucket isn't an error either. Hash tables expect it, and handle it.
Practice what you just read
- 4 code examples you can edit and run
- a practice exercise that checks your code
- a 5-question quiz
- 5 review cards for spaced repetition
Try a quiz question
Why is my_list.pop(0) slow on a long list?