The Data Structures Cheatsheet: Time & Space Complexity for Every Structure You Need#

Bookmark this page. Whether you’re cramming the night before a FAANG interview or just need to double-check whether deleting from a heap is O(log n) or O(n), this cheatsheet covers the ten data structures that account for nearly every coding interview question: arrays, linked lists, stacks, queues, hash maps, sets, trees, heaps, graphs, and tries.

For each structure you’ll find the time complexity of the core operations (average and worst case), space complexity, a minimal Python snippet, and the situations where it’s the right tool. Every section links to the full lesson in our 60-day curriculum if you want to go deeper.

The Master Table#

If you only have five minutes, this is the table to scan. Complexities are average case; worst cases follow in the per-structure sections.

* O(1) amortized when appending to the end.  ** O(1) once you hold a reference to the node; finding it costs O(n).

Where n is the number of elements, V/E are vertices/edges, and m is key length (for tries).

1. Arrays#

Contiguous memory, index-based access. Python’s list is a dynamic array.

Space: O(n)

1nums = [3, 1, 4, 1, 5]
2nums.append(9)        # O(1) amortized
3nums.insert(0, 2)     # O(n) — shifts every element
4first = nums[0]       # O(1)
5nums.sort()           # O(n log n)

Best for: index-based lookups, iteration, two-pointer and sliding-window patterns, anything where data fits in order and you rarely insert in the middle.

Study more: Day 4: Introduction to Arrays and Day 25: Binary Search.

2. Linked Lists#

Nodes connected by pointers. No random access, but O(1) insertion and deletion when you already hold a reference to the node.

Space: O(n), plus pointer overhead per node

 1class Node:
 2    def __init__(self, val):
 3        self.val = val
 4        self.next = None
 5
 6head = Node(1)
 7head.next = Node(2)          # insert after head: O(1)
 8new = Node(0)
 9new.next = head              # insert at head: O(1)
10head = new

Best for: frequent insertion/deletion at the ends, implementing stacks/queues/LRU caches, problems built around pointer manipulation (reverse a list, detect a cycle, merge sorted lists).

Study more: Day 7: Introduction to Linked Lists, Day 9: Doubly Linked Lists, and Day 10: Advanced Linked List Operations.

3. Stacks#

LIFO: last in, first out. In Python, just use a list with append/pop.

Space: O(n)

1stack = []
2stack.append("a")   # push
3stack.append("b")
4top = stack[-1]     # peek -> "b"
5stack.pop()         # pop  -> "b"

Best for: matching brackets, undo history, expression evaluation, iterative DFS, monotonic-stack problems (next greater element, largest rectangle in histogram).

Study more: Day 11: Stacks.

4. Queues#

FIFO: first in, first out. Use collections.deque, never a plain list (popping from the front of a list is O(n)).

Space: O(n)

1from collections import deque
2
3q = deque()
4q.append("first")     # enqueue
5q.append("second")
6front = q[0]          # peek -> "first"
7q.popleft()           # dequeue -> "first"

Best for: BFS on trees and graphs, level-order traversal, sliding-window maximum (as a monotonic deque), task scheduling and producer/consumer patterns.

Study more: Day 12: Queues and Day 20: Graph Traversals.

5. Hash Maps (Dictionaries)#

Key → value mapping backed by a hash table. Python’s dict. The single most useful structure in interviews.

The O(n) worst case happens only under pathological collisions or during a resize. Treat hash map operations as O(1) in interviews, but say you know the worst case exists. Interviewers listen for that.

Space: O(n)

1counts = {}
2for ch in "interview":
3    counts[ch] = counts.get(ch, 0) + 1
4
5# Or, idiomatically:
6from collections import Counter, defaultdict
7counts = Counter("interview")
8graph = defaultdict(list)   # great for adjacency lists

Best for: frequency counting, memoization, two-sum-style complement lookups, grouping (anagrams), caching, de-duplication with metadata.

Study more: Day 23: Hash Tables.

6. Sets#

A hash map without values. Membership tests in O(1) average.

Space: O(n)

1seen = set()
2seen.add(42)
3if 42 in seen:              # O(1) average
4    print("duplicate!")
5
6evens = {2, 4, 6}
7primes = {2, 3, 5}
8print(evens & primes)       # intersection -> {2}
9print(evens | primes)       # union -> {2, 3, 4, 5, 6}

Best for: duplicate detection, “have I visited this node?” checks in graph traversal, longest consecutive sequence, set-algebra problems.

Study more: Day 24: Sets.

7. Trees (Binary Search Trees)#

Hierarchical nodes; a BST keeps left < node < right, giving logarithmic operations when balanced.

Space: O(n); recursion stack adds O(h) where h is the height.

 1class TreeNode:
 2    def __init__(self, val):
 3        self.val = val
 4        self.left = None
 5        self.right = None
 6
 7def insert(root, val):
 8    if root is None:
 9        return TreeNode(val)
10    if val < root.val:
11        root.left = insert(root.left, val)
12    else:
13        root.right = insert(root.right, val)
14    return root

A BST built from sorted input degenerates into a linked list. That’s the O(n) worst case. Self-balancing variants (AVL, Red-Black) guarantee O(log n).

Best for: sorted data with dynamic inserts, range queries, in-order traversal producing sorted output, and the enormous family of tree-recursion interview questions.

Study more: Day 13: Trees Introduction, Day 15: Binary Search Trees, and Day 16: Tree Traversals.

8. Heaps (Priority Queues)#

A complete binary tree stored in an array, where every parent beats its children (min-heap: parent ≤ children). Python’s heapq is a min-heap.

Space: O(n)

 1import heapq
 2
 3nums = [5, 1, 8, 3]
 4heapq.heapify(nums)          # O(n)
 5heapq.heappush(nums, 2)      # O(log n)
 6smallest = heapq.heappop(nums)   # O(log n) -> 1
 7
 8# Max-heap trick: negate values
 9heapq.heappush(max_heap := [], -5)
10largest = -heapq.heappop(max_heap)

Best for: top-K problems, merging K sorted lists, running median (two heaps), Dijkstra’s algorithm, any “repeatedly grab the smallest/largest” pattern.

Study more: Day 17: Heaps and Day 28: Heapsort.

9. Graphs#

Vertices connected by edges. In interviews, the adjacency list (a dict of lists) wins almost every time.

BFS and DFS both run in O(V + E) with O(V) extra space.

 1from collections import defaultdict, deque
 2
 3graph = defaultdict(list)
 4for u, v in [(0, 1), (0, 2), (1, 3)]:
 5    graph[u].append(v)
 6    graph[v].append(u)      # omit for directed graphs
 7
 8def bfs(start):
 9    visited, q = {start}, deque([start])
10    while q:
11        node = q.popleft()
12        for nxt in graph[node]:
13            if nxt not in visited:
14                visited.add(nxt)
15                q.append(nxt)

Best for: anything with relationships, such as islands in a grid, course scheduling (topological sort), shortest paths, connected components, cycle detection.

Study more: Day 18: Graphs Introduction, Day 19: Graph Representations, and Day 21: Shortest Path Algorithms.

10. Tries (Prefix Trees)#

A tree keyed by characters, where each root-to-node path spells a prefix. Complexity depends on key length m, not the number of stored words.

 1class TrieNode:
 2    def __init__(self):
 3        self.children = {}
 4        self.is_word = False
 5
 6class Trie:
 7    def __init__(self):
 8        self.root = TrieNode()
 9
10    def insert(self, word):
11        node = self.root
12        for ch in word:
13            node = node.children.setdefault(ch, TrieNode())
14        node.is_word = True
15
16    def starts_with(self, prefix):
17        node = self.root
18        for ch in prefix:
19            if ch not in node.children:
20                return False
21            node = node.children[ch]
22        return True

Best for: autocomplete, spell-checking, prefix matching, word-search puzzles on grids. If a problem says “prefix”, think trie first. We cover tries in depth in Tries Explained Simply.

Study more: Day 58: Tries.

How to Actually Memorize This#

Don’t. Memorizing tables is fragile under interview pressure. Instead, internalize three rules that regenerate most of the table on demand:

1. Contiguous memory gives O(1) access but O(n) middle insertion: that’s arrays.
2. Pointers give O(1) insertion but O(n) access: linked structures.
3. Hashing trades order for O(1) average everything: maps and sets.

Trees and heaps are “logarithmic middle ground,” graphs are “cost proportional to what you touch (V + E),” and tries are “cost proportional to key length.”

The rest is practice. Our 60-day challenge dedicates a full day to each of these structures with implementations and exercises. Days 4–24 cover every structure in this cheatsheet in order. Sign up free and work through them one day at a time.

Related Articles#

• Hashing and Hash Functions: Efficient Data Retrieval
• Introduction to Merge Sort and Time Complexity
• Bit Manipulation Tricks for Coding Interviews
• Tries Explained Simply (With Real Interview Problems)

Happy coding, and good luck in that interview!