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 — 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!