Common data structures and their features

A reference for the data structures that show up in coding interviews — what each is, its operation costs, the Python type that implements it, and when to reach for it. For algorithms on these structures, see the pattern folders (trees, graphs, etc.).

Complexity at a glance

Average-case time for the core operations (n = number of elements):

Linear structures

Dynamic array — Python list

Contiguous block of references that grows by over-allocating. O(1) random access and append; inserting/deleting anywhere but the end shifts elements (O(n)).

a = [1, 2, 3]
a[0]            # O(1) index
a.append(4)     # O(1) amortized
a.insert(0, 9)  # O(n) — shifts everything right
a.pop()         # O(1) at end; a.pop(0) is O(n)

Use for: ordered, index-based collections; the default sequence; also serves as a stack. Internals: list_internals.

Linked list

Nodes holding a value plus pointer(s) to neighbor(s). O(1) insert/delete given a node, but O(n) to reach one — no random access. Singly = one next; doubly = next + prev.

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

Use for: O(1) splicing in the middle, LRU caches (doubly linked + dict). Python has no built-in singly list. Patterns: linked lists.

Stack (LIFO)

Last in, first out. A list works, or deque.

stack = []
stack.append(1)   # push
stack.pop()       # pop top

Use for: DFS, undo, expression parsing, bracket matching, monotonic-stack problems.

Queue (FIFO)

First in, first out. Use collections.deque — list.pop(0) is O(n).

from collections import deque
q = deque([1, 2])
q.append(3)      # enqueue
q.popleft()      # dequeue — O(1)

Use for: BFS, scheduling, buffering.

Deque (double-ended queue)

O(1) push/pop at both ends. Python collections.deque (block-of-arrays).

from collections import deque
d = deque(maxlen=3)       # optional ring buffer
d.appendleft(0); d.append(1)

Use for: sliding-window maxima (monotonic deque), ring buffers. Patterns: bisect/heapq/deque.

Hash-based structures

Hash map — Python dict

Key → value with O(1) average lookup/insert/delete via hashing. Keys must be hashable (immutable). Insertion-ordered since 3.7.

d = {"a": 1}
d["b"] = 2          # O(1) avg
d.get("c", 0)       # default, no KeyError

Use for: lookups, counting (collections.Counter), memoization, adjacency lists. Worst case O(n) under adversarial collisions. Internals: dict_internals.

Hash set — Python set / frozenset

Unordered unique elements, O(1) membership. frozenset is the hashable (immutable) version — usable as a dict key or set element.

seen = set()
if x in seen:       # O(1) avg
    ...
seen.add(x)

Use for: dedup, “have I seen this?”, set algebra (&, |, -, ^).

Trees

Binary tree

Each node has up to two children. The basis for BSTs, heaps, tries, and expression trees. Traversed via DFS (pre/in/post-order) or BFS (level-order).

class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val, self.left, self.right = val, left, right

Patterns: tree traversals.

Binary search tree (BST)

Ordered binary tree: everything in the left subtree < node < everything in the right. In-order traversal yields sorted output. O(log n) search/insert/delete when balanced — degrades to O(n) if it becomes a “stick”.

Use for: ordered data with dynamic inserts. Python has no stdlib BST — use sortedcontainers.SortedList (third-party) or a sorted list + bisect.

Balanced BST (AVL, Red-Black)

Self-balancing BSTs that guarantee O(log n) by rotating on insert/delete. Red-Black trees back many standard ordered maps (C++ std::map, Java TreeMap). Python’s stdlib has none; interviews usually accept “I’d use a balanced BST / SortedList.”

Heap / priority queue — Python heapq

A complete binary tree stored as an array, satisfying the heap property (parent ≤ children for a min-heap). O(1) peek-min, O(log n) push/pop. Not fully sorted — only the root is ordered.

import heapq
h = []
heapq.heappush(h, 3); heapq.heappush(h, 1)
heapq.heappop(h)          # 1 (smallest)
# max-heap: push negated values, or (-priority, item) tuples

Use for: top-K, merge-K-lists, Dijkstra, scheduling, running median (two heaps).

Trie (prefix tree)

A tree keyed by characters; each root-to-node path spells a prefix. O(k) insert/search where k = key length, independent of how many keys are stored.

trie = {}
node = trie
for ch in "cat":
    node = node.setdefault(ch, {})
node["$"] = True          # end-of-word marker

Use for: autocomplete, prefix matching, word dictionaries, IP routing.

Graphs

Graph

Vertices + edges. Stored as an adjacency list (dict[node] -> list[neighbors]; sparse; O(V+E) space) or an adjacency matrix (V×V; O(V²) space; O(1) edge lookup; good for dense graphs). Can be directed/undirected, weighted/unweighted, cyclic/acyclic.

from collections import defaultdict
g = defaultdict(list)
g[0].append(1)            # edge 0 → 1

Use for: networks, dependencies, maps. Traversal and shortest paths: graphs, Dijkstra.

Union-Find (disjoint set)

Maintains a partition of elements into disjoint sets; find returns a set’s representative, union merges two. With path compression + union by rank, operations are ~O(α(n)) ≈ O(1).

parent = list(range(n))
def find(x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]   # path compression
        x = parent[x]
    return x

Use for: connected components, cycle detection in undirected graphs, Kruskal’s MST. See union-find.

Specialized: segment tree and Fenwick tree (BIT) give O(log n) range queries (sum/min over a range, with point updates). Rarely required outside competitive programming, but worth recognizing by name.

Choosing the right one

Interview angle

• “When would you use a deque over a list?” When you push/pop at the front — deque is O(1), list.pop(0) is O(n).
• “How do you get a max-heap in Python?” heapq is min-only; push negated values, or store (-priority, item) tuples.
• “Array vs linked list?” Array: O(1) index, cache-friendly, O(n) middle insert. Linked list: O(1) splice at a node, but O(n) to find it and no random access.
• “What makes a hash map O(1)?” Hashing to a bucket — amortized O(1) with good distribution and resizing; worst case O(n) on heavy collisions.
• “Which structure for top-K?” A heap of size K (O(n log k)).