AnacodicAnacodicAI Labs
← Back to Learning Hub

Python Data Structures

PythonAlgorithmsBeginner24 min

By: Anacodic Team

TL;DR — Choosing between a list, a set, and a dict is not a style preference; it changes the asymptotic complexity of your program. x in list scans every element (O(n)); x in set hashes straight to the answer (O(1)). In the runnable example below that is an 833× difference at 20,000 items, and the gap widens with n — which is why an x in list sitting inside a loop is the single most common way to accidentally write an O(n²) algorithm that passes every test on small data and stalls in production. Four more decisions follow the same pattern: Counter over hand-rolled counting dicts, deque over list.pop(0) when the window is large (24× at 5,000 elements, and nothing at 3 — the cost is O(k), so the window size is what matters), dict.fromkeys when dedupe must preserve order, and tuples over lists whenever the value has to be a dict key, because lists are unhashable. Each is one line of code and the right answer is not negotiable once you know the complexity.

1. Simple explanation

Every container answers a different question efficiently, and the question you ask most often should decide which one you pick.

A list is an ordered row of slots. Getting item 5 is instant, because the position is arithmetic. But asking "is this value in here?" means walking the row and comparing every element, because nothing about the value tells you where it would be.

A set and a dict work differently. They run the value through a hash function — a computation that turns any value into a number — and use that number as the address. To check membership, hash the value and look at that one address. It does not matter whether there are ten items or ten million; you do the same amount of work. That is what O(1) means.

The cost is that hashing throws away order and requires the values to be hashable, which in practice means immutable. That is the whole trade: a list keeps order and accepts anything, a set gives up both to answer one question instantly.

Analogy — a pile of books versus a library catalogue. To find out whether a pile contains a particular book you check the spines one at a time; a hundred books means up to a hundred checks. A library catalogue tells you the shelf from the title alone — one lookup, and it takes the same time in a small library as a national one. The catalogue costs you something: the books must sit in an assigned order, not the order you happened to acquire them. If you need "the third book I bought," the pile wins. If you need "do we have this?", the catalogue wins by a margin that grows with the collection.

The rest of this article is the same reasoning applied to four more choices, each of which has a clearly correct answer that beginners routinely get wrong.

2. Diagram

MEMBERSHIP: the operation that decides everything

  LIST  `"doc-19999" in as_list`
    ┌────┬────┬────┬────┬─────────────────────────┬────┐
    │ 0  │ 1  │ 2  │ 3  │  ... 19,995 more ...    │19999│
    └────┴────┴────┴────┴─────────────────────────┴────┘
      ↑    ↑    ↑    ↑    compare, compare, compare...   ↑ found
      └──────────── O(n): touches every element ─────────┘

  SET   `"doc-19999" in as_set`
       hash("doc-19999") ──► 0x3f2a  ──►  bucket 0x3f2a: present?
       └────────────── O(1): ONE computation, ONE probe ────────┘

       20,000 items → 51.61 ms  vs  0.06 ms     (833x)
      200,000 items → the list gets 10x worse; the set does not move


THE ACCIDENTAL O(n²) -- why this matters more than it looks

  seen = []                        seen = set()
  for doc in docs:        n        for doc in docs:        n
      if doc.id in seen:  × O(n)       if doc.id in seen:  × O(1)
          continue                         continue
      seen.append(doc.id)              seen.add(doc.id)
  └──── O(n²) ────┘                 └──── O(n) ────┘
   10k docs ≈ 100,000,000 ops        10k docs ≈ 10,000 ops


PICKING A CONTAINER -- ask what you do MOST

   need                              use          why
   ──────────────────────────────────────────────────────────────
   ordered, index access, duplicates list         O(1) by position
   "is it in here?", uniqueness      set          O(1) hashed
   key → value lookup                dict         O(1) hashed
   count occurrences                 Counter      + most_common()
   default value per missing key     defaultdict  no `if k not in`
   append/pop at BOTH ends           deque        O(1) either end
   immutable, usable as a dict key   tuple        hashable


LIST vs DEQUE -- the cost is O(k) in the WINDOW, not the stream

   list.pop(0)  ┌──┬──┬──┬──┬──┐   remove front, then SHIFT
                └──┴──┴──┴──┴──┘   every remaining element left
                 ✗  ←──←──←──←      k moves, every iteration

   deque        ┌──┬──┬──┬──┬──┐   both ends are O(1);
                └──┴──┴──┴──┴──┘   maxlen evicts automatically

   window k=3   →  2.7x     ← too small to matter
   window k=500 →  4.8x
   window k=5000→ 24.0x     ← now it dominates

3. How it works

Hashing, and why it buys O(1)

A hash function maps a value to a fixed-size integer. Python's hash() is available directly: hash("doc-1") returns a large int. A set stores its elements in an array of buckets and uses hash(x) % n_buckets as the index. Membership is: compute the hash, go to that bucket, compare the few items there.

Two different values can hash to the same bucket — a collision — so the bucket holds a small number of entries that must be compared with ==. Python keeps the table sparse (resizing when it passes roughly two-thirds full) so collisions stay rare and the average bucket holds about one item. That is why the O(1) is an average case; the pathological worst case is O(n) if every element collides, which does not happen with well-behaved hash functions on ordinary data.

The requirement this imposes: a hashable object's hash must never change while it is in the set, otherwise it would be sitting in the wrong bucket and become unfindable. Python enforces this by making mutable built-ins unhashable. hash([1,2]) raises TypeError: unhashable type: 'list', which is why the last section of the code example matters — your cache key must be a tuple.

Note that hashing is not free in absolute terms. Hashing a long string costs time proportional to its length. For a handful of items, a list scan can genuinely be faster than building a set, because building the set means hashing everything once. The crossover is low — around a few dozen items for the membership pattern — and the asymptotic argument takes over immediately after.

dict, and insertion order

Since Python 3.7, dict preserving insertion order is a language guarantee, not a CPython implementation detail (it was the latter in 3.6). This is what makes dict.fromkeys(items) the idiomatic order-preserving dedupe: it builds a dict whose keys are the unique items in first-seen order, and you take list(...) of it. set(items) loses that order, and the order you get back is a function of hash values, not of anything meaningful. It will also look stable across runs for integers and change for strings between processes, because string hashing is randomised by default (PYTHONHASHSEED) as a defence against hash-collision denial of service.

Counter and defaultdict

collections.Counter is a dict subclass for counting. It replaces the three-line "check if key exists, initialise, increment" idiom with Counter(tokens), and adds most_common(n) — which is a partial sort, more efficient than sorting the whole thing when n is small. It also supports arithmetic: c1 - c2, c1 & c2, which is occasionally exactly what you want for comparing two distributions.

collections.defaultdict(factory) calls factory() for any missing key on access. defaultdict(list) is the standard grouping idiom. Its one trap: reading a missing key inserts it. dd["nope"] returns [] and now "nope" is a key, so len(dd) changed because you looked at it. Use dd.get(k) when you only want to read.

deque

A list is a contiguous array. append is amortised O(1) — occasionally it reallocates and copies, but averaged out it is constant. pop(0) is O(k) in the list's length, because every remaining element must shift down one slot.

collections.deque is a doubly-linked list of fixed-size blocks. Both ends are O(1). The maxlen parameter makes it a ring buffer that evicts from the far end automatically — the natural fit for a sliding window, a rolling log, or the last N turns of a conversation.

The important qualifier, which most tutorials skip: the cost of pop(0) scales with the window size, not the stream length. With a 3-element window, shifting 3 items is free, and deque wins nothing. That is exactly what the measurement in §5 shows, and it is the honest version of the usual "always use deque" advice. The corollary is that deque gives up O(1) random access — indexing the middle is O(n) — so it is the wrong choice if you need both ends and arbitrary indexing.

Tuples

Tuples are immutable, therefore hashable (as long as their contents are), therefore usable as dict keys and set members. This is the mechanism behind every composite cache key: cache[(tenant_id, query)]. A tuple is also slightly smaller and slightly faster to construct than a list, though that is rarely the reason to choose one.

The word "immutable" is doing careful work: a tuple's bindings cannot change, but if it holds a list, that list can still be mutated — and then hash(t) raises, because the tuple's hash depends on its contents. hash((1, [2])) is a TypeError.

4. The math

The whole article reduces to comparing growth rates, so it is worth being precise about what the notation claims.

For a list of length $n$, a membership test compares elements until it finds a match. For a value present at a uniformly random position, the expected number of comparisons is:

$$ E[\text{comparisons}] = \frac{1}{n}\sum_{i=1}^{n} i = \frac{n+1}{2} $$

and for a value that is absent it is exactly $n$ — every element must be checked before you can conclude it is not there. Absent lookups are the worst case and they are also common (that is what a cache miss is), which is why the example includes 200 deliberately-missing probes.

For a hash set with load factor $\alpha = n / \text{buckets}$ and open addressing, the expected number of probes for an unsuccessful search is approximately:

$$ E[\text{probes}] \approx \frac{1}{1 - \alpha} $$

Python resizes to keep $\alpha \lesssim 2/3$, giving $1/(1 - 2/3) = 3$ probes in the worst tolerated case, and closer to 1–2 typically. Crucially, $n$ does not appear in that expression. Growing the set triggers a resize that restores $\alpha$; the lookup cost does not grow.

Putting the two together for the nested-loop pattern:

$$ T_{\text{list}}(n) = \sum_{i=1}^{n} \Theta(i) = \Theta(n^2), \qquad T_{\text{set}}(n) = \sum_{i=1}^{n} \Theta(1) = \Theta(n) $$

The ratio is $\Theta(n)$, which is the precise statement behind "the gap grows." At $n = 10{,}000$ the list version does about $5 \times 10^7$ comparisons; at $n = 100{,}000$, about $5 \times 10^9$. Ten times the data, a hundred times the work. This is the shape of every "it was fine last month" performance report.

For the deque comparison, the list version performs one pop(0) per stream element, each shifting $k$ items:

$$ T_{\text{list}}(n, k) = \Theta(nk), \qquad T_{\text{deque}}(n, k) = \Theta(n) $$

The ratio is $\Theta(k)$ — linear in the window, independent of the stream. That predicts the measured 2.7× / 4.8× / 24.0× at $k = 3 / 500 / 5000$: roughly proportional once $k$ is large enough that the shift dominates the per-iteration overhead, and invisible below that. The measured numbers are sublinear in $k$ at the low end precisely because fixed per-iteration costs dominate there.

5. Real code

"""Choosing the container: the difference is asymptotic, not stylistic."""
import time
from collections import Counter, defaultdict, deque

N = 20_000
ids = [f"doc-{i}" for i in range(N)]
as_list, as_set, as_dict = ids, set(ids), {k: i for i, k in enumerate(ids)}
probes = [f"doc-{i}" for i in range(0, N, N // 200)] + ["missing"] * 200


def timed(fn):
    t0 = time.perf_counter()
    fn()
    return (time.perf_counter() - t0) * 1000


print(f"MEMBERSHIP TESTS over {N:,} items, {len(probes)} lookups")
lt = timed(lambda: [p in as_list for p in probes])
st = timed(lambda: [p in as_set for p in probes])
dt = timed(lambda: [p in as_dict for p in probes])
print(f"  {'list  `x in list`':<22} {lt:>8.2f} ms   O(n) -- scans every element")
print(f"  {'set   `x in set`':<22} {st:>8.2f} ms   O(1) -- hashes straight to it")
print(f"  {'dict  `k in dict`':<22} {dt:>8.2f} ms   O(1)")
print(f"  -> set is ~{lt/max(st,1e-9):.0f}x faster here, and the gap GROWS with n.")
print("     A `x in list` inside a loop is the most common accidental O(n^2).")

print("\nCOUNTING -- three ways, and only one is idiomatic")
tokens = "the cat sat on the mat the cat sat".split()

manual = {}
for t in tokens:
    if t not in manual:
        manual[t] = 0
    manual[t] += 1

dd = defaultdict(int)
for t in tokens:
    dd[t] += 1

cnt = Counter(tokens)
print(f"  manual dict     {dict(sorted(manual.items()))}")
print(f"  defaultdict     {dict(sorted(dd.items()))}")
print(f"  Counter         {dict(sorted(cnt.items()))}")
print(f"  Counter also gives you: most_common(2) = {cnt.most_common(2)}")
assert manual == dd == dict(cnt)

print("\nSLIDING WINDOW -- list.pop(0) is O(k); deque handles eviction in O(1)")
K = 3


def with_list(items, k=K, collect=True):
    win, out = [], []
    for x in items:
        win.append(x)
        if len(win) > k:
            win.pop(0)                       # O(k): shifts every element left
        if collect:
            out.append(tuple(win))
    return out


def with_deque(items, k=K, collect=True):
    win, out = deque(maxlen=k), []           # maxlen evicts for you, O(1)
    for x in items:
        win.append(x)
        if collect:
            out.append(tuple(win))
    return out


seq = list(range(8))
print(f"  last 3 windows, list : {with_list(seq)[-3:]}")
print(f"  last 3 windows, deque: {with_deque(seq)[-3:]}")
assert with_list(seq) == with_deque(seq)
print("  With a 3-element window the two are indistinguishable -- shifting 3")
print("  items is free. The cost of pop(0) is O(k), so it only shows up when")
print("  the WINDOW is large:")
big = list(range(40_000))
print(f"  {'window':>8} {'list pop(0)':>14} {'deque':>10}")
for k in (3, 500, 5000):
    lms = timed(lambda: with_list(big, k, collect=False))
    dms = timed(lambda: with_deque(big, k, collect=False))
    print(f"  {k:>8} {lms:>11.0f} ms {dms:>7.0f} ms   {lms/max(dms,1e-9):>5.1f}x")

print("\nDEDUPE WHILE KEEPING ORDER -- dict remembers insertion order (3.7+)")
dupes = ["b", "a", "b", "c", "a", "d"]
print(f"  input                {dupes}")
print(f"  set(...)             {sorted(set(dupes))}  <- order LOST")
print(f"  dict.fromkeys(...)   {list(dict.fromkeys(dupes))}  <- order kept")

print("\nTUPLES ARE HASHABLE, LISTS ARE NOT -- which decides your cache key")
cache = {}
cache[("acme-corp", "refund policy")] = "30 days, unopened"   # fine
try:
    cache[["acme-corp", "refund policy"]] = "x"
except TypeError as e:
    print(f"  list as dict key -> TypeError: {e}")
print(f"  tuple as dict key -> works: {cache[('acme-corp', 'refund policy')]!r}")

assert st < lt                                   # set beats list on membership
assert cnt.most_common(1)[0] == ("the", 3)
assert list(dict.fromkeys(dupes)) == ["b", "a", "c", "d"]
assert set(dupes) == {"a", "b", "c", "d"}
assert with_deque(seq)[-1] == (5, 6, 7)
# pop(0) is O(k), so the penalty appears only once the window is large.
assert timed(lambda: with_list(big, 5000, collect=False)) > \
       timed(lambda: with_deque(big, 5000, collect=False))
print("\nall assertions passed")

Output (absolute timings vary with hardware; the ratios are the point):

MEMBERSHIP TESTS over 20,000 items, 400 lookups
  list  `x in list`         51.61 ms   O(n) -- scans every element
  set   `x in set`           0.06 ms   O(1) -- hashes straight to it
  dict  `k in dict`          0.08 ms   O(1)
  -> set is ~833x faster here, and the gap GROWS with n.
     A `x in list` inside a loop is the most common accidental O(n^2).

COUNTING -- three ways, and only one is idiomatic
  manual dict     {'cat': 2, 'mat': 1, 'on': 1, 'sat': 2, 'the': 3}
  defaultdict     {'cat': 2, 'mat': 1, 'on': 1, 'sat': 2, 'the': 3}
  Counter         {'cat': 2, 'mat': 1, 'on': 1, 'sat': 2, 'the': 3}
  Counter also gives you: most_common(2) = [('the', 3), ('cat', 2)]

SLIDING WINDOW -- list.pop(0) is O(k); deque handles eviction in O(1)
  last 3 windows, list : [(3, 4, 5), (4, 5, 6), (5, 6, 7)]
  last 3 windows, deque: [(3, 4, 5), (4, 5, 6), (5, 6, 7)]
  With a 3-element window the two are indistinguishable -- shifting 3
  items is free. The cost of pop(0) is O(k), so it only shows up when
  the WINDOW is large:
    window    list pop(0)      deque
         3           3 ms       1 ms     2.7x
       500           5 ms       1 ms     4.8x
      5000          25 ms       1 ms    24.0x

DEDUPE WHILE KEEPING ORDER -- dict remembers insertion order (3.7+)
  input                ['b', 'a', 'b', 'c', 'a', 'd']
  set(...)             ['a', 'b', 'c', 'd']  <- order LOST
  dict.fromkeys(...)   ['b', 'a', 'c', 'd']  <- order kept

TUPLES ARE HASHABLE, LISTS ARE NOT -- which decides your cache key
  list as dict key -> TypeError: unhashable type: 'list'
  tuple as dict key -> works: '30 days, unopened'

all assertions passed

Two observations that the numbers force.

The 833× is not the interesting part — the trend is. 833× at 20,000 items would be 8,330× at 200,000, because the set does not get slower. Any single measurement understates the problem; what you are choosing is the slope.

The deque result contradicts the usual advice, and that is deliberate. At k=3 the two are 2.7× apart and both take milliseconds — nobody should refactor for that. The advice "always use deque instead of pop(0)" is repeated everywhere without the qualifier that makes it true. The cost is O(k). If your window is small, list.pop(0) is fine, and if your window is 5,000, it is 24× and climbing. Knowing which variable drives the cost is the difference between applying a rule and understanding one.

6. Real-world example

A document-deduplication step in an ingestion pipeline, written the way it usually is first:

def dedupe(docs):
    seen = []
    out = []
    for doc in docs:
        if doc.id not in seen:        # O(n) inside an O(n) loop
            seen.append(doc.id)
            out.append(doc)
    return out

With 500 documents in the test fixture this runs in about 3 ms and looks fine. In production the corpus is 80,000 documents, and this single function takes roughly ninety seconds — because it performs about $3.2 \times 10^9$ string comparisons. The symptom reported is "ingestion is slow"; the profiler points at dedupe; the diff that fixes it is two characters plus a method name:

def dedupe(docs):
    seen = set()
    out = []
    for doc in docs:
        if doc.id not in seen:        # O(1)
            seen.add(doc.id)
            out.append(doc)
    return out

Same output, same order preserved, now linear. On the same 80,000 documents it finishes in well under a second.

If you do not need the document objects themselves and only want unique ids in order, the whole function collapses to one line:

unique_ids = list(dict.fromkeys(doc.id for doc in docs))

This pattern shows up throughout retrieval systems. Merging results from two retrievers means deduplicating by document id while preserving rank order — dict.fromkeys over the concatenated ids is exactly right, and it is the substrate under the fusion step described in Retrieval Techniques. Caching an embedding by (model_name, text) needs a tuple key. Counting which chunks get retrieved most often across a week of traffic is a Counter and one call to most_common(20), which is how you find the chunks worth rewriting.

7. Interview questions companies actually ask

"What is the time complexity of x in list versus x in set?" O(n) and O(1) average. Strong answer adds: the set's O(1) is average-case, amortised over resizes, and assumes a well-distributed hash; the absent-value case is the list's true worst case at exactly n comparisons.

"Why can't you use a list as a dictionary key?" Dict keys must be hashable, and hashability requires the hash to be stable for the object's lifetime. Lists are mutable, so their hash would change and the entry would become unfindable. Use a tuple. Strong answer: a tuple containing a list is also unhashable, because tuple hashing recurses into contents.

"When is a deque better than a list?" When you add or remove at the front, or need a fixed-size sliding window via maxlen. Strong answer names the real qualifier: list.pop(0) is O(k) in the list's length, so deque wins in proportion to the window size and wins nothing for a small window — and deque gives up O(1) random access in exchange.

"How would you deduplicate a list while preserving order?" list(dict.fromkeys(items)). Strong answer explains why: dicts have guaranteed insertion order since 3.7, and set() gives an order determined by hash values, which for strings is randomised per process.

"defaultdict versus dict.setdefault versus Counter?" Counter for counting, defaultdict(list) for grouping, setdefault when you want the default without the side effect of inserting on read. Strong answer names the defaultdict trap: reading a missing key inserts it.

"What is a hash collision and how does Python handle it?" Two values mapping to the same bucket. Python uses open addressing with probing, and keeps the load factor below about two-thirds by resizing, so collisions stay rare and lookups stay near-constant.

8. When to use / tradeoffs

set for membership and uniqueness. The only reasons not to are: you need order, you need duplicates, or the elements are unhashable. For fewer than a few dozen items the difference is unmeasurable, so a list is fine — but the set costs nothing extra to write, and it is the choice that stays correct as the data grows.

dict for key→value, and as an ordered set via fromkeys. Memory overhead is real — a dict costs meaningfully more per entry than a list — which matters at millions of entries and not before.

Counter for counting, always. There is no tradeoff. It is a dict subclass, so anything that accepts a dict accepts it.

deque when you push and pop at the front, or want a maxlen ring buffer. Do not reach for it reflexively: it is slower than a list for indexing, and for a small window there is no gain to have. The decision variable is the window size, not the presence of pop(0) in the code.

tuple when the value is a key, a record, or genuinely fixed. Cheaper and hashable. Use a NamedTuple or a dataclass once the tuple has more than about three fields, because result[2] is unreadable and result.score is not — see Python Advanced.

list as the default. It is the right answer for "a sequence of things in order," which is most data. The article is not an argument against lists; it is an argument against using a list for membership tests.

The one genuine judgement call is when to convert. Building a set from a list costs O(n) and hashes every element. If you will do more than a handful of membership tests, convert once and reuse. If you will do exactly one, the conversion costs more than the scan. The mistake worth avoiding is converting inside the loop — if x in set(big_list) rebuilds the set on every iteration and is strictly worse than the list scan it was meant to replace.

9. Summary + related articles

Container choice is a complexity decision wearing the clothes of a style decision. x in list is O(n) and x in set is O(1), and putting the former inside a loop is the standard route to an accidentally quadratic program — one that passes on fixture data and stalls on real data, because the failure scales with n and your tests do not.

The four supporting choices follow the same logic: Counter for counting, dict.fromkeys for order-preserving dedupe, tuples for keys because hashability requires immutability, and deque when the sliding window is large enough for the O(k) shift to matter. That last qualifier is the one most often stated wrongly, and the measurement in §5 shows why it deserves the care: at a window of 3 there is nothing to fix.

Related articles

  • Python Fundamentals — the object model underneath all of this, and why mutability and hashability are the same question
  • Python Advanced — generators for streaming, and dataclasses for when a tuple has grown too many fields
  • Python Best Practices — the type hints and tests that catch container misuse before it ships
  • Async Programming — the other common source of "fast in testing, slow in production"
  • Retrieval Techniques — merging ranked lists, which is order-preserving dedupe at scale
  • Tokenization — vocabularies are dicts, and merge lookup is exactly the hashed-membership pattern

Resources

← Previous: Python FundamentalsNext: Python Advanced →