Choosing a Data Structure
Beginner · 12 min read · Data Structures Basics, Putting It Together
One table of every structure and operation, and a decision guide for picking one.
Picking the data structure is often the whole problem. Once you know you need "the minimum, repeatedly", the answer is a heap. Once you know you need "have I seen this?", it's a hash set.
The method
Every structure, every operation
* amortised.
Signals that point to a structure
A decision guide
Worked examples
"Return the first non-repeating character in a string."
Further reading
Key takeaways
- Choose by operations: list what must be fast, then find the structure whose fast operations cover them.
- Hash map for lookups, array for positions, stack and queue for arrival order, heap for repeated minimums.
- Use TreeMap for sorted keys with ranges, a trie for prefixes, and a graph for relationships.
- When one structure isn't enough, combine two and keep them in sync.
- Always say why: the operation, its cost, and the alternative you rejected.