Why This Data Structure?
Five questions — what operations are frequent, what lookup is needed, does order matter, do duplicates matter, how large can it get — produce a recommendation with the case where it flips. The answer is derived, not remembered.
The situation, the reflex, and why it stalls
Every lesson starts where being stuck starts: someone has a problem, and the first move that comes to mind feels like progress.
A reviewer asks "why is this a map?" and you do not have an answer beyond "it seemed right". What five questions would have produced the answer, and how do you run them on a concept you have never seen?
I can list data structures — array, map, set, sorted map, queue — and I can say what each is. What I cannot do is look at a new concept, say a list of recent searches or a set of reserved seats, and say which one it should be. I pick something, and if someone asks why, I feel found out.
Match by resemblance. The concept looks like a list, so it becomes an array; it has ids, so it becomes a map; the tutorial for something similar used a set. Resemblance is fast and usually not wrong, which makes the missing reason easy not to notice.
Resemblance produces a structure with no argument attached, so when the structure turns out awkward — every render converts the map to an array — the awkwardness is coded around rather than traced back to a question that was never asked.
- Resemblance produces a structure with no argument attached, so when the structure turns out awkward — every render converts the map to an array — the awkwardness is coded around rather than traced back to a question that was never asked.
- The structure is chosen for the concept's noun rather than its verbs. "Recent searches" sounds like a list, so it becomes one; the frequent operation is "was this searched before?", which is a lookup, and the list scans for it on every keystroke.
- When the requirement changes — the seat map grows from a room to a stadium — nothing says which assumption the structure rested on, because none was written. The change is a fresh guess, and it often keeps the old structure out of inertia.
- Learning stalls with it. Structures learned as things — "a hash map is a table with buckets" — do not connect to the decision, so the DSA knowledge exists and the choice is still made by feel.
The move
Precisely enough to apply it to a problem you have never seen — not a slogan.
- Ask the five questions in order, of the operations rather than of the concept's name. Which operations are frequent? What lookup do they need — by key, by position, by range, none? Does order matter — insertion, sorted, or none? Do duplicates matter — must the same thing appear once, or may it repeat? How large can it get — a handful, thousands, unbounded?
- Let each answer eliminate or prefer. Lookup by key prefers a map or a set; a required insertion order prefers an array or a language whose map keeps order; "must appear once" prefers a set or a map key over an array with a check; "unbounded" turns a scan into a cost and persistence into a question. The recommendation is what survives all five.
- Attach the per-operation complexity to the recommendation, and the case where it flips. "Array; add O(n), view O(n) in order; flips to a map when the collection grows past the point where the scan is measurable, or when uniqueness must be structural." The flip condition is what makes the answer revisable.
- When the questions do not settle it — two structures survive — choose the simpler and write the other as the switch. The method produces a reason either way; what it never produces is "it seemed right".
The five questions as a pipeline
The questions are ordered because each one narrows the field for the next. Frequency says which operations the structure must serve; lookup says what those operations ask for; order and duplicates are rules the structure can keep for you; size says whether any of the costs are real. The Why This Data Structure? lab runs exactly this pipeline and shows where the recommendation changed.
Each stage has a way of failing, and the device names it. The characteristic one is answering from the noun — the concept "sounds like a list" — instead of from the verb, which the first stage exists to prevent.
- 1Frequent operations
Marks which of the operations run often — add and view for a cart, membership test for seats — so the structure is chosen for them and not for the rare ones.
fails by Listing every operation as equally important, so the structure optimises removal that happens once a session.
- 2Lookup
Says what the frequent operations look things up by: a key (product id), a position (the third item), a range (seats 10–20), or nothing (walk everything).
fails by Answering from the noun — "it has ids, so by key" — when the frequent operation walks everything and never looks up at all.
- 3Order
Decides whether the collection's order means something to the user (insertion order for a cart, ranked for search results) or only to the code.
fails by Assuming the language's map keeps order and building a cart whose display order is a runtime detail.
- 4Duplicates
Decides whether each element must appear once, and whether that rule should be structural (a key, a set, a unique constraint) or a line of code.
fails by Choosing an array and forgetting the line — the predict-the-bug case.
- 5Size and its bound
Says what bounds the collection — a person, the catalog, nothing — and therefore whether an O(n) scan is a cost or a rounding error.
fails by Designing for the largest imaginable case and paying its conversions at the size that actually arrives.
The output is a sentence: structure, cost per frequent operation, and the condition that flips it. If the pipeline ends in a structure that cannot be built in memory — an index, a table — it has routed you to another domain, which is a success.
What each answer prefers
The decision below is the pipeline's output for the structures a beginner can reach. It is deliberately not a lookup table from concept to structure; it is from answers to structure, so that the same table serves a cart, a seat map and a list of recent searches.
The costs are the honest half. A set that makes uniqueness structural gives up order; a map that makes lookup constant pays at the JSON boundary; an array that keeps order and serialises for free scans on every lookup. There is no row without a cost.
Given the five answers, which structure survives?
when Order means something, the collection is small and bounded, and it crosses a JSON or rendering boundary often. Lookup by key is acceptable as a scan at this size.
cost Every lookup is O(n); uniqueness is a line of code; the switch condition is size.
when The frequent operation looks up by key, the collection can grow, or "one per key" must be structural. The value carries what the key does not — quantity, holder.
cost Conversion at every serialisation; order is the language's promise, not the structure's; a second structure if a different order is displayed.
when The frequent operation is a membership test — is this seat taken, was this searched before — and nothing needs to be stored beside the key.
cost No order, no payload; the moment "who holds it?" becomes a read, it is a map.
when Lookup is by range or the order is computed from the elements — a price-ordered list, seats by row — and it changes often enough that re-sorting an array is the cost.
cost Log-time operations everywhere and a structure most languages make you think about; an array sorted once at render is usually enough.
when The collection must survive, be shared, or be enforced against clients you do not trust; uniqueness becomes a constraint and lookup becomes an index.
cost Every operation is a round trip and concurrency is real; the in-memory shape still has to be chosen for the code that touches the rows.
The questions you cannot answer yet
Sometimes one of the five has no answer, and the reflex is to guess. The board below turns the two most common gaps into questions with an experiment each. Note what the experiments have in common: they are small, they produce a number or a fact, and they are about the concept, not about the structure.
The assumed column is where resemblance hides. Writing "order matters" as an assumption rather than a fact is how it gets checked with the person who asked, instead of baked into a structure that cannot be changed without a migration.
- ✓Add and view are frequent; remove and change quantity are rare.
- ✓Add looks up by product id; view walks everything.
- ✓A product appears once, with a quantity — the rule found from the add-again example.
- ~The cart is displayed in the order things were added. To be confirmed with whoever owns the design; a cart sorted by price would move the order answer.
- ~One shopper, one cart, one process — the V0 assumption that the size question depends on.
? How big can a cart get?
becomes What bounds the number of distinct products in one cart — a shopper, a business rule, or nothing — and at what count does the add scan become measurable in this runtime?
experiment Build carts of ten, a thousand and a hundred thousand entries in a script; time a thousand adds against each; note the count at which the array and the map first differ measurably.
? Do we need the cart in order?
becomes Is insertion order a requirement the shopper sees, or an accident of the first implementation — and if the cart is later sorted by something else, is it sorted on render or stored sorted?
experiment Show the design owner two cart screenshots, one in insertion order and one sorted by price, and ask which is right; the answer decides whether order is stored or computed.
Both experiments take an hour and settle the two questions that resemblance answered in a second. The second one is also the difference between storing order and computing it, which is the derived-versus-stored question wearing a different hat.
The implementation ladder
Concept, examples, pseudocode, code, tests, production — for the concept this lesson is about. Code is the fourth tab, not the first.
Shopping Cart = A temporary collection of products the user intends to purchase, held between browsing and checkout.
- Does a cart have identity? Yes, weakly. Two carts with the same items are still two carts, because each belongs to someone and will become a different order. It needs an id once it leaves memory; in memory the variable is the identity.
- Who owns it? A shopper — a logged-in user or an anonymous session. The owner is part of the state because "my cart" has to be findable again.
- How long does it exist? From the first add until checkout or abandonment. Whether it survives a reload, a closed browser or a login is not a property of the concept; it is a persistence decision made later, and each answer changes where the cart lives.
- Should it survive reload? Usually yes for a store, usually no for a demo. V1 in memory says no; V2 browser storage says yes on one device; V3 server storage says yes everywhere the user is logged in.
- Should it survive login? Only if an anonymous cart and a logged-in cart are merged — a rule that does not exist in V1 and appears as a modification later.
- itemscollection of CartItemkeepThe cart is its items; without them nothing else means anything.
- items[].productIdidkeepThe reference to what is being bought. The catalog owns the product; the cart only points at it.
- items[].quantityinteger > 0keepTwo laptops is one entry with quantity 2, not two entries — the rule "one entry per product" needs a quantity to hold.
- owneruser id or session iddependsSo the cart can be found again by the person it belongs to.
- items[].productNamestringderiveIt would be convenient to render the cart without a catalog lookup.
- items[].pricemoneydependsThe total needs a price per item.
- totalmoneydropEvery screen shows the total.
- currencycodedependsPrices need a currency to be added.
- createdAttimestampdropAbandoned carts might be expired or emailed about.
- update Add item — the updated cart
- delete Remove item — the updated cart
- update Change quantity — the updated cart
- read View items — the list of entries — product id and quantity — for rendering
- domain Calculate total — the sum of price × quantity over the entries
- delete Clear cart — the empty cart
- • Every quantity is greater than zero.
- • One logical entry per product.
- • The total is never negative.
- • An unknown product cannot be added.
- • Quantity cannot exceed available stock — if inventory is enforced here.
How to do it
Most important first.
- Write the operations first, each with what it reads and changes (Inputs, Outputs and Side Effects); the five questions are asked of that list, and a list that is missing the frequent operation gives the wrong answer with confidence.
- Answer each question with the operation that made you answer it. "Lookup by key — because add looks for an existing product id" is checkable; "lookup by key — probably" is resemblance again.
- For the size question, ask what bounds it. A cart is bounded by a shopper's patience; a server's set of carts is bounded by the number of shoppers; a log is unbounded. The bound decides whether a scan is a cost or a rounding error.
- Write the recommendation as a sentence with the complexity and the flip: structure, cost of each frequent operation, condition that changes the answer (Complexity, Annotated Not Asserted).
- Run the Why This Data Structure? lab on a concept that is not the cart — reserved seats, recent searches — and compare its recommendation with the one you derived; where they differ, find which question you answered from the noun instead of the verbs.
Worked on a concrete problem
The move has to produce something. This is what it produced.
- The cart, through the five questions. Frequent: add and view; total on every render. Lookup: by product id, on add and change quantity. Order: insertion — the shopper expects the cart in the order things were added. Duplicates: a product must appear once, with a quantity. Size: a handful; bounded by a person. Recommendation: array of CartItem, add O(n) scan, view O(n) in order; flips to a map when the collection is large or held server-side keyed by owner.
- "Search products by name", through the same five. Frequent: lookup by a partial string, on every keystroke. Lookup: by prefix or substring, not by key. Order: results ranked, so a computed order rather than insertion. Duplicates: a product appears once in results. Size: the whole catalog — thousands, and read far more than written. Recommendation: not an in-memory array scanned per keystroke; the questions point at an index, which is a different domain's lesson and a different concept (
search-index), and the method's job was to say so. - Reserved seats for one show. Frequent: "is this seat taken?" and "take this seat". Lookup: by seat id. Order: none — nobody lists seats in reservation order. Duplicates: a seat is reserved once, and that is the rule that matters most. Size: a room — hundreds, bounded. Recommendation: a set of seat ids, because the frequent operation is a membership test and the rule is uniqueness; it flips to a map the moment "who holds it?" is a read, and to rows the moment two people can race for the last seat.
How you know it worked
What now exists that did not before, and what question you can now ask.
- The recommendation came out of the operations list, and each of the five answers names the operation that produced it.
- The per-operation cost is written beside the structure, and the flip condition is a sentence someone could check against a measurement or a new requirement.
- When a reviewer asks "why not X?", the answer is one of the five questions — "because order matters and X does not keep it" — rather than a defence of taste.
- The same five questions produce a sensible answer for a concept you have never implemented, which is the test that the method transferred.
The questions you can now ask
The field this whole domain exists for. After this lesson, these are the questions to put to an unfamiliar problem.
- ?Which operations are frequent, and which one would I be embarrassed to have made slow?
- ?What does each frequent operation look things up by — a key, a position, a range, or nothing?
- ?Does the order of the collection mean something to the user, or only to the code?
- ?Must each thing appear once — and if so, would I rather the structure enforce it or a line of code?
- ?What bounds the size, and at what size does the cheap answer stop being cheap?
What can go wrong
- The questions are asked of the concept's name. "A cart is a collection of items" answers none of them; "add looks up by product id" answers two. Asked of nouns, the method reproduces the resemblance reflex with extra steps.
- All five are weighted equally when one dominates. For reserved seats, uniqueness and the race for the last seat outweigh everything, and a method that averages five answers hides the one that decides.
- The size question is answered by imagining the largest possible case. "A cart could have a million items" is true and useless; the bound is a shopper, and designing for the imagined case adds a map with conversions for a size that never arrives.
- The recommendation is treated as the end. It is the input to From English to Pseudocode; a structure chosen and not written against is a decision without a consequence.
- Five questions take longer than resemblance, and for the many concepts where resemblance is right the time was spent confirming it.
- A recommendation with a flip condition has to be revisited when the condition trips; a structure chosen once and never questioned has the cheaper life until it does not.
- The method reaches structures — an index, rows — that are other domains' lessons, and the honest answer to "which structure?" is sometimes "not one you can build in memory this afternoon", which is a slower answer than a guess.
- "So a map whenever there is lookup by key." Only when that lookup is frequent and the collection is large enough for the scan to matter, or when key uniqueness must be structural; a cart looks up by key on add and is still an array, because the other four questions said so.
- "The five questions replace learning DSA." They route into it. The questions say "you need a structure whose membership test does not grow with size"; knowing that a hash set is that structure, and what it costs, is the DSA lesson (Problem Solving and DSA).
- "If two structures survive, the method failed." It succeeded: it told you the choice does not matter much yet, and the simpler one with a written switch is the correct output of that finding.
Where this applies
Problem-solving advice is stated as universal far more often than it is. These labels say what each method is specific to — and where CONTESTED appears, the note gives the strongest form of the opposing view.
- GENERALThe five questions apply to any collection-shaped state — carts, seats, sessions, recent searches. For state that is not a collection — a counter, a status — the questions collapse to "how large?" and the method is a formality.
- SIMPLIFIEDThe questions and the structures they reach — array, map, set, sorted, rows — are a teaching model; memory layout, cache behaviour and the runtime's actual map implementation are left out, and at scale they decide cases the five questions leave open.
- ILLUSTRATIVEThe room of hundreds of seats, the catalog of thousands of products and the cart of a handful of items are invented sizes for the shape of the argument; the size at which a scan becomes a cost is a measurement, not a number to quote.
Where the depth lives
This domain asks the question and hands the answer off by name.