The question behind every choice
There is no best data structure. Each one makes a few operations very cheap and pays for it by making others expensive. So the useful question is never "which is fastest?". It is:
Which operations will I do most often?
Same data, different questions
Here are four structures holding the same 15 numbers. They are asked eight "is this number here?" questions, and then four "what is the next number after this one?" questions. The bars count how many items each structure had to look at.
Items looked at so far (lower is better) · question: is X here?
Start. Four structures, each holding the same 15 numbers. First question type: is this number here?
For the first kind of question the hash map is unbeatable. It goes straight to the answer. Then the question changes, and it becomes the slowest of the four, because a hash map keeps nothing in order. To find "the next number after 31" it has to look at everything.
The sorted array and the tree were never the fastest, and they never fell apart either.
What each structure makes cheap
| Structure | Cheap | Expensive |
|---|---|---|
| Dynamic array | Read by position, add at the end, walk through | Insert or remove at the front or middle, search |
| Sorted array | Search, find the nearest value, ranges | Insert and remove, because items must shift |
| Hash map | Find, add and remove by key | Anything involving order |
| Set | "Have I seen this?" | Anything involving order |
| Search tree | Find, add, remove, and stay sorted | Slower than a hash map for plain lookups |
| Heap | Add, and remove the smallest | Finding anything else |
| Stack | Add and remove at one end | Reaching anything below the top |
| Queue | Add at one end, remove at the other | Reaching the middle |
| Linked list | Insert or remove once you are at the spot | Getting to the spot |
A few questions that settle it
How will you find an item?
These questions cover the large majority of everyday code and interview problems.
Example
Reading a problem for clues
"Find two numbers that add up to a target." You need to ask "have I seen 7 before?" many times. That is a set or a hash map.
"Keep the 10 highest scores as new scores arrive." You repeatedly need the smallest of your top 10, to compare against. That is a heap.
"Find all bookings between 2pm and 5pm." A range, in order. That is a sorted structure.
"Process jobs in the order they arrived." First in, first out. That is a queue.
When you are not sure
Start with a dynamic array for a list of things and a hash map for looking things up. They are the right answer more often than everything else combined, and they are easy to replace later if measuring shows a problem.
Key takeaways
- Every data structure makes some operations cheap and others expensive.
- Choose by the operations you do most, not by a general idea of speed.
- Hash maps are the fastest way to look up by key, and useless for anything ordered.
- Sorted arrays and trees answer "next", "nearest" and range questions.
- When unsure: a dynamic array for lists, a hash map for lookups.