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

1. Need fast lookup by key? Hash map.
2. Need sorted order? BST or sorted array with binary search.
3. Need min/max repeatedly? Heap.
4. Processing in LIFO/FIFO? Stack or queue.
5. Hierarchical data? Tree.
6. Connections between entities? Graph.
7. String prefixes? Trie.
8. 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.

How to Prepare Effectively

Successful interview preparation goes beyond memorizing answers. Here is a structured approach to data structures cheat sheet preparation:

• Research the company: Understand their products, culture, recent news, and competitors. This context shapes how you frame your answers.
• Practice with the STAR method: Structure your behavioral answers using Situation, Task, Action, Result. Our STAR method guide provides a detailed framework with examples.
• Prepare 8-10 stories: Have a bank of versatile stories covering leadership, conflict resolution, failure, teamwork, and initiative. Each story should have quantified results.
• Practice out loud: Answers sound different spoken versus in your head. Record yourself and listen for filler words, vague language, and stories that run too long.
• Prepare questions to ask: Having thoughtful questions for the interviewer demonstrates genuine interest and critical thinking.

Common Interview Mistakes

Avoid these errors that frequently cost candidates job offers:

• Rambling answers: Keep responses under 2 minutes. Use the STAR framework to stay structured and concise.
• Not quantifying impact: "Improved the process" is weak. "Reduced processing time by 40%, saving 15 hours per week" is compelling.
• Badmouthing previous employers: Always frame past experiences positively, even when discussing challenges or reasons for leaving.
• Neglecting your resume: Be ready to discuss every bullet point on your resume. If it is on the page, an interviewer may ask about it.
• Not following up: Send a thank-you email within 24 hours referencing specific topics from the conversation.

Build a Resume That Gets You Interviews

The best interview preparation starts with a resume that gets you in the door. Make sure your resume highlights the achievements and skills most relevant to your target role. Use strong action verbs and include ATS keywords from the job description.

Check resume examples for your target position, then build your professional resume with EasyResume to make a strong first impression before the interview even begins.