List, Dict, Set, Tuple — When to Use Which

TL;DR

Four built-in containers cover most of the work. Pick wrong and your preprocessing loop goes from O(n) to O(n²); pick right and the code reads itself.

The single most common mistake: writing if x in some_list: inside a loop. That’s O(n) per check, O(n²) total. Convert the list to a set first and it’s O(1) per check, O(n) total.

The picture in your head

• list is a row of post boxes, each holding a reference. Indexed access is O(1) (it’s an array under the hood). Adding to the end is O(1) amortized. Adding to the front shifts everything, O(n).
• tuple is a list whose contents are fixed at creation. Same layout in memory, no resizing logic, slightly smaller footprint, and hashable if its contents are.
• dict is a hash table — the canonical key/value store. CPython 3.7+ guarantees insertion order, so you also get “ordered” for free.
• set is a dict without values — same hash table, just the keys.

The first three (list, tuple, dict) are the workhorses. set is the one engineers under-use; learning to reach for it cuts a lot of quadratic code.

Costs you should memorise

For containers of size n. Source: wiki.python.org/moin/TimeComplexity.

The two highlighted rows — x in list is O(n), x in dict/set is O(1) — are the ones you’ll quote most often.

If you need O(1) on both ends, use collections.deque (a doubly-linked list of fixed-size blocks). appendleft and popleft are O(1).

When each one wins

list — the default sequence

Reach for list when you have a sequence of items, you’ll iterate over them, you might append more later, and you don’t need fast membership tests.

# Building a batch of preprocessed examples
batch = []
for raw in raw_examples:
    batch.append(preprocess(raw))

Don’t reach for list when:

• You’ll do many x in batch checks. Use a set (or build a set from the list at the moment you need to check).
• You need O(1) push/pop on both ends. Use collections.deque.
• You’ll mostly index by some key. Use dict.

tuple — the fixed record

Tuples are immutable lists. The two real reasons to use them:

1. You want it to be a key. tuple is hashable; list is not. dict[(user_id, item_id)] = score works; dict[[user_id, item_id]] = score raises TypeError.
2. You want to communicate “this won’t change.” def get_shape(self) -> tuple[int, int]: says “always exactly two ints, never more, never fewer.” list[int] would mean “any length, mutable.”

The “multiple return values” idiom — return loss, accuracy — is implicitly a tuple. Unpacking it (loss, acc = train_step(...)) is one of the nicest things Python has.

For tuples with named fields and a few methods, prefer NamedTuple or a frozen dataclass — both give attribute access (shape.height, not shape[0]) without losing immutability.

dict — anything keyed

The workhorse. Vocabularies, frequency counts, configs, caches, ID-to-object maps, ID-to-embedding maps. If the question is “given X, what’s the Y?”, the answer is a dict.

# Token frequency over a corpus
from collections import Counter
freqs = Counter(tokens)              # dict subclass; gives O(1) lookup

# Build a vocabulary: token -> integer id
vocab = {tok: i for i, (tok, _) in enumerate(freqs.most_common())}

# Look up an ID — O(1)
id_for_the = vocab["the"]

Two dict-related patterns worth knowing cold:

# 1) Default values — three ways
counts = {}
for word in words:
    counts[word] = counts.get(word, 0) + 1   # explicit get

from collections import defaultdict
counts = defaultdict(int)
for word in words:
    counts[word] += 1                         # auto-init missing key to 0

from collections import Counter
counts = Counter(words)                       # one-liner; identical result

# 2) Merging dicts
merged = {**defaults, **overrides}            # Python 3.5+
merged = defaults | overrides                 # Python 3.9+; same result

The keys-must-be-hashable rule means dict keys are always immutable. String, int, tuple-of-immutables, frozenset. Never list, never dict, never plain set.

set — membership and uniqueness

If you find yourself writing if x in some_list: more than twice in a function, stop and ask: should this be a set?

# Bad — O(n²) total
seen = []
for x in stream:
    if x not in seen:
        seen.append(x)

# Good — O(n) total
seen = set()
for x in stream:
    if x not in seen:
        seen.add(x)

# Better, if you don't need to preserve order
unique = set(stream)

# Best, if you DO need to preserve insertion order — dict keys give it
unique = list(dict.fromkeys(stream))

Set operations are themselves the right tool a surprising amount:

train_ids = set(train_df["user_id"])
test_ids  = set(test_df["user_id"])

leaked    = train_ids & test_ids        # intersection — train/test contamination!
holdout   = test_ids - train_ids        # difference — clean test users
all_users = train_ids | test_ids        # union
disjoint  = train_ids ^ test_ids        # symmetric difference

That train_ids & test_ids line is how you catch user leakage in 30 seconds — the kind of audit a long Pandas merge would also do, but slower and harder to read.

A worked decision — counting tokens by length

Three implementations of the same task, all O(n), but with different container choices.

words = ["the", "quick", "brown", "fox", "the", "lazy", "dog"]

# v1 — list of (length, word) pairs (bad: hard to query later)
out = [(len(w), w) for w in words]

# v2 — dict from length to list of words
from collections import defaultdict
by_len = defaultdict(list)
for w in words:
    by_len[len(w)].append(w)
# {3: ['the', 'fox', 'the', 'dog'], 5: ['quick', 'brown'], 4: ['lazy']}

# v3 — dict from length to set of unique words
by_len_unique = defaultdict(set)
for w in words:
    by_len_unique[len(w)].add(w)
# {3: {'the', 'fox', 'dog'}, 5: {'quick', 'brown'}, 4: {'lazy'}}

The dict[int, set[str]] from v3 lets you ask “which 3-letter words have I seen?” in O(1) and answer “is ‘fox’ in the 3-letter bucket?” in O(1). The list-of-pairs from v1 forces O(n) scans for both questions.

The right shape often is dict[K, set[V]] or dict[K, list[V]] — not a flat list. Ask yourself “what queries do I want?” and let the container fall out of the answer.

collections — the ones worth knowing

The collections module ships specialized containers that solve common patterns in one line.

Counter is the one I reach for weekly:

from collections import Counter

# Most-common labels in a dataset
labels = Counter(df["label"])
top5 = labels.most_common(5)

# Vocabulary intersection
vocab_a = Counter(tokens_a)
vocab_b = Counter(tokens_b)
shared  = vocab_a & vocab_b   # multiset intersection — min count per key

Common gotchas

• x = []; y = x doesn’t copy. See PY 101. y = x.copy() for a shallow copy.
• {1, 2, 3} is a set; {} is an empty dict. Use set() for empty set.
• Iterating a dict yields keys. Use .items() for (k, v) pairs. for k, v in d.items():.
• Modifying a dict / set while iterating raises RuntimeError. Iterate over list(d) if you need to mutate.
• tuple of one element needs the trailing comma. (1) is the int 1. (1,) is the one-element tuple.
• Sorting a dict doesn’t exist — dicts preserve insertion order, so build a new dict from sorted items: dict(sorted(d.items(), key=lambda kv: kv[1])).

Where this shows up in ML

• Vocabularies. dict[str, int] from token to ID; list[str] for the inverse. Building both at once from Counter.most_common().
• Feature stores. dict[entity_id, dict[feature_name, value]] is the common in-memory shape; reach for pd.DataFrame once it’s bigger than memory or you need joins.
• Train/test leakage audits. set(train_ids) & set(test_ids) — zero rows or you have a problem.
• Dataloader caches. dict[idx, Tensor] keyed by example index, or lru_cache on the loader function.
• Class weights. dict[label, float] — passed straight to nn.CrossEntropyLoss(weight=...) after you build a tensor from the values in the right order.
• Tokenizer normalisation. dict[str, str] for character mappings; set[str] for stopwords.

The defensive habit: when you’re about to write if x in something inside a loop, stop and check the type of something. If it’s a list, it’s almost certainly the wrong container.

Resources

• Python docs — Built-in Types — docs.python.org — the canonical reference for list, dict, set, tuple.
• Python docs — collections module — docs.python.org — Counter, defaultdict, deque, OrderedDict, ChainMap.
• CPython TimeComplexity wiki — wiki.python.org — the source of every cost in the table above.
• Fluent Python (2nd ed.) — Chapters 2, 3, 4 — oreilly.com — sequences, dicts, sets, in depth.