Choosing a Data Structure Is Choosing What to Make Cheap

Learn them as choices, not as implementations

Most people learn data structures as a list of things to implement: here is a linked list, write one, here is a binary tree, write one. Then they finish, remember roughly none of it, and go back to using an array for everything.

That happens because implementation is the least transferable part. You will implement a hash map approximately never. You will choose between a hash map and something else roughly every second week, usually without noticing you made a choice, and the cost of choosing badly shows up months later as a page that takes four seconds to load.

So learn them as a set of trade offs. Every structure makes one operation cheap by making another expensive, and the only question that ever matters is which operation your code performs most. Here are twelve pairings for recognising that.

The two that cover most of your work

1. Access by position + a known size → an array. Contiguous memory, constant time indexing, and the friendliest possible behaviour for the processor cache. It is the default for a reason, and a surprising amount of clever structure selection loses to a plain array of a few thousand items.

2. Lookup by key + no interest in order → a hash map. Constant time on average for insert, lookup and delete, paid for in memory and in the complete loss of ordering. If you find yourself scanning a list to find a matching item inside another loop, this is almost always the fix.

When order is the requirement

3. Sorted order + range queries → a balanced tree or a sorted structure. A hash map cannot answer "everything between these two values" without looking at everything. Trees keep order at logarithmic cost, which is what every database index is really doing underneath.

4. Always needing the smallest or largest + a changing set → a heap. Not a sorted list, which pays to keep the whole thing in order when you only ever look at one end. A heap gives you the extreme in constant time and reorders lazily, which is exactly the amount of work the problem requires.

5. Last in, first out + nesting → a stack. Undo, matching brackets, the call stack itself, depth first traversal. Whenever a problem has a shape where the most recent unfinished thing must be resolved first, you are describing a stack even if you have not named it.

6. First in, first out + fairness → a queue. Work to be processed in arrival order, or a breadth first traversal. The moment you want the oldest waiting item rather than the newest, the structure is decided.

When the shape of the data is the point

7. Hierarchy + parents and children → a tree. File systems, comment threads, the document your browser renders. Once you see that most traversal code is the same three lines with a different visit function, a great deal of recursive code stops looking hard.

8. Arbitrary relationships + traversal → a graph. Followers, dependencies, routes, permissions. Many problems that look novel turn out to be a graph problem you have already seen, and recognising that is worth more than any specific algorithm you might run on it.

9. Grouping things + repeated merges → a union find. Connected components, deduplication, anything where you keep discovering that two clusters are actually one. It is small enough to write from memory and does something no other structure does cheaply.

Choosing under real constraints

10. A cache + a size limit → a hash map plus a linked list. This is the one composite structure worth knowing by heart. Constant time lookup from the map, constant time recency updates from the list, which is how every least recently used cache you have ever used is built.

11. A hot loop + a performance problem → think about memory layout. Two structures with identical complexity can differ by an order of magnitude in practice, because one walks contiguous memory and the other chases pointers around the heap. Complexity notation deliberately hides the constant, and sometimes the constant is the whole story.

12. Genuine uncertainty + a deadline → an array or a hash map, and move on. Start with the obvious structure, write the test, and change it when a measurement tells you to. Most premature structure selection is optimisation in disguise, and it costs readability today for a problem that may never arrive.

What else belongs on this list

Deques, for anything where items arrive at one end and expire at the other, which an array will happily do while paying a linear cost every time something leaves the front. Tries, when the question is what starts with this rather than what equals this. Sets, because a map to a boolean communicates less than saying set. Immutable and persistent structures, which make concurrent reading safe by removing the question entirely, and which are worth understanding even if your language does not push you towards them. Bit sets, for dense integer membership where memory actually matters. And ring buffers, which quietly power a great deal of logging and audio and networking code.

The one I would add above all of those, though, is not a structure. It is the habit of asking, before you store anything, what you are going to ask of it later. Almost every bad structure choice is really a failure to answer that question at the point where it was cheap to answer.

The short version

Array for position, hash map for keys, and those two carry most days. Tree when order matters, heap when only the extreme matters, stack for nesting, queue for fairness. Tree, graph and union find when the shape of the relationships is the actual problem. Map plus list when you mean cache.

Underneath all fifteen is one question, asked before you write the storage rather than after: which operation is this code going to perform ten thousand times? Answer that and the structure is usually obvious. Skip it and you will find out from a production graph.