DSA Tutorial #10: When to Use Which Data Structure — Complete Guide

Choosing the right data structure is half the solution to any coding problem. In interviews, the first question is always: “What data structure should I use?” A wrong choice leads to slow solutions or unnecessary complexity. In this article, you will learn a decision framework for choosing the right data structure, see head-to-head comparisons, and get a complete cheat sheet you can reference any time.

This article covers everything from our first 9 articles in the series.

The Decision Framework

When you see a problem, ask yourself these questions in order:

1. What do I need to do most often?

2. What are my constraints?

3. Am I storing relationships or just values?

• Just values: Array, hash set, heap
• Key-value pairs: Hash map
• Hierarchical data: Tree
• Connections between items: Graph
• Groups of items: Union-Find
• Strings with shared prefixes: Trie

Time Complexity Comparison

Here is a side-by-side comparison of all data structures and their operation costs.

Core Operations

* If you have a reference to the node. Otherwise O(n) to find it first.

** Peek only (min or max). Arbitrary access is O(n).

*** Amortized with path compression and union by rank. m = length of the string (used in the Trie row).

Space Complexity

Head-to-Head Comparisons

Array vs Linked List

In practice: arrays (and dynamic arrays like ArrayList, list, slice) are almost always better because of CPU cache efficiency. Use linked lists only when you need O(1) insert/delete at known positions.

Hash Map vs BST

Heap vs Sorted Array

Stack vs Queue

BFS vs DFS on Graphs

Trie vs Hash Set (for strings)

Union-Find vs Graph DFS

Common Interview Patterns and Their Data Structures

Here are the most common interview patterns and which data structure solves them best.

Pattern 1: “Find something in O(1)”

Use a hash map or hash set. If you need O(1) lookup, hashing is your tool.

Examples: Two Sum, Contains Duplicate, First Unique Character

Pattern 2: “Top K” or “Kth largest/smallest”

Use a heap. Keep a heap of size k.

Examples: Kth Largest Element, Top K Frequent Elements, K Closest Points

Pattern 3: “Valid parentheses” or “Matching pairs”

Use a stack. Push opening brackets, pop when you see closing brackets.

Examples: Valid Parentheses, Min Stack, Daily Temperatures

Pattern 4: “Level-by-level” or “Shortest path”

Use BFS with a queue.

Examples: Binary Tree Level Order, Shortest Path in Grid, Word Ladder

Pattern 5: “Explore all paths” or “Find all combinations”

Use DFS with backtracking.

Examples: Permutations, Subsets, Word Search, N-Queens

Pattern 6: “Connected components” or “Group items”

Use Union-Find if edges come dynamically. Use DFS/BFS on a static graph.

Examples: Number of Islands, Accounts Merge, Redundant Connection

Pattern 7: “Autocomplete” or “Prefix matching”

Use a trie.

Examples: Implement Trie, Word Search II, Search Suggestions

Pattern 8: “Sorted data with insert/delete”

Use a balanced BST (TreeMap/TreeSet in Kotlin/Java, SortedList in Python).

Examples: Sliding Window Median, My Calendar, Data Stream as Disjoint Intervals

Pattern 9: “Process elements in order of priority”

Use a heap (priority queue).

Examples: Merge K Sorted Lists, Task Scheduler, Reorganize String

Pattern 10: “Sliding window with min/max”

Use a deque (monotonic queue).

Examples: Sliding Window Maximum, Shortest Subarray with Sum at Least K

Quick Decision Flowchart

Follow this flowchart when you face a new problem:

Need O(1) lookup by key?
  YES -> Hash Map / Hash Set
  NO  -> Continue

Need min/max repeatedly?
  YES -> Heap
  NO  -> Continue

Need sorted order?
  YES -> BST / Sorted Array
  NO  -> Continue

Working with strings and prefixes?
  YES -> Trie
  NO  -> Continue

Need to track connected groups?
  YES -> Union-Find
  NO  -> Continue

Working with a graph or grid?
  YES -> Need shortest path?
    YES -> BFS
    NO  -> DFS
  NO  -> Continue

Need LIFO (undo, matching)?
  YES -> Stack
  NO  -> Continue

Need FIFO (scheduling, ordering)?
  YES -> Queue
  NO  -> Continue

Default -> Array

Real-World Examples

Here is what powers real systems behind the scenes:

Common Mistakes

1. Using a sorted array when you need frequent inserts. Insert into a sorted array is O(n). Use a heap or BST instead.

2. Using DFS when BFS gives shortest path. DFS does not guarantee shortest path in unweighted graphs. Use BFS.

3. Using a hash map when you need sorted iteration. Hash maps are unordered. Use a BST or sort the keys separately.

4. Implementing a linked list when an array works. Arrays are almost always faster due to cache locality. Only use linked lists when you truly need O(1) insert/delete at known positions.

5. Forgetting that hash map worst case is O(n). Rare, but possible with bad hash functions. Mention this in interviews to show you understand trade-offs.

Interview Strategy

When the interviewer gives you a problem:

1. Identify the core operation. What do you do most? Lookup? Insert? Get min? Traverse?
2. Pick the data structure. Use the decision framework above.
3. State it out loud. “I will use a hash map because I need O(1) lookups.”
4. Consider trade-offs. “A heap gives me O(log n) insert and O(1) peek, which is better than sorting every time.”
5. Code it. Use your language’s built-in data structures — do not implement from scratch unless asked.

Interviewers care more about you choosing the right data structure than writing perfect code. A correct choice with a minor bug beats a wrong data structure with perfect syntax.

Practice Problems — Full Review

Go back and practice these problems. They cover all 9 data structures:

What’s Next?

Congratulations — you now know all the core data structures. In the next part of this series, we move to Algorithms, starting with Sorting Algorithms. You will learn the most important sorts, their trade-offs, and when each one is the best choice.

Next: DSA Tutorial #11: Sorting Algorithms

Full series: DSA from Zero to Interview Ready