Programming foundations: Python

Sefism.

Chapter 06

Data structures and Big-O

The handful of structures most code is built from, and how to reason about the time and memory a solution costs as the input grows.

Big-O notation

Also called time complexity, space complexity, asymptotic analysis, Big-O

What
Big-O describes how the running time or memory of an algorithm grows as the input size n grows, ignoring constants. Common classes, fastest first: O(1), O(log n), O(n), O(n log n), O(n²), O(2^n).
Why
It predicts whether code that is fine on 100 rows will still work on a million, and lets you compare solutions before writing them.
Example
Checking whether a list contains duplicates with two nested loops is O(n²). Adding each item to a set and checking membership first is O(n) time and O(n) extra space.

Watch out

Ignoring hidden loops: in on a list, indexOf, contains and string concatenation inside a loop are each O(n).

Arrays and amortised growth

Also called amortized, dynamic array, contiguous memory

What
An array stores items side by side in memory, so reading by index is O(1). A dynamic array doubles its capacity when full, so appending is O(1) on average (amortised) even though an occasional append copies everything.
Why
It is why appending to a list is cheap but inserting or deleting at the front is O(n): every later item has to shift.

Watch out

Inserting at the start of a list in a loop, turning an O(n) job into O(n²).

Linked lists

Also called singly linked list, doubly linked list, nodes

What
A chain of nodes where each node holds a value and a pointer to the next (and, in a doubly linked list, the previous) node.
Why
Inserting or removing next to a node you already hold is O(1), which suits queues and LRU caches. Finding an item by position is O(n).

Watch out

Choosing a linked list for general storage: poor cache locality makes it slower than a dynamic array for almost every everyday task.

Stacks

Also called LIFO, push, pop

What
A last-in, first-out collection: you push onto the top and pop from the top, both O(1).
Why
Stacks model undo history, matching brackets, depth-first search and the call stack itself.
Python
def balanced(text: str) -> bool:
    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

Watch out

Popping from an empty stack without checking, which throws or returns nothing depending on the language.

Queues and deques

Also called FIFO, double-ended queue, enqueue, dequeue

What
A queue is first-in, first-out: add at the back, remove from the front, both O(1). A deque (double-ended queue) allows O(1) adds and removes at both ends.
Why
Queues model waiting lines, job processing and breadth-first search.
Python
from collections import deque

queue = deque(["ada", "linus"])
queue.append("grace")
first = queue.popleft()  # "ada"

Watch out

Using a plain list as a queue: removing from the front shifts every element, O(n) per call (Python list.pop(0), JavaScript shift).

How hash tables work

Also called hashing, hash function, collisions, buckets, hash map

What
A hash table turns a key into a number with a hash function, uses it to pick a bucket in an array, and stores the entry there. Keys that land in the same bucket (collisions) are handled by chaining or probing.
Why
It is how dictionaries and sets get O(1) average lookups. The worst case is O(n) when many keys collide.

Watch out

Changing an object after using it as a key, or defining equality without a matching hash, so the entry can no longer be found.

Trees and binary search trees

Also called BST, binary tree, root, leaf

What
A tree is a hierarchy of nodes with one root, where each node has children and no cycles. In a binary search tree, left children are smaller and right children larger than their parent.
Why
Trees model folders, HTML and org charts. A balanced search tree keeps data sorted with O(log n) lookup, insert and delete; TreeMap and std::map are built this way.

Watch out

Inserting sorted data into a plain BST, which degrades it into a linked list with O(n) operations.

Graphs

Also called vertices, edges, adjacency list, BFS, DFS, breadth-first search, depth-first search

What
A graph is a set of nodes (vertices) connected by edges, which may have directions or weights. It is usually stored as an adjacency list: a map from each node to its neighbours.
Why
Road maps, social networks, dependencies and web links are graphs. Breadth-first search finds shortest paths in unweighted graphs; depth-first search explores and detects cycles.

Watch out

Traversing a graph without tracking visited nodes, which loops forever on the first cycle.

Recursion

Also called base case, recursive case

What
A function that calls itself on a smaller version of the problem, with a base case that stops the calls.
Why
Recursion fits naturally shaped problems: trees, nested folders, divide and conquer sorts and backtracking.
Python
def factorial(n: int) -> int:
    if n <= 1:
        return 1
    return n * factorial(n - 1)

Watch out

A missing or unreachable base case, which recurses until the stack overflows.

Go deeper

06 · Data structures and Big-O6 / 10