Data Structures Cheat Sheet: Arrays, Trees, Graphs & More

Data structures are the building blocks of every program. Choosing the right one means the difference between an O(1) lookup and an O(n) scan. This cheat sheet covers all major structures — complexity, code, and when to use each.

Quick reference: all complexities

*Amortized or average case. BST worst case is O(n) when unbalanced.

Array

A contiguous block of memory. Index gives O(1) access.

# Python — list is a dynamic array
arr = [1, 2, 3, 4, 5]

arr[2]          # O(1) — access by index
arr.append(6)   # O(1) amortized — append
arr.insert(1, 9)  # O(n) — insert in middle shifts elements
arr.pop()       # O(1) — remove last
arr.pop(0)      # O(n) — remove first shifts all
arr[1:4]        # O(k) — slice creates a copy

// JavaScript — Array is dynamic
const arr = [1, 2, 3, 4, 5];

arr[2];              // O(1)
arr.push(6);         // O(1) amortized
arr.splice(1, 0, 9); // O(n) — insert at index
arr.pop();           // O(1)
arr.shift();         // O(n) — remove first
arr.slice(1, 4);     // O(k)

Use arrays when: you need O(1) random access, compact memory, or iteration by index.

Avoid arrays when: frequent insert/delete in the middle (use a linked list), or unknown size with many prepend operations.

Linked list

Nodes connected by pointers. No index — traverse to reach a node.

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

class LinkedList:
    def __init__(self):
        self.head = None

    def prepend(self, val):       # O(1)
        node = Node(val)
        node.next = self.head
        self.head = node

    def append(self, val):        # O(n) without tail pointer
        node = Node(val)
        if not self.head:
            self.head = node
            return
        cur = self.head
        while cur.next:
            cur = cur.next
        cur.next = node

    def delete(self, val):        # O(n) to find, O(1) to remove
        if self.head and self.head.val == val:
            self.head = self.head.next
            return
        cur = self.head
        while cur and cur.next:
            if cur.next.val == val:
                cur.next = cur.next.next
                return
            cur = cur.next

Singly linked list: each node has next. Efficient prepend/delete-head.

Doubly linked list: each node has next and prev. Efficient delete of any known node, used in LRU caches.

Use linked lists when: you need O(1) insert/delete at head/tail, implementing a queue, or building LRU cache (with a hash map).

Stack

Last-in, first-out (LIFO). Think: function call stack, undo history.

# Python — use a list as a stack
stack = []
stack.append(1)   # push — O(1)
stack.append(2)
stack.append(3)
top = stack[-1]   # peek — O(1)
stack.pop()       # pop — O(1)

const stack = [];
stack.push(1);          // O(1)
stack.push(2);
const top = stack[stack.length - 1];  // peek — O(1)
stack.pop();            // O(1)

Classic stack problems: balanced parentheses, evaluate expressions, next greater element, monotonic stack patterns.

Queue / Deque

First-in, first-out (FIFO). Use collections.deque in Python — not a list (list pop(0) is O(n)).

from collections import deque

queue = deque()
queue.append(1)     # enqueue — O(1)
queue.append(2)
queue.append(3)
front = queue[0]    # peek — O(1)
queue.popleft()     # dequeue — O(1)

# Deque — double-ended queue
dq = deque()
dq.appendleft(0)   # O(1) prepend
dq.append(4)       # O(1) append
dq.popleft()       # O(1)
dq.pop()           # O(1)

// JavaScript has no built-in queue; use an array for small inputs
const queue = [];
queue.push(1);       // enqueue — O(1)
queue.shift();       // dequeue — O(n)! use a pointer offset for large queues

// Efficient queue with two stacks or a linked list for O(1) dequeue

Use queues when: BFS traversal, task scheduling, rate limiting with a sliding window.

Hash map

Key → value lookup in O(1) average. Hash function maps key to bucket; collisions resolved by chaining or open addressing.

# Python dict
counts = {}
counts["apple"] = counts.get("apple", 0) + 1  # safe increment
del counts["apple"]

# defaultdict — no KeyError, default value on miss
from collections import defaultdict
graph = defaultdict(list)
graph["a"].append("b")

# Counter — frequency map
from collections import Counter
freq = Counter("banana")   # {'a': 3, 'n': 2, 'b': 1}
freq.most_common(2)        # [('a', 3), ('n', 2)]

// Map — preferred over plain object for dynamic keys
const map = new Map();
map.set("a", 1);
map.get("a");         // 1
map.has("b");         // false
map.delete("a");
map.size;             // number of entries

// Iteration
for (const [key, val] of map) { ... }
[...map.keys()], [...map.values()], [...map.entries()]

// Object — fine for string keys, but no .size, key order not guaranteed pre-ES2015
const freq = {};
for (const ch of "banana") freq[ch] = (freq[ch] ?? 0) + 1;

Use hash maps when: frequency counting, caching (memoization), two-sum style lookups, graph adjacency lists.

Watch out: worst-case O(n) with hash collisions; key must be hashable (no mutable objects as keys in Python).

Binary search tree (BST)

Each node: left child < node < right child. Gives O(log n) search on balanced trees.

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

def insert(root, val):
    if not root:
        return BSTNode(val)
    if val < root.val:
        root.left = insert(root.left, val)
    else:
        root.right = insert(root.right, val)
    return root

def search(root, val):
    if not root or root.val == val:
        return root
    if val < root.val:
        return search(root.left, val)
    return search(root.right, val)

def inorder(root):   # sorted order
    if root:
        yield from inorder(root.left)
        yield root.val
        yield from inorder(root.right)

Unbalanced BST degrades to O(n) — inserting sorted data creates a linked list. Use AVL or Red-Black trees (Python sortedcontainers.SortedList, Java TreeMap, C++ std::map) for guaranteed O(log n).

Heap (priority queue)

Complete binary tree where parent ≤ children (min-heap). O(log n) insert/extract, O(1) peek-min.

import heapq

heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 4)
heapq.heappush(heap, 1)

min_val = heap[0]            # O(1) peek
smallest = heapq.heappop(heap)  # O(log n)

# Max-heap — negate values
heapq.heappush(heap, -val)
max_val = -heapq.heappop(heap)

# heapify an existing list — O(n)
nums = [3, 1, 4, 1, 5, 9]
heapq.heapify(nums)

# k largest elements
import heapq
heapq.nlargest(3, nums)     # O(n log k)
heapq.nsmallest(3, nums)

// No built-in heap in JS — use a library or implement one
// For interviews, a simple min-heap class:
class MinHeap {
  constructor() { this.h = []; }
  push(v) {
    this.h.push(v);
    this._up(this.h.length - 1);
  }
  pop() {
    const top = this.h[0];
    const last = this.h.pop();
    if (this.h.length) { this.h[0] = last; this._down(0); }
    return top;
  }
  peek() { return this.h[0]; }
  get size() { return this.h.length; }
  _up(i) {
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (this.h[p] <= this.h[i]) break;
      [this.h[p], this.h[i]] = [this.h[i], this.h[p]];
      i = p;
    }
  }
  _down(i) {
    const n = this.h.length;
    while (true) {
      let s = i, l = 2*i+1, r = 2*i+2;
      if (l < n && this.h[l] < this.h[s]) s = l;
      if (r < n && this.h[r] < this.h[s]) s = r;
      if (s === i) break;
      [this.h[s], this.h[i]] = [this.h[i], this.h[s]];
      i = s;
    }
  }
}

Use heaps when: k-th largest/smallest, merge k sorted lists, Dijkstra's shortest path, scheduling by priority.

Graph

Vertices (nodes) connected by edges. Can be directed/undirected, weighted/unweighted.

# Adjacency list — O(V+E) space, best for sparse graphs
from collections import defaultdict, deque

graph = defaultdict(list)
# Undirected edge
def add_edge(u, v):
    graph[u].append(v)
    graph[v].append(u)

# BFS — shortest path in unweighted graph
def bfs(start, target):
    queue = deque([(start, [start])])
    visited = {start}
    while queue:
        node, path = queue.popleft()
        if node == target:
            return path
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))
    return None

# DFS — iterative
def dfs(start):
    stack = [start]
    visited = set()
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        for neighbor in graph[node]:
            stack.append(neighbor)
    return visited

# DFS — recursive
def dfs_recursive(node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs_recursive(neighbor, visited)
    return visited

# Weighted graph — Dijkstra's shortest path
import heapq

def dijkstra(graph, start):
    # graph = {node: [(weight, neighbor), ...]}
    dist = {start: 0}
    heap = [(0, start)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist.get(u, float("inf")):
            continue
        for w, v in graph.get(u, []):
            nd = d + w
            if nd < dist.get(v, float("inf")):
                dist[v] = nd
                heapq.heappush(heap, (nd, v))
    return dist

Adjacency matrix — O(V²) space, O(1) edge lookup, best for dense graphs.

Use BFS for: shortest path (unweighted), level-order traversal, connected components.
Use DFS for: cycle detection, topological sort, path existence, backtracking.

Trie (prefix tree)

Tree where each node is a character. Efficient for prefix search and autocomplete.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):         # O(m) where m = word length
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True

    def search(self, word):         # O(m)
        node = self.root
        for ch in word:
            if ch not in node.children:
                return False
            node = node.children[ch]
        return node.is_end

    def starts_with(self, prefix):  # O(m)
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return False
            node = node.children[ch]
        return True

    def autocomplete(self, prefix): # O(m + output)
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return []
            node = node.children[ch]
        results = []
        self._collect(node, prefix, results)
        return results

    def _collect(self, node, current, results):
        if node.is_end:
            results.append(current)
        for ch, child in node.children.items():
            self._collect(child, current + ch, results)

Use tries when: autocomplete/prefix search, word dictionary lookup, IP routing (CIDR), spell checking.

When to use which structure

Common interview patterns

Two-pointer: array problems — pair sum, remove duplicates, container with most water.

Sliding window: subarray/substring — max sum subarray, longest substring without repeating chars.

Monotonic stack: next greater element, largest rectangle in histogram, daily temperatures.

BFS + queue: shortest path, level-order tree traversal, word ladder.

DFS + recursion/stack: tree traversal, connected components, cycle detection, subset generation.

Heap: k-th largest, merge k lists, top-k frequent elements, median of data stream.

Trie: word search, prefix queries, replace words, search suggestions.

Union-find (DSU): connected components, cycle detection in undirected graph, Kruskal's MST.

# Union-Find (Disjoint Set Union)
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):             # path compression
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):         # union by rank
        px, py = self.find(x), self.find(y)
        if px == py:
            return False           # already connected
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return True

Common mistakes

Language built-ins

Common mistakes: 6 FAQ

Q: When should I use a hash map vs a BST?
Hash map for O(1) average get/set when you don't need ordering. BST (TreeMap) when you need sorted iteration, range queries, floor/ceiling lookups, or rank operations.

Q: Why is Python's heapq a min-heap? How do I get max-heap?
Negate values: push -val, pop and negate the result. For objects, use (-priority, item) tuples.

Q: What's the difference between list and collections.deque in Python?
list.pop(0) is O(n) — it shifts all elements. deque.popleft() is O(1). Use deque for any queue or when prepending frequently.

Q: Why does an unbalanced BST degrade to O(n)?
Inserting already-sorted data (1, 2, 3, 4, ...) creates a right-skewed tree — effectively a linked list. Every operation traverses the full height. Balanced variants (AVL, Red-Black) guarantee O(log n) by rotating after insert/delete.

Q: When should I use a trie over a hash set for word lookup?
Hash set is O(m) per lookup (hashing) and works well for exact matches. Trie shines for prefix queries, autocomplete, and "starts with" operations — it naturally groups words by shared prefixes.

Q: How do I implement an LRU cache?
Combine a hash map (O(1) key lookup) with a doubly linked list (O(1) move-to-front and evict-tail). Python's functools.lru_cache or collections.OrderedDict does this for you.

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.cache = OrderedDict()

    def get(self, key):
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.cap:
            self.cache.popitem(last=False)