32 of 32 · 6 min
Choosing, which is the actual skill
Eleven pages of structures. The skill is not remembering them: it is picking one and being able to say why.
The one table to keep
| Structure | Index | Search | Insert | Delete | Ordered |
|---|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) | Yes |
| Sorted array | O(1) | O(log n) | O(n) | O(n) | Yes |
| Linked list | O(n) | O(n) | O(1)* | O(1)* | Yes |
| Stack | n/a | n/a | O(1) | O(1) | LIFO |
| Queue | n/a | n/a | O(1) | O(1) | FIFO |
| Hash table | n/a | O(1) avg | O(1) avg | O(1) avg | No |
\* at a position you already hold.
Three questions, in order
1. What do I do most? Not what the data is: what the program does to it ten thousand times a second. Mostly lookups by key means a hash table, whatever the data looks like.
2. Do I need order? Sorted output, a range query, "the next largest": a hash table cannot do any of them, however fast it is at the rest.
3. What is the worst case, and does it matter? A hash table's O(n) worst case is fine in a script and unacceptable in something an attacker can reach.
Worked examples
| The problem | The structure | Because |
|---|---|---|
| Have I seen this? | Hash set | Membership is all you need |
| Count each word | Hash map | Key to number |
| Undo | Stack | Most recent first |
| Print jobs | Queue | Arrival order |
| Leaderboard, sorted | Sorted array or heap | Order is the point |
| Fixed grid of pixels | Array | Index arithmetic |
The habit worth forming
Before writing a loop, ask what it costs when the input is a million. That single question would have saved the student on page one four minutes and a term of confusion, and it costs about five seconds to ask.