Data Structures Cheat Sheet
Summarizes core linear and non-linear data structures, their time complexities, and example implementations of stacks, queues, and hash tables.
2 PagesBeginnerMar 28, 2026
Linear Structures
Structures that store elements in a sequential order.
- Array- Contiguous, fixed or dynamic-size collection with O(1) index access, O(n) insertion/deletion in the middle
- Linked List- Nodes with pointers to the next (and optionally previous) node; O(1) insertion/deletion at a known position, O(n) access
- Stack- LIFO structure with O(1) push/pop; used for undo history, call stacks, and expression evaluation
- Queue- FIFO structure with O(1) enqueue/dequeue; used for task scheduling and BFS traversal
- Deque- Double-ended queue supporting O(1) insertion/removal at both ends
Trees, Graphs & Hashing
Non-linear structures for hierarchical and connected data.
- Binary Tree- Each node has at most two children; traversed via in-order, pre-order, post-order, or level-order
- Binary Search Tree (BST)- Left subtree < node < right subtree; O(log n) search/insert/delete when balanced, O(n) worst case
- Heap- Complete binary tree maintaining the min-heap or max-heap property; O(log n) insert/extract, O(1) peek
- Hash Table- Maps keys to values via a hash function; average O(1) lookup/insert, O(n) worst case with collisions
- Graph- Vertices connected by edges; represented as an adjacency list (space-efficient) or adjacency matrix (fast edge lookup)
- Trie- Tree structure for storing strings by shared prefixes; O(m) lookup where m is the key length
Stack & Queue in Practice
Common Python implementations with O(1) operations.
python
# Stack using a Python liststack = []stack.append(1) # pushstack.append(2)stack.pop() # pop -> 2 (LIFO)# Queue using collections.deque (O(1) at both ends)from collections import dequequeue = deque()queue.append(1) # enqueuequeue.append(2)queue.popleft() # dequeue -> 1 (FIFO)
Hash Table & Set Usage
Counting and membership checks with O(1) average time.
python
# Hash table (dict) usagecounts = {}for word in ["a", "b", "a", "c", "b", "a"]: counts[word] = counts.get(word, 0) + 1# {'a': 3, 'b': 2, 'c': 1}# Using a set for O(1) average membership checksseen = set()seen.add(5)5 in seen # => True
Union-Find (Disjoint Set)
Near-O(1) amortized union/find using path compression and union by rank, used for Kruskal's MST and cycle detection.
python
class UnionFind: def __init__(self, n): self.parent = list(range(n)) self.rank = [0] * n def find(self, x): if self.parent[x] != x: self.parent[x] = self.find(self.parent[x]) # path compression return self.parent[x] def union(self, a, b): ra, rb = self.find(a), self.find(b) if ra == rb: return False if self.rank[ra] < self.rank[rb]: ra, rb = rb, ra self.parent[rb] = ra if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1 return True# Amortized time per operation is O(alpha(n)), effectively constant
LRU Cache with Doubly Linked List + Hash Map
Combines a hash map and a doubly linked list to get O(1) get/put with eviction of the least recently used entry.
python
from collections import OrderedDictclass LRUCache: def __init__(self, capacity): self.capacity = capacity self.cache = OrderedDict() def get(self, key): if key not in self.cache: return -1 self.cache.move_to_end(key) # mark as recently used 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.capacity: self.cache.popitem(last=False) # evict least recently used
Fenwick Tree (Binary Indexed Tree)
Supports prefix-sum queries and point updates in O(log n), far leaner than a segment tree for cumulative sums.
python
class FenwickTree: def __init__(self, n): self.tree = [0] * (n + 1) def update(self, i, delta): i += 1 while i < len(self.tree): self.tree[i] += delta i += i & (-i) # move to next responsible node def prefix_sum(self, i): i += 1 total = 0 while i > 0: total += self.tree[i] i -= i & (-i) # move to parent return total def range_sum(self, l, r): return self.prefix_sum(r) - (self.prefix_sum(l - 1) if l > 0 else 0)
Advanced & Self-Balancing Structures
Structures beyond the basics, used when worst-case guarantees or probabilistic space savings matter.
- AVL Tree- Self-balancing BST that rebalances via rotations whenever a subtree's height difference exceeds 1; guarantees O(log n) operations
- Red-Black Tree- Self-balancing BST using color invariants instead of strict height balance; looser balancing than AVL but fewer rotations on insert/delete, used in std::map and TreeMap
- B-Tree- Multi-way balanced tree where nodes hold multiple keys; minimizes disk reads, so it's the backbone of most database indexes and filesystems
- Skip List- Layered linked lists with probabilistic "express lanes"; O(log n) expected search/insert without tree rebalancing logic, used in Redis sorted sets
- Bloom Filter- Probabilistic set membership structure using multiple hash functions over a bit array; O(1) checks with no false negatives but possible false positives
- Segment Tree- Binary tree over an array enabling O(log n) range queries (sum/min/max) and point or range updates
- Persistent Data Structure- Structure where every mutation returns a new version while preserving old versions, typically via structural sharing (e.g. persistent trees in Clojure/Scala)
Weighted Graph Representations
Adjacency list with weights versus a matrix, and converting between them for algorithms like Dijkstra.
python
# Adjacency list with weights: space O(V + E)graph = { "A": [("B", 4), ("C", 1)], "B": [("D", 1)], "C": [("B", 2), ("D", 5)], "D": [],}# Adjacency matrix: space O(V^2), O(1) edge-weight lookupimport mathnodes = list(graph)idx = {n: i for i, n in enumerate(nodes)}n = len(nodes)matrix = [[math.inf] * n for _ in range(n)]for u in graph: for v, w in graph[u]: matrix[idx[u]][idx[v]] = w# Rule of thumb: sparse graphs (E << V^2) -> adjacency list;# dense graphs or frequent edge-weight lookups -> adjacency matrix
Pro Tip
Pick the data structure by which operation dominates your workload — a hash table wins for lookups, but if you need sorted order or range queries, a balanced BST or sorted array beats it despite slower average-case lookup.
Was this cheat sheet helpful?
Explore Topics
#DataStructures#DataStructuresCheatSheet#Programming#Beginner#LinearStructures#TreesGraphsHashing#StackQueueInPractice#Hash#CheatSheet#SkillVeris
