Choosing a Data Structure Is Choosing What to Make Cheap

How to choose the right data structure: decide what must be cheap

If you want to know how to choose the right data structure, here is the whole answer in one sentence: every structure makes some operations cheap by making others expensive, so work out which operation your code will perform most, and pick the structure that makes that one cheap. Everything else in this post is detail around that idea.

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 the course, 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 every other 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 I would rather you learn data structures as a set of trade-offs. Below are twelve pairings of a situation and the structure it calls for, followed by a comparison table, the questions I ask before storing anything, and the mistakes I see most often.

Three questions to ask before you store anything

Before you pick a structure, answer these three. They take thirty seconds and prevent most bad choices.

• How will I find things later? By position, by key, by order, by "the smallest one", or by relationship? This decides more than anything else.
• What happens most often? Reads, inserts, deletes, or scans? A structure tuned for fast lookup can be slow to keep sorted, and the other way round.
• How big does it get? For a few hundred items almost anything works and the simplest choice wins. For millions of items the choice starts to matter, and sometimes memory matters as much as speed.

If you cannot answer the first question, you are not ready to choose. That is the most common root cause of a bad structure: nobody asked what the data would be asked later.

The two data structures 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. The cost is insertion or deletion in the middle, which shifts everything after it. Python's own time complexity notes spell this out: appending to a list is amortised O(1), inserting in the middle is O(n).

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. The same Python notes are honest about the catch: average O(1), but the worst case can degrade to O(n) when many keys collide. If you find yourself scanning a list to find a matching item inside another loop, a hash map is almost always the fix. A set is the same idea without values, and saying "set" communicates your intent better than a map to booleans.

Data structures and their uses when order matters

3. Sorted order + range queries → a balanced tree

A hash map cannot answer "everything between these two values" without looking at everything. A balanced search tree keeps order at logarithmic cost, so lookups, inserts and range scans all stay fast. This is what database indexes are doing underneath (usually a B-tree, a wide cousin of the binary tree), and it is why an index on created_at makes "orders from last week" quick.

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 costs logarithmic time per insert or removal, which is exactly the amount of work the problem needs. Schedulers, "top k" problems and Dijkstra's algorithm all run on heaps.

5. Last in, first out + nesting → a stack

Undo, matching brackets, the call stack itself, depth first traversal. Whenever 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 processed in arrival order, requests waiting for a worker, breadth first traversal. The moment you want the oldest waiting item rather than the newest, the structure is decided. One practical warning: a plain array used as a queue pays a linear cost every time it removes from the front. Use a proper double-ended queue, such as Python's collections.deque, which Python's time complexity notes recommend whenever you add or remove at both ends.

When the shape of the data is the point

7. Hierarchy + parents and children → a tree

File systems, comment threads, organisation charts, the page your browser renders. Once you see that most tree traversal code is the same few lines with a different "visit" function, a lot of recursive code stops looking hard. Grokking Tree Coding Patterns for Interviews is a good way to drill those shapes until they feel routine.

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. Store it as an adjacency list (a hash map from node to neighbours) unless the graph is small and dense.

9. Grouping things + repeated merges → union find

Connected components, deduplicating accounts that share an email, anything where you keep discovering that two clusters are actually one. Union find (also called disjoint set union) is small enough to write from memory and does something no other structure does as 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. The map gives constant time lookup; the doubly linked list gives constant time "move to most recent" and "drop the oldest". That is how a least recently used (LRU) cache is built. You rarely have to write it: Java's LinkedHashMap has an access-order mode that its official documentation describes as well suited to building LRU caches, and Python ships functools.lru_cache.

11. A hot loop + a performance problem → think about memory layout

Two structures with identical Big-O can differ by an order of magnitude in practice, because one walks contiguous memory and the other chases pointers around the heap. The well known latency numbers every programmer should know, originally compiled by Jeff Dean and Peter Norvig, put a main memory reference at roughly 200 times an L1 cache hit. Complexity notation deliberately hides the constant, and in a hot loop the constant is sometimes the whole story. This is why an array often beats a linked list even for workloads the textbook says favour the list.

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.

Data structure time complexity at a glance

Averages for the common operations. Treat this as a map, not a contract: real performance also depends on memory layout, language and data size.

If the Big-O column itself feels shaky, fix that first. Grokking Algorithm Complexity and Big-O and the free Big-O Cheat Sheet are both good places to start.

Common mistakes when choosing data structures

These are the ones I see most in code reviews and in student projects:

• A list where a set belongs. Checking if x in items inside a loop over a list of thousands is quadratic. Change one line and it is linear.
• Sorting to find one thing. Sorting a whole collection to get the minimum, or the top three, when a single pass or a small heap would do.
• An array used as a queue. Removing from the front of an array shifts every element. It works in testing and crawls in production.
• Picking a clever structure nobody else can read. A skip list or a trie in the wrong place costs every future reader. Use it when a measurement demands it.
• Ignoring the database. The most important structure in most applications is the index on your table, not anything in your code. Harvard's free CS50 Introduction to Databases with SQL covers indexes in plain terms.

What else belongs on this list

• Deques, for anything where items arrive at one end and expire at the other.
• Tries, when the question is "what starts with this" rather than "what equals this", such as autocomplete.
• Immutable and persistent structures, which make concurrent reading safe by removing the question entirely.
• Bit sets, for dense integer membership when memory genuinely matters.
• Ring buffers, which quietly power a lot of logging, audio and networking code.

The one I would add above all of those is not a structure. It is the habit of asking, before you store anything, what you are going to ask of it later.

How to choose the right data structure in practice

Reading a comparison table does not make the choice automatic. Practise it like this:

• Solve problems by structure first. Spend a week on hash map problems, a week on heaps, and so on, then mix them. The DSA roadmap orders them for you, and my post on how to learn DSA from scratch gives a 12-week plan.
• Say the operation before the structure. "I need the smallest item repeatedly, so a heap." If you cannot name the operation, you are guessing.
• Read one real codebase. Look at how a library you use stores its data and ask why. The question on how to read and understand a large codebase has a method.
• Profile one slow thing. Next time something feels slow, measure before you change the structure. You will be surprised how often the answer is an index or a nested loop.

For structured practice, Grokking Data Structures & Algorithms for Coding Interviews walks through each structure with problems, and the DSA cheat sheet keeps the operations and costs on one page. Once the structures feel natural, the next step is recognising problem shapes, which I cover in fifteen problem shapes and the move that solves each.

My honest read

Array for position, hash map for keys, and those two carry most days. A tree when order matters, a heap when only the extreme matters, a stack for nesting, a queue for fairness. A tree, a graph or union find when the relationships are the problem. A map plus a list when you mean cache.

Underneath all twelve is one question, asked before you write the storage rather than after: which operation will this code perform ten thousand times? Answer that and the structure is usually obvious. Skip it and you will find out from a production graph. This is also one of the fundamentals worth learning as a software engineer, because it will outlast every framework you use.

Learn it on Sefism

• DSA roadmap and the DSA cheat sheet
• Grokking Data Structures & Algorithms for Coding Interviews for structured practice
• Grokking Algorithm Complexity and Big-O if Big-O still feels shaky
• VisuAlgo to see each structure in motion
• Fifteen problem shapes and the move that solves each
• Programming roadmap if you are still learning your first language

FAQ

How do I choose the right data structure for a problem?

Work out which operation happens most (lookup by key, access by position, finding the smallest, keeping order) and pick the structure that makes that operation cheap. Accept that something else becomes more expensive.

When should I use a hash map instead of an array?

Use a hash map when you look things up by a key such as an ID or a name and do not care about order. Use an array when you access items by position or iterate over all of them in order.

Is a linked list ever better than an array?

Occasionally, when you insert or remove at a node you already hold, as in an LRU cache. For most everyday work a dynamic array is faster because its memory is contiguous and cache friendly.

What is the difference between a heap and a sorted array?

A sorted array keeps everything in order, which makes inserts slow. A heap only guarantees that the smallest (or largest) item is at the top, so inserts and removals are logarithmic. Use a heap when you only need the extreme.

Which data structures should beginners learn first?

Arrays, hash maps and sets, then stacks and queues, then trees and heaps, then graphs. That order matches how often you will use them in real work.

Ask your own question

If your situation is different from anything here, the career questions library has honest answers to the questions students and engineers ask me most.

Want a learning roadmap built around you, written answers to your own questions and a place to discuss your FYP? Create your free Sefism account. Members can also book a one to one session when they want to talk it through.

Stay in touch

• LinkedIn: where I share roadmaps, career advice and honest takes on hiring. Follow, or message me.
• X (Twitter): short practical thoughts on engineering and careers.
• Instagram: quick tips and a more personal side.
• Sefism Discord: meet other students and engineers working through the same job market and share what is working.
• Sefism on YouTube: walkthroughs and talks.