Advanced Data Structures

Lists and dictionaries will carry you a long way. Advanced data structures matter when the obvious approach starts costing too much — searching a list of a million items, repeatedly finding the smallest value, or representing connections rather than sequences. This guide covers the six structures worth knowing, what each is actually fast at, and the everyday problem each one solves.

The one idea behind all of them#

Every data structure is a trade. Making one operation fast usually makes another slower. A list is fast to append to and slow to search; a set is fast to search and keeps no order. There is no best structure, only a best fit for what your code does most often.

So before choosing, finish this sentence: the operation this code performs thousands of times is ____. That answer picks the structure.

Stacks: last in, first out#

A stack only lets you add and remove at one end. Think of a pile of plates — the last one on is the first one off.

stack = []

stack.append("page1")   # push
stack.append("page2")
stack.append("page3")

print(stack.pop())      # page3  - most recent first
print(stack.pop())      # page2
print(stack[-1])        # page1  - peek without removing

Stacks are behind the browser back button, undo in an editor, and the “call stack” in the error messages you read every day. They are also how you check balanced brackets:

def balanced(text):
    pairs = {")": "(", "]": "[", "}": "{"}
    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("a(b[c]d)e"))   # True
print(balanced("a(b[c)d]e"))   # False

Queues: first in, first out#

A queue adds at one end and removes from the other — a supermarket till, not a pile of plates.

from collections import deque

queue = deque()
queue.append("job1")     # join the back
queue.append("job2")
queue.append("job3")

print(queue.popleft())   # job1  - oldest first
print(queue.popleft())   # job2

Use deque rather than a plain list. Removing the first item of a list with pop(0) has to shift every remaining element along by one; on a queue of a million items that is a million moves per removal. A deque does it in constant time.

Heaps: the smallest item, cheaply#

A heap keeps the smallest element ready to hand without sorting everything.

import heapq

tasks = []
heapq.heappush(tasks, (3, "write docs"))
heapq.heappush(tasks, (1, "fix the crash"))
heapq.heappush(tasks, (2, "answer email"))

print(heapq.heappop(tasks))   # (1, 'fix the crash')
print(heapq.heappop(tasks))   # (2, 'answer email')

Pushing and popping both cost roughly the logarithm of the size — far cheaper than re-sorting a list after every insertion. This is the structure behind priority queues, task schedulers, and route-finding algorithms.

Python’s heap is a min-heap. For largest-first, negate the priority:

heapq.heappush(tasks, (-score, name))   # highest score pops first

Trees: hierarchy#

A tree is nodes with children and no loops. Folders inside folders, an HTML document, a comment thread — all trees.

tree = {
    "name": "root",
    "children": [
        {"name": "docs", "children": []},
        {"name": "src", "children": [
            {"name": "main.py", "children": []},
        ]},
    ],
}


def walk(node, depth=0):
    print("  " * depth + node["name"])
    for child in node["children"]:
        walk(child, depth + 1)


walk(tree)

The function calls itself for each child. That is recursion, and trees are the structure where recursion feels natural rather than clever.

A binary search tree keeps values ordered so that searching halves the remaining options at every step. In practice you will rarely write one — a dictionary or a sorted list plus bisect usually beats it — but understanding the idea explains why database indexes are fast.

Graphs: connection#

A graph is nodes connected by edges, with loops allowed. Social networks, road maps, package dependencies.

graph = {
    "A": ["B", "C"],
    "B": ["D"],
    "C": ["D"],
    "D": [],
}


def reachable(graph, start):
    """Breadth-first search: everything you can get to from start."""
    from collections import deque
    seen = {start}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for neighbour in graph[node]:
            if neighbour not in seen:
                seen.add(neighbour)
                queue.append(neighbour)
    return seen


print(reachable(graph, "A"))   # {'A', 'B', 'C', 'D'}

Note what this function uses: a queue for the frontier, a set for what has been visited. Swap the deque for a stack and you have depth-first search instead. Most graph algorithms are a small variation on this shape.

Sets: is this thing in there?#

A set stores unique values and answers “does it contain x?” in roughly constant time, no matter how big it is.

names_list = ["ana", "sam", "kim"] * 100000
names_set = set(names_list)

"kim" in names_list   # checks items one by one
"kim" in names_set    # one hash lookup

Sets also do the operations you learned as Venn diagrams:

a = {1, 2, 3, 4}
b = {3, 4, 5}

print(a & b)   # {3, 4}       - in both
print(a | b)   # {1,2,3,4,5}  - in either
print(a - b)   # {1, 2}       - in a only
print(a ^ b)   # {1, 2, 5}    - in one but not both

If you ever write if item not in some_list inside a loop, converting that list to a set is often the single biggest speed-up available to you.

Choosing between them#

Where to go next#

• What is an algorithm? — the other half of the same subject.
• Python lists explained — the structure everything here is compared against.
• Python dictionaries explained — hashing, in practical terms.