Choosing the Right Data Structure

Every data structure is a trade-off. A Python list gives you fast indexed access but slow insertion at the front; a dict gives you near-instant lookup by key but no built-in sense of numeric order; a deque gives you fast operations at both ends but slow access to the middle. Choosing the right data structure isn’t about memorizing which one is “best” — it’s about matching the operation your algorithm performs most often to the structure that makes that operation cheap. Get this right and an O(n2) solution becomes O(n); get it wrong and a perfectly correct algorithm crawls once the input gets large.

Overview: How to Choose

Before writing a line of code, ask three questions about the problem: What operation happens most often? Does order matter? and Do I need to find things by value, or by position? The answers point almost directly at a structure.

Picture a “recently viewed products” feature that keeps the last few items a shopper looked at, with a new item added on every view and the oldest one dropped once the list is full. A first instinct is a plain list: append new items, then trim the front with recent.pop(0) once it grows too large. That works, but pop(0) is O(n) — every remaining element has to shift left by one slot to fill the gap, because a Python list is backed by one contiguous block of memory. If this runs on every page view for millions of users, that O(n) shift adds up fast. Swap the list for collections.deque and both ends become O(1), because a deque is implemented as a doubly linked block structure built for exactly this access pattern. Nothing about the underlying problem changed — only the structure whose strengths line up with the operation actually being performed.

Now picture a different problem: given a huge collection of numbers, repeatedly answer “have I seen this number before?” A list forces you to scan every element to answer that, since there’s no shortcut — O(n) per check. A set answers the same question in O(1) average time, because it hashes the value and jumps almost directly to the bucket where it would live. The moment a problem is dominated by “does X exist” or “what value is associated with key X,” a hash-based structure (set or dict) should be your default, not an afterthought.

A third pattern shows up constantly in interviews: “give me the smallest or largest item efficiently, repeatedly, as the collection keeps changing.” Re-sorting the whole collection every time something changes wastes work you already did. A heapq-based priority queue keeps the smallest element accessible in O(1) and lets you insert or remove items in O(log n), without ever fully sorting the collection.

Later lessons in this course cover trees, graphs, and tries in depth. This lesson is about the everyday building blocks — list, dict, set, tuple, deque, and heapq — and the decision process for picking among them, because that decision comes up in nearly every problem you will ever solve.

Time and Space Complexity

The table below summarizes the operations that matter most, measured in terms of n, the number of elements currently stored.

Structure Index/Key Access Search (“is X in it?”) Insert Delete Space
list O(1) by index O(n) O(1) amortized at end, O(n) at front/middle O(n), shifts elements O(n)
dict / set O(1) average by key O(1) average O(1) average O(1) average O(n)
tuple O(1) by index O(n) not mutable not mutable O(n)
deque O(n) by index O(n) O(1) at either end O(1) at either end O(n)
heapq (list-backed heap) O(1) to peek smallest O(n) O(log n) O(log n) to pop smallest O(n)

The O(1) average for dict/set comes from hashing: Python computes hash(key) and uses it to jump almost directly to a slot in an underlying array, finding the value in constant time regardless of how many items are stored, as long as collisions stay rare. The worst case degrades to O(n) if many keys collide into the same bucket, but Python’s hash design makes that vanishingly unlikely for well-behaved keys, so “O(1) average” is the number to reason with in practice. A list‘s O(n) search exists because there is no shortcut — the interpreter walks from the start, comparing each element, until it finds a match or reaches the end.

Examples

Each example below solves a small, realistic problem and explains why its structure was chosen over the obvious alternative.

Example 1: Two Sum with a dict instead of nested loops

The naive approach checks every pair of numbers for a target sum, which is O(n2). Storing each number’s index in a dict as you scan turns it into a single O(n) pass: for each value, check whether its complement was already seen.

def two_sum(nums: list[int], target: int) -> list[int]:
    seen = {}
    for index, value in enumerate(nums):
        complement = target - value
        if complement in seen:
            return [seen[complement], index]
        seen[value] = index
    return []

nums = [2, 7, 11, 15]
target = 9
result = two_sum(nums, target)
print(result)
print(f"Indices {result} sum to {target}: {nums[result[0]]} + {nums[result[1]]} = {target}")

Output:

[0, 1]
Indices [0, 1] sum to 9: 2 + 7 = 9

At index = 0, value = 2, the complement 7 is not yet in seen, so seen becomes {2: 0}. At index = 1, value = 7, the complement is 2, which is in seen mapped to index 0, so the function returns [0, 1] immediately. The dict turned a repeated “have I seen the complement?” question into an O(1) average lookup instead of an inner loop.

Example 2: First unique character with Counter

Finding the first non-repeating character requires knowing, for every character, how many times it appears in total. A Counter (a dict subclass) builds that frequency map in one O(n) pass, then a second O(n) pass finds the answer.

from collections import Counter

def first_unique_char(text: str) -> str:
    counts = Counter(text)
    for char in text:
        if counts[char] == 1:
            return char
    return ""

word = "swiss"
result = first_unique_char(word)
print(f"First unique character in '{word}': '{result}'")

Output:

First unique character in 'swiss': 'w'

Counter("swiss") produces {'s': 3, 'w': 1, 'i': 1}. Scanning the original string in order, 's' has count 3 so it’s skipped, and 'w' has count 1, so it’s returned. Without a hash map, computing each character’s total count would mean rescanning the whole string for every character — O(n2) instead of O(n).

Example 3: A fixed-size recent-items tracker with deque

This mirrors the “recently viewed products” scenario from the overview. deque(maxlen=...) automatically discards the oldest item once it’s full, and every append is O(1) regardless of size.

from collections import deque

def track_recent_searches(searches: list[str], max_size: int) -> list[str]:
    recent: deque[str] = deque(maxlen=max_size)
    for search in searches:
        recent.append(search)
    return list(recent)

searches = ["python", "java", "sql", "rust", "go"]
result = track_recent_searches(searches, 3)
print(result)

Output:

['sql', 'rust', 'go']

As each of the five searches is appended, the deque keeps only the most recent three: once "rust" is appended, "python" is silently dropped from the left end; once "go" is appended, "java" is dropped. The final contents are ['sql', 'rust', 'go']. A list with manual trimming could do the same thing, but every trim would be an O(n) shift; the deque does it in O(1).

How It Works Step by Step

Tracing two_sum([2, 7, 11, 15], 9) from Example 1 shows exactly why the dict-based approach avoids a nested loop:

Step index, value complement = target – value seen before this step Action
1 0, 2 9 – 2 = 7 {} 7 not in seen, so store seen[2] = 0
2 1, 7 9 – 7 = 2 {2: 0} 2 is in seen, return [seen[2], 1] = [0, 1]

The loop stops after just two iterations, having never compared nums[0] against nums[2] or nums[3] at all — the dict lookup replaced what would otherwise be an inner scan through the rest of the list.

Common Mistakes

Mistake 1: Using a list for repeated membership checks

Checking value in some_list inside a loop looks harmless, but each check is O(n), so doing it n times makes the whole function O(n2).

def has_duplicate_slow(nums: list[int]) -> bool:
    seen = []
    for num in nums:
        if num in seen:  # O(n) scan on every single call
            return True
        seen.append(num)
    return False

print(has_duplicate_slow([1, 2, 3, 2]))

Output:

True

This returns the correct answer, but on a list of 100,000 numbers with no duplicates it performs on the order of 5 billion comparisons. Swapping seen from a list to a set fixes the complexity without changing the logic at all:

def has_duplicate_fast(nums: list[int]) -> bool:
    seen = set()
    for num in nums:
        if num in seen:  # O(1) average set lookup
            return True
        seen.add(num)
    return False

print(has_duplicate_fast([1, 2, 3, 2]))

Output:

True

Mistake 2: Using list.pop(0) to implement a queue

A queue needs to remove items from the front in O(1). list.pop(0) looks like it does that, but it’s actually O(n), because every remaining element must shift left one position to close the gap.

queue = [1, 2, 3, 4, 5]
first = queue.pop(0)  # O(n): shifts every remaining element left
print(first, queue)

Output:

1 [2, 3, 4, 5]

The output looks fine for a small list, which is exactly why this mistake survives code review — it only becomes a performance problem at scale. collections.deque is designed for this: popleft() is O(1) because a deque doesn’t need to shift anything to remove from either end.

from collections import deque

queue = deque([1, 2, 3, 4, 5])
first = queue.popleft()  # O(1): no shifting required
print(first, list(queue))

Output:

1 [2, 3, 4, 5]

Best Practices

  • Identify the single most frequent operation in your algorithm’s hot loop before picking a structure — the complexity of rare operations matters far less than the complexity of the one that runs n times.
  • Reach for set the moment you find yourself asking “have I seen this?” or “is this a duplicate?” repeatedly inside a loop.
  • Reach for dict when you need to associate extra data with a key (counts, first-seen index, cached results) — it’s the backbone of countless DSA patterns.
  • Reach for deque for any queue, stack-with-both-ends, or sliding-window pattern instead of a plain list.
  • Reach for heapq when you repeatedly need the current minimum or maximum from a changing collection, instead of re-sorting from scratch each time.
  • Don’t default to a list just because it’s the most familiar structure — look at what the algorithm actually does with the data before choosing.
  • Remember that tuples are hashable when their contents are, but lists never are — use a tuple as a dict key or set member when you need a compound key.

Practice Exercises

  • You’re given a huge stream of user IDs and need to answer “has this ID appeared before?” as fast as possible, without caring about order. Which structure would you reach for, and what’s the average-case time complexity of a single lookup?
  • Implement is_valid_parentheses(expression: str) -> bool, which returns True if a string like "()[]{}" has every bracket correctly matched and nested. Which structure naturally models “the most recently opened bracket must be the next one closed”? Expected output for "([{}])" is True, and for "([)]" is False.
  • A leaderboard changes constantly, and you must repeatedly report the 3 highest scores. Would you re-sort a list after every update, or maintain a heap? Justify your answer in terms of the complexity of a single update.

Summary

  • Match the structure to the dominant operation: index access favors list, membership or key/value lookup favors dict/set, both-ends access favors deque, and repeated min/max queries under change favor heapq.
  • dict and set give O(1) average lookup, insert, and delete via hashing; list gives O(n) search and O(n) front insert/delete because it must shift elements.
  • deque is the right choice whenever a problem needs O(1) appends and pops at both ends (queues, sliding windows, undo history) — a list’s pop(0) is O(n) and silently kills performance at scale.
  • heapq keeps repeated “give me the min/max” queries at O(log n) per update instead of re-sorting the whole collection.
  • dict and set preserve insertion order in modern Python (3.7+), but that is not the same as being sorted — don’t rely on it as a substitute for real ordering logic.
  • When unsure, state explicitly which operation your algorithm performs most often, then pick the structure that makes that specific operation cheapest.