Choosing the Right Data Structure

Bringing it all together#

Every page so far introduced one data structure in isolation. But the actual skill you're building toward isn't "can you implement a linked list from memory" — it's recognizing which structure a real problem calls for, quickly, before you've written a single line of code. This page is a practical decision guide for exactly that, plus a few worked scenarios to practice the reasoning.

The decision table#

Notice the pattern in the "why" column: almost every choice comes down to which operation you'll perform most often, and picking the structure that makes that specific operation cheap — usually at some acknowledged cost elsewhere (a hash table doesn't preserve order; a heap doesn't let you peek at the second-smallest cheaply; a trie can cost more memory than a flat set for dissimilar strings). There is no single "best" data structure — there's only "best for what you're about to do most."

Worked scenario 1: build a leaderboard#

The problem: a game needs to display the top 10 highest-scoring players at any moment, out of potentially millions of players whose scores are constantly changing.

The wrong instinct: keep every player's score in a list and re-sort the whole thing every time the leaderboard is displayed. With millions of players, a full sort is O(n log n) — repeated on every request, that's an enormous amount of wasted work, since you only ever care about the top 10, not a total ordering of everyone.

The right structure: a min-heap of size 10. This is exactly the "k largest elements" pattern from the heaps page. Keep a min-heap holding only the current top 10 scores. When a new score comes in: if the heap has fewer than 10 entries, add it. Otherwise, compare it to the heap's smallest member (the root) — if the new score is higher, it displaces the current 10th place.

import heapq

class Leaderboard:
    def __init__(self, size=10):
        self.size = size
        self.heap = []   # min-heap of (score, player_name) — smallest of the "top N" sits at the root

    def submit_score(self, player, score):
        if len(self.heap) < self.size:
            heapq.heappush(self.heap, (score, player))
        elif score > self.heap[0][0]:
            heapq.heapreplace(self.heap, (score, player))

    def top_players(self):
        return sorted(self.heap, reverse=True)


board = Leaderboard(size=3)
for player, score in [("Ava", 50), ("Sam", 80), ("Kim", 65), ("Zoe", 90), ("Lee", 40)]:
    board.submit_score(player, score)

print(board.top_players())
# [(90, 'Zoe'), (80, 'Sam'), (65, 'Kim')]  — Ava and Lee never made the cut

Why this is the right call: updating the leaderboard is O(log 10) — effectively constant — regardless of how many total players there are, because the heap never grows past size 10. A full sort would be redone from scratch, over all players, every single time.

Worked scenario 2: detect duplicate entries in a stream#

The problem: data is arriving continuously (log lines, sensor readings, incoming request IDs), and you need to instantly flag whenever something arrives that you've already seen before.

The wrong instinct: keep every seen item in a list and check if item in seen_list for each new arrival. That check is O(n), and it gets slower the longer the stream runs, since the list keeps growing — a classic case of an operation that looks fine in a quick test but degrades badly at real scale.

The right structure: a hash set. Membership testing (in) on a Python set is O(1) on average, regardless of how many items it already holds — exactly the property this problem needs.

def detect_duplicates(stream):
    seen = set()
    duplicates = []

    for item in stream:
        if item in seen:              # O(1) average — instant, no matter how large 'seen' gets
            duplicates.append(item)
        else:
            seen.add(item)

    return duplicates


incoming = ["req-1", "req-2", "req-3", "req-2", "req-4", "req-1"]
print(detect_duplicates(incoming))   # ['req-2', 'req-1']

Why this is the right call: the entire operation is O(n) total (one O(1) check per arriving item), versus O(n²) if a list had been used instead — the difference between a stream processor that keeps up in real time and one that falls further and further behind as it runs.

Worked scenario 3: undo/redo in a text editor#

The problem: a text editor needs to support "undo" (revert the most recent action) and "redo" (reapply an undone action), with actions arriving continuously as the user types.

The right structure: two stacks. Every action gets pushed onto an "undo stack." Pressing undo pops the most recent action off that stack, reverses it, and pushes it onto a second "redo stack" (in case the user changes their mind). Pressing redo does the reverse.

class TextEditor:
    def __init__(self):
        self.undo_stack = []
        self.redo_stack = []

    def do_action(self, action):
        self.undo_stack.append(action)
        self.redo_stack.clear()          # a fresh action invalidates any old "redo" history

    def undo(self):
        if not self.undo_stack:
            return None
        action = self.undo_stack.pop()
        self.redo_stack.append(action)
        return action

    def redo(self):
        if not self.redo_stack:
            return None
        action = self.redo_stack.pop()
        self.undo_stack.append(action)
        return action


editor = TextEditor()
editor.do_action("type: Hello")
editor.do_action("type: World")
print(editor.undo())   # "type: World" — the most recent action, reversed first (LIFO)
print(editor.undo())   # "type: Hello"
print(editor.redo())   # "type: Hello" — reapplied

Why this is the right call: undo/redo is inherently a LIFO problem — "reverse the most recent thing first" is the literal definition of a stack, which is precisely why virtually every real editor implements undo this exact way.

The general reasoning process#

When you're facing a new problem, ask, in order:

1. What operation will I perform most often — lookup, insertion, deletion, "give me the min/max," "give me things in order," "give me things matching a prefix," or "give me the relationships between these things"?
2. Does the answer need to preserve insertion order, sorted order, or no particular order at all? This alone rules out several structures immediately (a hash set has no order; a heap only orders the extreme element cheaply; a BST maintains full sorted order).
3. What's the actual scale? A O(n²) approach might be completely fine for 50 items and completely unusable for 5 million — always ask how large n realistically gets.
4. What am I willing to trade? Every structure buys a fast operation at the cost of something else — extra memory (hash tables, tries), weaker ordering guarantees (heaps), or slower access elsewhere (linked lists trading index access for cheap front-insertion). There is no free lunch, only an explicit, informed trade.

Common mistakes#

• Defaulting to whatever structure you're most comfortable with, rather than the one the problem's dominant operation actually calls for — this course exists specifically to widen that default toolbox.
• Optimizing an operation that barely happens, while ignoring the one that happens constantly. Always identify the hot path — the operation performed most frequently — and design around that first.
• Ignoring realistic scale. A structure choice that's irrelevant at n = 100 can be the entire difference between a responsive system and a frozen one at n = 10,000,000.
• Forgetting that combinations are normal. Real systems often use several structures together (a hash map for lookup plus a heap for priority plus a list for insertion order) — don't feel obligated to solve every requirement with exactly one structure.