Data Structures Interview Cheat Sheet: Big-O, Operations, and When to Use Each
A solid understanding of data structures is the foundation of every successful coding interview. Knowing which data structure to reach for, its time complexity for key operations, and its tradeoffs is what separates candidates who solve problems quickly from those who struggle. This data structures interview cheat sheet covers every structure you need to know, organized for fast reference during your preparation.
Bookmark this page and use it alongside our algorithm patterns guide to connect data structures with the problem-solving patterns they enable.
Big-O Notation Quick Reference
- O(1) - Constant: Hash map lookup, array index access.
- O(log n) - Logarithmic: Binary search, balanced BST operations.
- O(n) - Linear: Array scan, linked list traversal.
- O(n log n) - Linearithmic: Merge sort, heap sort.
- O(n^2) - Quadratic: Nested loops, bubble sort.
- O(2^n) - Exponential: Recursive subsets, brute-force combinations.
- O(n!) - Factorial: All permutations.
Arrays
Time Complexity
- Access by index: O(1)
- Search (unsorted): O(n)
- Search (sorted): O(log n) with binary search
- Insert at end: O(1) amortized
- Insert at position: O(n)
- Delete at position: O(n)
When to Use
Use arrays when you need fast index-based access, when data size is known, and for contiguous sequence problems. Arrays are the default choice unless you need a different structure's properties.
Common Interview Problems
Two Sum, Maximum Subarray, Product of Array Except Self, Container With Most Water. See our top 50 coding questions for details.
Linked Lists
Time Complexity
- Access by index: O(n)
- Search: O(n)
- Insert at head: O(1)
- Insert at tail: O(1) with tail pointer
- Delete: O(n) to find, O(1) to remove
When to Use
Use linked lists for frequent insertions/deletions at arbitrary positions, implementing stacks and queues, and LRU caches.
Common Interview Problems
Reverse Linked List, Merge Two Sorted Lists, Detect Cycle (Floyd's Algorithm), LRU Cache.
Stacks
Time Complexity
- Push: O(1)
- Pop: O(1)
- Peek: O(1)
- Search: O(n)
When to Use
Matching brackets, parsing expressions, DFS traversal, undo operations, and monotonic stack problems (next greater element, largest rectangle in histogram).
Queues
Time Complexity
- Enqueue: O(1)
- Dequeue: O(1)
- Peek: O(1)
- Search: O(n)
When to Use
BFS traversal, level-order tree traversal, task scheduling, and processing in arrival order.
Hash Tables (Hash Maps)
Time Complexity
- Insert: O(1) average, O(n) worst case
- Delete: O(1) average, O(n) worst case
- Search: O(1) average, O(n) worst case
When to Use
Fast lookups by key, counting frequencies, checking duplicates, memoization. Hash maps are the single most useful data structure in coding interviews. If your brute-force is O(n^2) because of repeated lookups, a hash map likely reduces it to O(n).
Common Interview Problems
Two Sum, Group Anagrams, Longest Consecutive Sequence, Subarray Sum Equals K, LRU Cache.
Binary Trees
Time Complexity (Balanced BST)
- Search: O(log n)
- Insert: O(log n)
- Delete: O(log n)
- Traversal: O(n)
Unbalanced worst case: All operations degrade to O(n).
Self-Balancing Trees
AVL Trees: Strictly balanced. Faster lookups but slower insertions.
Red-Black Trees: Approximately balanced. Faster insertions. Used in Java TreeMap, C++ std::map.
When to Use
Ordered data with efficient search/insert/delete, range queries, finding kth smallest element.
Heaps (Priority Queues)
Time Complexity
- Insert: O(log n)
- Extract min/max: O(log n)
- Peek min/max: O(1)
- Build heap: O(n)
When to Use
Top-K problems, kth largest/smallest element, merge K sorted lists, median from data stream. If the problem mentions "kth" or "top," think heap.
Graphs
Time Complexity (Adjacency List)
- BFS/DFS traversal: O(V + E)
- Add vertex: O(1)
- Add edge: O(1)
- Space: O(V + E)
Key Algorithms
BFS: Shortest path in unweighted graphs. Uses a queue.
DFS: Cycle detection, topological sort, connected components. Uses stack/recursion.
Dijkstra: Shortest path in weighted graphs. O((V + E) log V).
Topological Sort: Ordering tasks with dependencies. Only works on DAGs.
Union-Find: Connected components and cycle detection. Near O(1) per operation.
When to Use
Data with relationships: social networks, maps, dependency chains. Finding paths, connected components, or ordering with dependencies.
Tries (Prefix Trees)
Time Complexity
- Insert word: O(m) where m is word length
- Search word: O(m)
- Search prefix: O(m)
When to Use
Autocomplete systems, spell checkers, prefix matching, word search in grids, IP routing.
How to Choose the Right Data Structure
- Need fast lookup by key? Hash map.
- Need sorted order? BST or sorted array with binary search.
- Need min/max repeatedly? Heap.
- Processing in LIFO/FIFO? Stack or queue.
- Hierarchical data? Tree.
- Connections between entities? Graph.
- String prefixes? Trie.
- Fast access by index? Array.
Master these data structures and you will have the foundation for any coding interview. Pair this with our top 50 coding questions, a structured LeetCode study plan, and a polished resume built on EasyResume.