Skip to content
Tutorials Center
My learning

Topics

Lesson 219 of 225 ยท Practice and Review

Choosing the Right Data Structure

Pick the right data structure by the operations you need. Decision tables, Python built-ins versus custom code, counted comparisons and real system examples.

A data structure is a promise about which operations are cheap. A list promises cheap access by position. A set promises cheap membership tests. A heap promises that the smallest item is always at hand. No structure is cheap at everything, so "which structure should I use?" is really the question "which operations will my program do most, and which of them must be fast?"

This lesson turns that question into a routine. You list the operations, look them up in a table, check what Python already ships, and only build something custom when nothing built in fits. Along the way you will count comparisons and moves instead of timing code, because counts are the same on every machine and show exactly where the cost comes from.

Step 1: list the operations

Before naming a structure, write down what the program does with the data. For example, a login-session store might need: add a session, look up by token, remove when it expires, find the oldest session. Each verb is an operation, and the frequent ones decide the design. Ask these questions:

  • Do I look things up by position (index), by key (name, id), or by value (is this in there)?
  • Do I need the items in order (sorted, or insertion order)?
  • Do I need the smallest or largest repeatedly?
  • Do I add and remove at one end, both ends, or the middle?
  • Do I need prefix, range or nearest value queries?
  • Do I care about relationships between items (a graph)?
  • How big can the data get, and how many queries per update?

Step 2: the master table

Here is what the common structures offer. "Avg" means average case; n is the number of items.

Structure Index access Search by value Insert Delete Min / max Ordered iteration
list O(1) O(n) end O(1) amortized, middle O(n) end O(1), middle O(n) O(n) after a sort
tuple O(1) O(n) immutable immutable O(n) after a sort
dict / set by key O(1) avg O(1) avg O(1) avg O(1) avg O(n) insertion order (dict), none (set)
collections.deque ends O(1), middle O(n) O(n) both ends O(1) both ends O(1) O(n) insertion order
heapq (list as heap) n/a O(n) O(log n) min O(log n) min O(1) no
sorted list + bisect O(1) O(log n) O(n) shift O(n) shift O(1) yes
balanced tree (not built in) n/a O(log n) O(log n) O(log n) O(log n) yes
trie n/a O(L) key length O(L) O(L) n/a alphabetical
linked list (custom) O(n) O(n) after a known node O(1) after a known node O(1) O(n) insertion order

Some details matter more than the table shows. dict lookup is O(1) on average; a very bad hash function or adversarial keys can degrade it. list.insert(0, x) and list.pop(0) are O(n) because every other element must move. A heap does not keep everything sorted, only the minimum is guaranteed to be first.

Step 3: let counts show the difference

Let us make the table concrete. First, membership: finding out whether a value is present. The next program counts the checks a linear scan and a binary search make on a missing value, and compares them with a single set lookup:

Python Counting steps: list scan, binary search, set

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The scan grows with n, binary search grows with log2(n), and the hash lookup stays flat. That is why "does this exist?" should almost always be answered with a set or dict, unless you need sorted order too. The price of the set is memory (it stores hashes and spare slots) and the loss of order.

Next, queues. A Python list is a fine stack (append and pop at the end), but dequeuing from the front means sliding every remaining element one place left. The program below models that cost and compares it with collections.deque, which is built for both ends:

Python A list as a queue versus a deque

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The total is about n^2 / 2 moves: quadratic work for something that should be linear. Use deque whenever you take items from the front (BFS, task queues, sliding windows).

Finally, "give me the largest few". Sorting everything is wasteful when you want three items. The code counts comparisons made by sorted and by heapq.nlargest:

Python Counting comparisons: sort versus heap

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For k much smaller than n the heap does roughly n comparisons while sorting does about n log n. As k approaches n, the advantage disappears, and just sorting is simpler.

Step 4: know what Python gives you

Before writing a class, check the standard library. Most real needs are already covered:

Need Reach for Why
Counting occurrences collections.Counter most_common(k), arithmetic on counts
Grouping items by key collections.defaultdict(list) no key-existence checks
FIFO queue, both-ends access, fixed-size history collections.deque (maxlen=) O(1) at both ends, drops old items itself
Min or max repeatedly, top-k, merging sorted inputs heapq push, pop, nlargest, merge
Sorted data with binary search bisect bisect_left, bisect_right, insort
Memoisation functools.cache caches function results
Fixed list of numbers, compact array.array stores raw values, not objects
Set of values that cannot change (dict key) frozenset, tuple hashable
Recently-used order collections.OrderedDict (move_to_end) building an LRU cache

Notably absent: a balanced search tree, a linked list, a trie, a graph, a union-find. Those you build yourself (or install a package like sortedcontainers), and they appear in the tutorial as custom classes. The next program tours the standard tools in one go:

Python A tour of the standard library structures

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Step 5: match structures to real systems

The same operations show up in every real product. Here are five tiny systems, each built on the structure its operations ask for:

Python Five tiny systems, five structures

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice the pattern: the browser history needs the last thing visited (a stack), the printer needs the oldest waiting job (a queue), the scheduler needs the most urgent (a heap), friend suggestions need set operations on neighbours (a graph as a dict of sets), and autocomplete needs prefixes (a trie). The operations chose the structure.

A decision flow

TEXT
Need lookup by key?                         -> dict (or set if only membership)
Need the smallest/largest repeatedly?       -> heap
Need items in sorted order with inserts?    -> sorted list (small), balanced tree (large)
Need "closest value" or range counts?       -> sorted list + bisect
Take items from the front?                  -> deque
Take items from the end only (undo, parse)?-> list as a stack
Need prefix queries?                        -> trie
Need relationships between things?          -> graph (dict of lists/sets)
Need to group items into connected sets?    -> union-find
Fixed size, index access, numeric?          -> list or array

Add the most important extra dimension: frequency of operations. A structure that is slow to update but fast to query (a sorted array with prefix sums) is excellent when you read a million times and write once. Reverse it for the opposite workload. When both are frequent, look at structures that balance them, such as the Fenwick tree or segment tree.

Common mistakes

  • Using a list for membership tests in a loop: if x in big_list inside a loop is a hidden O(n^2). Convert to a set once.
  • Using list.pop(0) or insert(0, x) in a loop instead of a deque.
  • Sorting repeatedly inside a loop when a heap or a sorted structure would keep order for free.
  • Choosing by habit (always a dict, always a list) instead of listing the operations first.
  • Over-engineering: a custom tree for 50 items. For small n, a list and a scan is faster to write and often faster to run.
  • Forgetting memory: a set or dict can be several times larger than a list of the same values.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Your program checks "is this id already seen?" for millions of ids. Which structure is the best default?

    A set answers membership in O(1) on average. A list needs a scan for every check.
  2. 2. Why is list.pop(0) a poor choice for the front of a large queue?

    A list stores items contiguously, so removing the first one means moving all others. A deque removes from the front in O(1).
  3. 3. Which pair of operations is a heap designed for?

    A binary heap keeps the minimum at the root and restores the invariant in O(log n) after a push or a pop. It does not support efficient search or sorted iteration.
  4. 4. You need to count how many sorted scores fall between two values, many times. What should you use?

    Two binary searches give the positions of the range ends in O(log n), and their difference is the count.
  5. 5. You are choosing between a sorted list and a balanced tree for a huge dataset with constant inserts. What is the main argument for the tree?

    A balanced tree keeps both search and update logarithmic, while a sorted array pays a linear shift for every insertion. For moderate sizes the list is simpler and often fast enough.

Summary

  • Choose a structure by the operations you need and how often you do each, not by habit.
  • set and dict answer membership and lookup in O(1) on average; a list is for positions and stacks; a deque is for queues; a heap for the repeated minimum; bisect for sorted data and range counts.
  • Counting steps (comparisons, moves) is a reliable way to compare options without timing noise.
  • Python has no built-in balanced tree, linked list, trie, graph or union-find; build those yourself or pull in a package.
  • Real systems are combinations: a stack for history, a queue for jobs, a heap for priorities, sets for relationships, a trie for prefixes.
  • For small inputs, simplicity beats cleverness: measure the size before building something custom.

Next: Practice Problems: Arrays, Strings and Hashing