Card 01/ 07
Choosing a Data Structure by Its Operations
List what the program does most often, then pick the structure that makes those operations cheap.
Choosing a data structure starts from what the program does with its data, not from the structures you happen to know: list the operations it performs and how often each one runs, then pick the structure that makes the frequent ones cheap. This card covers that method, the questions that separate one structure from another, and the operations each structure makes cheap or slow.
An operation is one thing the program asks of its data: add an item, find one by its key, take the smallest, read the tenth. Its cost is how its running time grows with n, the number of items, written in Big O. The method has three steps.
- Write down every operation, with how often it runs: on every request, every second, or once at start-up.
- Cost each operation in the structures that could hold the data.
- Choose the structure that is cheapest for the frequent operations, and accept a slow operation that runs rarely.
A cook chooses a container the same way, by what will happen to the food: a jar for something poured out a little at a time, a tray for things that must all be seen at once. The likeness breaks on one point: a kitchen rarely keeps one food in two containers, and a program often keeps the same items in two structures, because no single structure makes all of its frequent operations cheap.
The questions below sort a program into a structure. Ask them in order and stop at the first that fits. The early ones ask about the shape of the data and how items leave, which rule out the most.
When The items are things joined in pairs, and the program asks what each one is joined to
, chooseWhen The program merges groups and asks whether two items are in the same group, and never splits a group
, chooseWhen The keys are strings and the program asks about prefixes: every key that starts with these letters, or whether any does
, chooseWhen Items leave from one end only: either the item added last, or the item that has waited longest
, chooseA stack for the item added last, a queue for the item that has waited longest
When The program repeatedly removes the smallest or the largest item while new items keep arriving, and never needs the others in order
, chooseWhen The program asks questions that need the keys in order, such as the next key after a value, the keys in a range, or the smallest and the largest, while keys are added and removed
, chooseWhen The program looks single items up, adds them or removes them by a key or by their value, and order does not matter
, chooseWhen The program inserts or removes items in the middle of a sequence at a place it already holds a reference to, or at both ends, and seldom reads by position
, chooseA linked list, doubly linked when it must step backwards or remove a node it holds
When The program reads items by position, appends at the end and scans in order
, choose
Otherwise More than one of these at once: keep two structures over the same items and update both together.
Two pairs of branches differ by a few words. A heap fits only while the program wants the extreme item; once it asks for the next key after a value, it needs the keys in order, which a balanced search tree keeps. A hash map fits only when order does not matter at all.
The table sets out what each structure makes cheap and what it makes slow, for n items.
| Structure | Cheap operations | Slow operations |
|---|---|---|
| Dynamic array | Read by position O(1); append O(1) amortised | Insert or remove in the middle O(n); search by value O(n) |
| Linked list | Insert or remove at a node it holds O(1); add at either end O(1) | Read by position O(n); search O(n) |
| Stack or queue | Add and remove at its end O(1) | Any item but the one at the end: not offered |
| Hash map or set | Look up, add and remove by key O(1) on average | Smallest, next key or a range O(n) |
| Balanced binary search tree | Look up, add and remove O(log n); next key, smallest and range start O(log n) | Read by position, unless each node also counts its subtree |
| Binary heap | Read the smallest O(1); add and remove the smallest O(log n) | Search for any other item O(n) |
| Trie | Look up or add a word of length k in O(k); list the words with a prefix | Memory: a node for every distinct prefix |
Amortised means averaged over a long run of appends: one append that grows the array is slow, but the total stays O(1) per append. A frequent operation in the right-hand column is the sign of a wrong choice.
← → move through sections and cards