Choosing the right data structure

Why membership cost decides your data structure

Reach for the wrong container and a fast function turns slow without a single line looking "wrong." The trap is x in collection. It reads the same for a list, a set, and a dict, but it does very different amounts of work. On a list, Python compares x against elements one at a time until it finds a match or runs out. On a million-element list that is up to a million comparisons for one lookup. Do that inside a loop and you have an O(n²) function that crawls on real data. Interviewers hand you exactly this shape and watch whether you notice.

The mental model

A list is a dynamic array: values laid out in order, great for indexing and iteration, but membership means scanning. A set (and a dict) is a hash table: each element runs through a hash function that computes where it lives, so x in a_set jumps almost straight to the right slot instead of walking everything.

x in a_list    # O(n): walk the list until found or exhausted
x in a_set     # O(1) average: hash x, look in one slot
x in a_dict    # O(1) average: same hashing, keyed lookup

O(n) means cost grows with size; O(1) means it stays flat whether the set holds ten items or ten million. That is the instinct to build: when you repeatedly ask "have I seen this?", reach for a set.

Table

Only the first row differs by an order of magnitude, and it is the row that reads identically in source. x in c looks the same for all three, which is exactly why the wrong container hides so well.

Operation	list	set	dict
x in c	O(n): scans until found	O(1) average	O(1) average, over keys
c[i] by position	O(1)	not supported	not supported
c[key] by key	not supported	not supported	O(1) average
Add one item	O(1) amortised (append)	O(1) average (add)	O(1) average
Keeps insertion order	yes	no	yes, since Python 3.7
Accepts unhashable items	yes	no	values yes, keys no

The classic upgrade

The demo below turns a list into a set and compares lengths. set(nums) drops duplicates, so if the set is shorter than the list, something repeated. That length comparison is the whole idea behind has_duplicates. When you need the scan itself, grow a seen set as you go:

seen = set()
for x in nums:
    if x in seen:      # O(1) check, not a rescan
        ...            # x is a repeat, handle it here
    seen.add(x)

That loop is O(n): one pass, each check flat. The list version, if x in seen against a growing list, would be O(n²).

Pitfalls

• set(nums) throws away order. It can tell you THAT a value repeated, but not WHICH one repeated first. For first_repeated you must scan left to right and test a growing seen set, returning the first x that is already inside it.

• Set and dict elements must be hashable, which in practice means immutable. {[1, 2]} raises TypeError: unhashable type: 'list'. Numbers, strings, and tuples are fine; lists, dicts, and sets are not.

Interview nuance: O(1) membership is average case, not a guarantee. A hash table is fast because elements scatter across many slots, but adversarial or unlucky inputs can collide into one slot and degrade a single lookup toward O(n). You also trade memory for that speed. So the honest answer to "why not always use a set?" is that sets cost extra memory, accept only hashable values, and keep no order.