MySmartCoPilot
Ask Passes Your pass 7 days left 1 day left Last day

Your country

Tools that support it use your country for local currency, number formats, units and paper size. Your choice is saved only in this browser.

Data Structures & Algorithms (DSA)  Module 21 – Algorithms in practice

Choosing the right data structure

Pick a data structure from the operations a program needs and how often it runs each, then back the choice with complexity, a measurement and its costs.

  • Intermediate
  • 25 minutes
  • Examples run with Python 3.14.8, Pyodide 314.0.7, Node.js 24.21.0 and quickjs 0.32.0
  • By MySmartCoPilot
Free: Start from the operations and how often they run · A first decision guide · Weighing more than speed · Check yourself. With a pass: 2 in-depth parts and 3 interview answers, about 15 minutes.

What you will learn

  • Choose structures from the required operations and their frequencies
  • Justify a choice with complexity and measurement
  • Weigh factors other than speed, such as memory, simplicity and maintainability

Before you start

What you’ll learn · Before you start

What you will learn

  • Choose structures from the required operations and their frequencies
  • Justify a choice with complexity and measurement
  • Weigh factors other than speed, such as memory, simplicity and maintainability

Before you start

On this page

Choose a data structure by listing the operations the program performs, such as insert, delete, find, smallest, in order, by range or by prefix, and how often each one runs. Then pick the structure whose costs are lowest for the operations that run most often, back the choice with its complexity and one measurement at the expected size, and weigh what speed does not show: memory, the time to write and maintain the code, and patterns in the data. The operations decide, not the structure’s popularity: a hash map is wrong the day the program needs “everything between two keys”, and a balanced tree is wasted on a program that only ever asks “is this key present?”.

Start from the operations and how often they run

Take a ticket waitlist with about 5,000 people waiting. Every minute 10,000 people join at the back and 10,000 are served from the front; 500 cancel their ticket, and 2,000 ask for their position in the queue. Before writing code, price each candidate: the cost of every operation, from its documented complexity, times how often it runs.

Pricing three candidates for a waitlist Python · core/waitlist_costs.py 
# A ticket waitlist with about 5,000 people waiting. Each candidate structure is priced by the cost of every operation
# (the number of elements it touches, from its documented complexity) times how often the operation runs in a minute.
# This is a model, not a timing: it shows which operation dominates each candidate before any code is written.
import math

N = 5_000
per_minute = {"join at the back": 10_000, "leave from the front": 10_000, "cancel a ticket": 500, "ask for my position": 2_000}

candidates = {
    "list": {  # pop(0) and remove() move every element after the one removed; index() scans from the front
        "join at the back": 1, "leave from the front": N, "cancel a ticket": N, "ask for my position": N / 2,
    },
    "collections.deque": {  # both ends in O(1); remove() and index() still scan
        "join at the back": 1, "leave from the front": 1, "cancel a ticket": N, "ask for my position": N / 2,
    },
    "OrderedDict by ticket": {  # insert, delete and pop the oldest in O(1); a position needs a walk from the front
        "join at the back": 1, "leave from the front": 1, "cancel a ticket": 1, "ask for my position": N / 2,
    },
}

for name, cost in candidates.items():
    total = sum(per_minute[op] * cost[op] for op in per_minute)
    worst = max(per_minute, key=lambda op: per_minute[op] * cost[op])
    share = per_minute[worst] * cost[worst] / total
    print(f"{name:22} {total:12,.0f} element visits a minute; {share:.0%} of them to {worst!r}")

steps = math.ceil(math.log2(1_000_000))
print(f"a counting tree over a million ticket numbers answers a position in about {steps} steps instead of {N // 2:,}")

Output

list                     57,510,000 element visits a minute; 87% of them to 'leave from the front'
collections.deque         7,520,000 element visits a minute; 66% of them to 'ask for my position'
OrderedDict by ticket     5,020,500 element visits a minute; 100% of them to 'ask for my position'
a counting tree over a million ticket numbers answers a position in about 20 steps instead of 2,500

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 waitlist_costs.py

A list is ruled out by one operation: serving from the front moves every remaining ticket, 87 % of its work. A deque serves both ends in O(1), and then the position queries dominate. An OrderedDict keyed by ticket also cancels in O(1), and still spends all its work walking to answer positions. The model points at the one operation left to fix: counting how many people are ahead of a ticket. A Fenwick tree over join numbers answers that count in O(log n), about 20 steps instead of 2,500, so the right design combines two structures, each doing what it is best at.

A first decision guide

A flow of four questions about the operations a program needs, each yes pointing to a hash map, heap, balanced tree or trie.List the operationsand how often each one runsOnly exact lookups by key?Hash map or hash setThe smallest or largest, again and again?Heap (priority queue)Sorted order, ranges, floor or ceiling?Balanced search tree,or a sorted array if updates are rarePrefixes of strings, or sums over ranges with updates?Trie for prefixes;Fenwick or segment tree for rangesOtherwise: an array (a list),the simplest and most compactyesnoyesnoyesnoyesno

The first questions to ask about the operations

Text description of the diagram

The diagram starts with "List the operations and how often each one runs" and then asks four questions in turn. Each "yes" leads to a family of structures; each "no" leads to the next question.

  1. Only exact lookups by key? Yes: a hash map or hash set.
  2. The smallest or largest, again and again? Yes: a heap, also called a priority queue.
  3. Sorted order, ranges, floor or ceiling? Yes: a balanced search tree, or a sorted array if updates are rare.
  4. Prefixes of strings, or sums over ranges with updates? Yes: a trie for prefixes, a Fenwick or segment tree for ranges.

If every answer is no, use an array or list, the simplest and most compact structure. When several answers are yes, the operations that run most often decide, and two structures can be combined.

  • Exact lookups (is it there, what is its value): a hash map or hash set, O(1) expected per operation, with no order.
  • The smallest or largest, again and again: a heap (priority queue), O(log n) to insert and remove, O(1) to peek.
  • Sorted order, ranges, floor and ceiling: a balanced search tree, O(log n) per operation, or a sorted array if updates are rare, since each insertion into it is O(n).
  • Both ends of a sequence: a deque or a ring buffer, O(1) at either end.
  • Everything with a given prefix: a trie, O(length of the prefix) to reach the matches, or a sorted list with binary search.
  • Sums or minimums over ranges, with updates: a Fenwick tree or a segment tree, O(log n) per update and per query.
  • “Seen before?” with very little memory: a Bloom filter, a few bits per key, with false positives only.
  • Which items are connected, as groups merge: union-find, nearly O(1) per operation.

When several needs apply, the most frequent operation decides, and two structures can be combined: a hash map with a heap, or an ordered dict with a counting tree, as in the waitlist. Prefer the standard library’s structure unless a measurement says otherwise, and write the reason in a comment beside it. The same method settles a live leaderboard, an autocomplete box, a booking calendar and a log deduplicator, and each ends with a different combination.

Weighing more than speed

The ACM/IEEE-CS/AAAI curriculum guidelines for algorithms ask students to discuss factors other than computational efficiency that influence a choice, naming programming time, maintainability and patterns in the input data, and to weigh the economic and environmental cost of inefficient algorithms. In practice that means four more questions:

  • Memory: how many bytes per item at the expected size, and does the structure still fit?
  • Simplicity: will the next person who changes this code understand it, and does the library already have it?
  • The data: is it already sorted, mostly small, or full of duplicates?
  • Change: which new query is likely next year, and how hard is it to add?

Check yourself

Check yourself

6 questions about this lesson. Every answer and why it is right is on the page, behind “Show the answer”. Your score stays in this browser.

  1. Question 1 of 6 A service checks every request's user ID against a blocklist of 2 million IDs and never needs them in order. Which structure fits?

    Choose one answer.

    Show the answer

    Answer: A hash set, for O(1) expected lookups

    The only operation is "is this ID in the set?", an exact lookup, which a hash set answers in O(1) expected time. A tree also works but pays O(log n) for an order nobody uses; a list pays O(n) on every request.

  2. Question 2 of 6 A job runner repeatedly takes the job with the earliest deadline and adds new jobs as they arrive. Which structure fits?

    Choose one answer.

    Show the answer

    Answer: A min-heap keyed by deadline

    "Take the smallest, add new ones" is exactly a priority queue: a binary heap does both in O(log n) and reads the smallest in O(1). Sorting after every insertion costs O(n log n) each time, and a hash map has no notion of the smallest.

  3. Question 3 of 6 A shop must answer "the cheapest product costing at least 500" while products are added and removed all day. Which structure fits?

    Choose one answer.

    Show the answer

    Answer: A balanced search tree (an ordered map) keyed by price

    "The smallest key at least x" is a ceiling query, which needs sorted order with fast updates: an ordered map answers it, inserts and removes in O(log n). A hash map has no order, and a heap only knows its smallest item, not the smallest above a threshold.

  4. Question 4 of 6 A table of 50,000 postal codes is loaded once a day and then searched millions of times by exact code and by range. What is the simplest good choice?

    Choose one answer.

    Show the answer

    Answer: A sorted array searched with binary search

    With no updates between loads, a sorted array gives O(log n) exact and range searches in the most compact, cache-friendly layout. A balanced tree is needed only when insertions and deletions are frequent; a linked list cannot be binary-searched.

  5. Question 5 of 6 A structure is used for 1 million lookups and 10 inserts a day. Candidate X: lookups O(1), inserts O(n). Candidate Y: both O(log n). For n = 1 million, which costs fewer steps a day?

    Choose one answer.

    Show the answer

    Answer: X, because the rare O(n) inserts cost about 10 million steps, far less than the lookups saved

    Weigh each cost by its frequency. X: 1,000,000 × 1 + 10 × 1,000,000 = 11 million steps. Y: 1,010,000 × about 20 = about 20 million steps. The frequent operation decides; a measurement then confirms the estimate.

  6. Question 6 of 6 Besides running time, which of these belong in the decision, according to the curriculum guidelines this lesson follows?

    Choose every answer that is right.

    Show the answer

    Answer:

    • The programming time and maintainability of the code
    • Patterns in the input data, such as data that arrives already sorted
    • The memory each candidate needs at the expected size

    The ACM/IEEE-CS/AAAI curriculum asks students to weigh factors other than efficiency, naming programming time, maintainability and patterns in the input data; memory is a cost of its own. A structure's number of features is not a reason to choose it: the operations the program needs are.

Five design briefs, from operations to a structure Pro

Each brief below starts from the operations and their frequencies and ends with a structure and its costs. The first is built and checked against a plain list; the other four are worked through and compared in one table.

In this part:

  • The waitlist built: an ordered dict and a Fenwick tree, checked
  • Four more briefs, worked with numbers

1 runnable example (Python) · about 3 minutes

Opening this part with your pass…

This part opens with any MySmartCoPilot pass.

  • Pro pass · 1 week₹79$2.99
  • 30 days₹179$5.99
  • 1 year₹1,699$45

One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.

Choose a passI have a licence key

It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).

Measuring before committing, and recording the decision Pro

Complexity narrows the candidates; a measurement at the expected size chooses between them, and a written record keeps the reasons for the next person. This part benchmarks two leaderboard designs, measures what three layouts cost in memory, and gives a rubric for defending a choice.

In this part:

  • Two leaderboard designs, measured
  • Memory: the other cost, measured
  • A decision record, and when to revisit it

2 runnable examples (Python) · about 3 minutes

Opening this part with your pass…

This part opens with any MySmartCoPilot pass.

  • Pro pass · 1 week₹79$2.99
  • 30 days₹179$5.99
  • 1 year₹1,699$45

One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.

Choose a passI have a licence key

It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).

Interview questions

  1. Fresher to mid · Warm-up

    What do you ask before choosing a data structure for a new feature?

    Which operations the feature performs (insert, delete, find by key, the smallest, sorted order, ranges, prefixes) and how often each one runs, because the most frequent operations decide. Then the sizes: how many items now and in a year, and how many bytes each takes. Then the shape of the data: already sorted, many duplicates, small integers in a known range. Finally the costs beyond speed: whether the standard library already has a structure that fits, how easy the code is to maintain, and which query is likely to be added next. With those answers, price each candidate by its costs times the frequencies, and confirm the winner with one measurement.

  2. Mid to senior

    A game has 10 million players. Scores change 50,000 times a second, the top 100 are shown 1,000 times a second, and players ask for their rank 5,000 times a second. Which structures would you use, and what does each operation cost?

    First step and follow-ups

  3. Mid to senior

    A search box suggests the 5 most popular product names that start with what the user has typed, over 2 million products, at 20,000 requests a second, and popularity changes every hour. Compare a sorted list with binary search against a trie, and choose.

    First step and follow-ups

  4. Fresher to mid

    A colleague wants to replace a Python list of 100,000 order IDs with a linked list, because new IDs are inserted in the middle and "inserting into a linked list is O(1)". Evaluate the proposal with numbers, and say what you would measure.

    First step and follow-ups

Key takeaways

  • List the operations and how often each runs; the most frequent operations decide.
  • Price each candidate before coding: its documented costs times the frequencies show which operation dominates.
  • Combine structures when no single one is good at every frequent operation, as the waitlist does.
  • Weigh memory, simplicity, the shape of the data and likely changes, not only the running time.

References

Related tools

Python Online Compiler Real CPython in your browser — with stdin, files and a stop button. Big Number Calculator Every digit exact: huge sums, products, powers, roots and factorials.

Report a problem with this lesson