Prep Guide / Data Structures
Data Structures Cheat Sheet
What each core structure is best at, which operations are cheap, and when to reach for it.
Most interview solutions are a familiar data structure plus a small idea. Knowing the cost of each operation lets you pick the right structure instantly and justify it out loud. Here is the working set, with the operations that matter.
Complexity at a glance
| Structure | Access | Search | Insert | Delete | Notes |
|---|---|---|---|---|---|
| Array / list | O(1) | O(n) | O(n) | O(n) | Index access is instant; inserting/removing shifts elements. |
| Hash map / set | — | O(1)* | O(1)* | O(1)* | Unordered. *Average; O(n) worst case. |
| Stack | O(1) top | — | O(1) | O(1) | LIFO — last in, first out. |
| Queue / Deque | O(1) ends | — | O(1) | O(1) | FIFO, or insert/remove at both ends. |
| Linked list | O(n) | O(n) | O(1) at head | O(1) at head | Cheap splice once you hold the node. |
| Balanced BST | O(log n) | O(log n) | O(log n) | O(log n) | Keeps elements sorted. |
| Heap (priority queue) | O(1) peek | O(n) | O(log n) | O(log n) | Min or max always on top. |
| Graph (adjacency list) | — | — | O(1) add edge | — | O(V + E) space; traverse with DFS/BFS. |
Array
A contiguous block with O(1) random access by index — the default container. Great when you index by position or iterate. Weak when you must insert or delete in the middle, which shifts everything after it.
Hash map & hash set
The single most useful interview tool: O(1) average lookup, insert, and delete. Use a map to remember a value mapped to a count or index, and a set for fast membership tests. The cost is unordered storage and O(n) extra memory.
Stack and queue
A stack (LIFO) models "most recent first" — matching brackets, undo, depth-first search. A queue (FIFO) models "first come, first served" and powers breadth-first search. A deque generalizes both, allowing O(1) insertion and removal at either end, which is exactly what sliding-window-maximum needs.
Linked list
Nodes linked by pointers. Splicing a node in or out is O(1) if you already hold a reference to it, but there is no random access — reaching the k-th element is O(n). The fast/slow pointer trick answers most structural questions without extra memory.
Tree & binary search tree
A binary tree expresses hierarchy; a balanced binary search tree keeps elements ordered with O(log n) search, insert, and delete. In interviews you usually traverse a given tree (DFS for subtree-defined answers, BFS for level-order) rather than build a self-balancing one.
Heap (priority queue)
A heap keeps the minimum or maximum reachable in O(1) and supports insert and extract in O(log n). It is the right tool for "top K", "k most frequent", scheduling, and merging sorted streams. In Java, PriorityQueue is a min-heap by default.
Graph
Nodes connected by edges, usually stored as an adjacency list for O(V + E) space. Grids are graphs in disguise. The toolkit is small: DFS or BFS plus a visited set, with BFS giving shortest paths in unweighted graphs.
Picking the right one
- Need fast lookup by key or "have I seen this"? → hash map / set.
- Need the most recent item, or to match/undo? → stack.
- Need to process in arrival order or shortest path? → queue + BFS.
- Need the smallest/largest repeatedly? → heap.
- Need elements kept in sorted order with fast updates? → balanced BST.
Each structure maps to one or more patterns — see the patterns page for the recognition signals, then practice applying them.
← Back to the prep guide