Choosing a Data Structure
A decision guide from the operations a problem needs (lookup, order, dedupe, range, priority) to the Java structure that delivers them.
On this page
Half of solving an interview problem is choosing the right container. The candidates who move fast don't memorize solutions - they've internalized a map from the operations a problem needs to the data structure that makes those operations cheap. This lesson builds that map.
Start from the operations, not the structure
Don't ask "should I use a list or a map?" Ask "what does this problem need to do repeatedly?" and let the answer pick the structure:
| The problem needs… | Reach for | Because |
|---|---|---|
| Index access, order, duplicates | ArrayList | O(1) get by index, keeps insertion order |
| Fast membership / dedupe | HashSet | O(1) average contains and add |
| Key → value lookup | HashMap | O(1) average get/put |
| Always get the min or max | PriorityQueue (heap) | O(log n) insert, O(1) peek at the extreme |
| FIFO order (BFS, tasks) | ArrayDeque as a queue | O(1) add/remove at ends |
| LIFO order (undo, DFS) | ArrayDeque as a stack | O(1) push/pop |
| Sorted keys / range queries | TreeMap / TreeSet | O(log n) ops, ordered iteration, floor/ceiling |
The single most common interview move is: "I'm calling contains in a loop → O(n^2) → replace
the list with a HashSet → O(n)." Recognizing that instantly is worth more than any one algorithm.
// slow: List.contains is O(n), so this is O(n^2)
List<Integer> seen = new ArrayList<>();
for (int x : a) { if (seen.contains(x)) return true; seen.add(x); }
// fast: HashSet.contains is O(1) average → O(n) overall
Set<Integer> seen = new HashSet<>();
for (int x : a) { if (!seen.add(x)) return true; } // add returns false if already presentThe words in the problem are hints
Certain phrases point straight at a structure. "Unique" or "seen before" → a Set. "Count
of" or "group by" → a Map (often Map<K, Integer> or Map<K, List<V>>). "k largest" or
"next smallest" → a heap. "Most recent" / LIFO → a stack. "In order" / "process in
arrival order" → a queue. Train yourself to hear the structure in the problem statement.
A carpenter doesn't reach for the same tool every time and force it to fit; they read the job - "this needs to grip," "this needs to cut a curve" - and pick the tool built for that motion. Choosing a data structure is the same craft: read what the problem must do over and over (look up, keep sorted, grab the smallest), and pick the container whose cheap operation is exactly that motion. Force the wrong one and you're sawing with a hammer - an O(n^2) solution to an O(n) problem.
For each, name the structure and the key operation it makes cheap: (a) "return the first non-repeating character in a string"; (b) "merge k sorted lists and always take the smallest next element"; (c) "check if a string of brackets is balanced."
You're calling list.contains(x) inside a loop over n elements and it's too slow. What's the standard fix?
Key takeaways
- Choose a data structure from the operations a problem repeats, not by habit.
- Set for uniqueness, Map for key→value or counts, heap for min/max, stack for LIFO, queue for FIFO, TreeMap/TreeSet for sorted/range.
- The top optimization: a contains/lookup inside a loop → swap a List for a HashSet, O(n^2) → O(n).
- Problem wording hints at the structure: 'unique'→Set, 'count of'→Map, 'k largest'→heap, 'most recent'→stack.
- Match the container whose cheap operation is exactly the motion the problem needs.