PythonData StructuresPerformance

List vs Set in Python — Performance, Use Cases

List vs Set in Python: iteration speed, O(1) membership testing, memory trade-offs, and exactly when to use each — with benchmark results.

July 6, 20254 min readRishabh Singh
Python List vs Set performance comparison overview
List vs Set — same surface, completely different engines underneath.

The Setup

When building Python applications, selecting the right data structure affects both code readability and performance. Lists and sets are two of the most frequently used containers — but they have dramatically different implementations under the hood.

A list stores elements in contiguous memory in insertion order. A set stores elements in a hash table — no guaranteed order, no duplicates, O(1) lookup. Same Python syntax, completely different trade-offs.

Iteration: Lists Win

1 How Lists Iterate

Lists maintain elements in contiguous memory. When you loop over a list, Python steps through a flat block of memory — no jumping, no hashing, no indirection. Cache-friendly sequential access makes this fast.

2 How Sets Iterate

Sets use hash tables. Memory is sparse and scattered — Python must walk the internal hash array, skip empty buckets, and compute hashes as it goes. More work per element, more cache misses.

"Lists are faster than sets when it comes to iterating over elements."
Benchmark showing list iteration speed vs set iteration speed in Python
Iteration benchmark: list's contiguous memory gives a consistent speed advantage over set's hash-table traversal.

Membership Testing: Sets Win — By Orders of Magnitude

1 List Membership — O(n)

x in my_list performs a linear scan — Python checks every element from index 0 until it finds a match or exhausts the list. For a list of 1,000,000 elements, worst case means 1,000,000 comparisons.

2 Set Membership — O(1)

x in my_set computes hash(x), jumps directly to the corresponding bucket, and checks one (or a handful of) elements. For a set of 1,000,000 elements, that's still one hash computation — regardless of size. For the full story of how the hash table pulls this off — open addressing, collisions, resizing — see why sets outperform lists.

"Sets are significantly faster than lists for membership operations."
Benchmark showing set membership testing is dramatically faster than list membership at scale
Membership testing: set's O(1) hash lookup vs list's O(n) linear scan — the gap widens with collection size.

Best Practices

Use a List When:

  • Order matters — you need elements in insertion sequence
  • Index-based access is needed — my_list[i]
  • Iteration and looping are the primary operations
  • Duplicates are allowed or required

Use a Set When:

  • Checking presence with the in operator
  • Ensuring uniqueness — sets automatically deduplicate
  • Rapid membership testing at any scale
  • Set operations: union (|), intersection (&), difference (-)
Full comparison chart: list vs set across iteration and membership testing benchmarks
Complete benchmark: list dominates iteration, set dominates membership. The right choice depends entirely on your access pattern.

Key Takeaways

  • Iteration → use a list. Contiguous memory = fast loops.
  • Membership testing → use a set. Hash table = O(1) lookup, always.
  • Need both? Keep a list for order/iteration, maintain a parallel set for fast lookups.
  • These small decisions matter in performance-sensitive applications — switching list to set for in checks can reduce a tight loop from O(n²) to O(n).

Frequently Asked Questions

Is list or set faster for iteration in Python?

Lists are faster for iteration. They store elements in contiguous memory, enabling cache-friendly sequential access. Sets use hash tables with scattered memory and hashing overhead, making iteration slower.

Is list or set faster for membership testing (in operator)?

Sets are dramatically faster. Sets use hash tables for O(1) average-case lookup. Lists perform a linear O(n) scan — checking every element until a match is found or the list is exhausted.

When should you use a Python set instead of a list?

Use a set when you need to check membership with in, ensure uniqueness, or perform rapid lookup at scale. Sets eliminate duplicates automatically and provide O(1) average-case membership testing.

What is the time complexity of in for list vs set?

For a list, x in my_list is O(n) — it scans every element. For a set, x in my_set is O(1) average case — it computes the hash and jumps directly to the bucket.

Can a Python set contain duplicates?

No. Sets automatically deduplicate — adding the same element twice has no effect. If you need to store duplicates, use a list or multiset (via collections.Counter).

Back to BlogRead on Medium