Card 07/ 07
Recap: Choosing a Data Structure
Operations first, costs second, and the built-in each language does or does not provide.
Choosing a data structure comes down to the five ideas below, each listed with the card that covers it. One habit links them: write down what the program does and how often, before naming any structure.
| The idea | Where |
|---|---|
| List the operations and how often each runs, cost them, and choose the structure cheapest for the frequent ones; ask the shape and removal questions first | Choosing a Data Structure by Its Operations |
| A rank is an ordered question, so a live leaderboard needs a balanced search tree with subtree sizes, not a heap | Choosing Example: A Leaderboard That Changes Every Second |
| Whole names alone are a hash set; a list of names by prefix makes it a trie | Choosing Example: Checking Usernames While They Are Typed |
| Java provides every structure up to a sorted map; Python lacks a sorted map; TypeScript lacks a heap, a queue and a sorted map | Built-In Structures in Python vs Java vs TypeScript |
| A loop over a whole set to find the smallest or the next value is an operation the structure does not offer, so the choice needs revisiting | Choosing a Structure Out of Habit |
The gaps in the standard libraries decide what a listing writes by hand, and none of them changes the choice itself: when the operations ask for a heap in TypeScript or a sorted map in Python, the answer is still that structure, written as one class. The table lists what each language leaves out.
| Language | Written by hand |
|---|---|
| Python | Balanced binary search tree; trie; union-find; graph |
| Java | Trie; union-find; graph |
| TypeScript | Queue; binary heap; balanced binary search tree; trie; union-find; graph |
Together they let you take a program you have not seen, list what it does, choose the structure that makes its frequent operations cheap, and know before writing a line whether your language provides it.
← → move through sections and cards