Data Structures Visualized

An array is a contiguous block of equal-size elements, so the address of index i is base + i × size — O(1) random access. Insertion or deletion at index i requires shifting the following elements, making it O(n)..

a = [12, 30, 21, 45, 9, 38, 27]

a[6]        # one multiply, one add, one read
# address = base + 6 * itemsize
# slots 0..5 are never touched — O(1)

len(a)      # also O(1), it is stored

A dynamic array holds a capacity larger than its length; on overflow it allocates a larger buffer (typically 2×) and copies. A single resize is O(n), but doubling makes the amortised cost of append O(1)..

# CPython list append, in essence:
def append(self, v):
    if self.length == self.capacity:
        self.capacity = self.capacity * 2   # O(n) copy
        self.buf = self.buf + [None] * self.capacity
    self.buf[self.length] = v               # O(1)
    self.length += 1

# amortised O(1) because capacity DOUBLES

A linked list stores each element in a node holding a value and a pointer to the next node. There is no index arithmetic, so access is O(n) traversal, but insertion or removal given a node reference is O(1) — only pointers are rewritten, nothing shifts..

class Node:
    def __init__(self, value, nxt=None):
        self.value, self.next = value, nxt

def insert_after(node, value):
    node.next = Node(value, node.next)
    return node.next
# two writes. nothing shifts.

Each node holds next and prev pointers, enabling O(1) removal given only the node (no predecessor search) and bidirectional traversal, at the cost of one extra pointer per node and more pointer updates per mutation..

def remove(node):
    node.prev.next = node.next
    node.next.prev = node.prev
# O(1) — no search for a predecessor

from collections import deque
d = deque([4, 8, 15])
d.appendleft(1)   # O(1) at BOTH ends
d.pop()           # O(1)

A stack is LIFO: push and pop both operate at one end in O(1). It is the structure behind function call frames, undo histories and depth-first traversal — anywhere you must finish the most recent thing before returning to the previous one..

stack = []
stack.append(4)      # push
stack.append(9)
stack.append(2)

stack.pop()          # 2  — last in, first out
stack[-1]            # 9  — peek

# a plain list IS the idiomatic Python stack

A queue is FIFO: enqueue at the tail, dequeue from the head, both O(1) with a linked list or ring buffer. It underlies breadth-first traversal, task scheduling and any producer/consumer buffer..

from collections import deque

q = deque()
q.append("Ada")      # join the back
q.append("Bo")

q.popleft()          # "Ada" — first in, first out

# never use list.pop(0) — that is O(n)

A hash function maps a key to a bucket index, giving average O(1) insert and lookup. Performance depends on a good hash and a low load factor; the map resizes and rehashes as it fills to keep buckets short..

def my_hash(key, n_buckets):
    total = 0
    for ch in key:
        total += ord(ch)
    return total % n_buckets

d = {"cat": 1, "dog": 2}
d["dog"]      # straight to the bucket — O(1)

Collisions occur when distinct keys hash to the same bucket. Separate chaining stores a list per bucket; open addressing probes for the next free slot.

buckets = [[] for _ in range(5)]

def put(k, v):
    i = my_hash(k, len(buckets))
    buckets[i].append((k, v))   # chain, do not overwrite

def get(k):
    i = my_hash(k, len(buckets))
    for key, val in buckets[i]:  # scan the short chain
        if key == k:
            return val

A tree is an acyclic connected graph with a root and a parent-child hierarchy. In a balanced binary search tree the ordering invariant lets you discard half the remaining nodes at each step, giving O(log n) search, insert and delete..

def search(node, t):
    if node is None:
        return None
    if t == node.value:
        return node
    if t < node.value:
        return search(node.left, t)
    return search(node.right, t)
# each comparison discards half the tree

A graph is a set of vertices and edges, directed or undirected, possibly cyclic. It is stored as an adjacency list (space O(V+E), good for sparse graphs) or an adjacency matrix (O(V²), constant-time edge lookup).

adj = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "F", "G"],
}

len(adj["B"])        # degree of B
"C" in adj["A"]      # is there an edge?
# space O(V + E) — right for sparse graphs