List vs Tuple vs Set in Python: Order, Mutability, Hashing

List vs tuple vs set in Python in one line: a list is an ordered sequence you can change, a tuple is an ordered sequence you cannot change, and a set is an unordered collection of unique, hashable items built on a hash table. The first two share a layout and answer "what is at position i?"; the set answers "is x in here?" without scanning. That one difference decides membership cost, whether the thing can be a dictionary key, and what the reader of your code should assume it means. The behaviour below is run live on Python 3.9 and checked against the Python documentation, as of October 2026.

Type	What it promises	Typical job
list	order, duplicates, in-place changes	a collection that grows: results, a stack, a queue of work
tuple	order, duplicates, no changes; hashable if its items are	a record: a point, a row, a composite dict key
set	uniqueness, fast in; no order, no index	membership: seen nodes, allowed values, deduplication

The problem it solves

All three hold "some values", so beginners pick whichever bracket they typed first. The cost shows up later: a visited list in a graph search turns an O(V + E) traversal into something closer to quadratic, a list used as a dict key raises TypeError, and a set used where order mattered prints results in a different order on every machine. Choosing well is mostly about which question your code asks most often.

The intuition

Start from what each type is underneath.

• A list is an array of references. CPython stores pointers to the items back to back, so xs[i] is one address calculation and append is amortised O(1). Asking x in xs has no shortcut: it compares x with each item from the front until one matches, O(n).
• A tuple is the same array, frozen. Indexing and in cost exactly what they cost on a list. What changes is the contract: no append, no item assignment, and therefore a hash. A tuple whose items are all hashable can be a dict key or a set member, which is why (row, col) is the standard key for grid problems. The documentation describes tuples as typically holding heterogeneous data and lists as typically holding homogeneous items: a tuple reads as a record with fixed fields, a list as "more of the same".
• A set is a hash table with keys and no values. x in s hashes x, jumps to a slot and compares a handful of candidates, so membership is O(1) on average. The price: items must be hashable, duplicates collapse, and iteration order is whatever the table's layout gives, not insertion order.

Immutability is shallow. A tuple holding a list cannot have that slot reassigned, but the list inside can still change, and such a tuple is not hashable at all. If you need an immutable, hashable set, frozenset exists for exactly that.

When to use which

• You append, sort, or index by position: list.
• The values are one record with a fixed shape, or you need a dict key made of several parts: tuple. A namedtuple or frozen dataclass when the fields deserve names.
• The main operation is "have I seen this?" or "is this allowed?": set. Build it once, test many times.
• You need unique values in first-seen order: list(dict.fromkeys(items)), because dicts keep insertion order and sets do not.

Watch it run

The lesson's animation is the layout lists and tuples share. Four prices sit back to back, so slot i is always at base + i × size; prices[2] lands straight on its slot in one arithmetic step. prices[0] = 99 overwrites in place for the same cost, append(8) drops in at the end with nothing moving, and insert(1, 42) has to push every later value one slot right, four shifts here and n in general. A tuple is that row without the last three frames: same instant read, no writes at all. A set is the one structure that does not look like this row, because it places each value by its hash rather than by position.

The code

Behaviour first: what each type allows, what can be a key, and the size of the container itself for a thousand integers on 64-bit CPython 3.9:

import sys

point_list = [3, 4]
point_tuple = (3, 4)
tags = {"python", "interview", "python"}       # the duplicate disappears

point_list[0] = 5                              # a list changes in place
print(point_list, point_tuple, sorted(tags))   # [5, 4] (3, 4) ['interview', 'python']
try:
    point_tuple[0] = 5
except TypeError as e:
    print(e)                                   # 'tuple' object does not support item assignment
try:
    tags[0]
except TypeError as e:
    print(e)                                   # 'set' object is not subscriptable

visits = {(3, 4): "home"}                       # a tuple can be a dict key
try:
    visits[[3, 4]] = "home"
except TypeError as e:
    print(e)                                   # unhashable type: 'list'
try:
    hash((3, [4]))                              # ...only if everything inside is hashable
except TypeError as e:
    print(e)                                   # unhashable type: 'list'

n = 1000
for kind in (list, tuple, set):
    print(kind.__name__, sys.getsizeof(kind(range(n))))
# list 8056
# tuple 8040
# set 32984

sys.getsizeof counts only the container, not the integers it points to. The list and tuple are both about eight bytes per slot; the tuple's header is slightly smaller and, unlike a list grown by append, it never keeps spare slots. The set is roughly four times larger, because a hash table keeps empty slots so that lookups stay short.

Now the cost of in on a miss, the worst case for a scan, with 10,000 items:

import timeit

n = 10_000
as_list, as_tuple, as_set = list(range(n)), tuple(range(n)), set(range(n))
missing = -1                                   # a miss: the worst case for a scan

def cost(container):
    return min(timeit.repeat(lambda: missing in container, number=200, repeat=5))

def verdict(slow, fast):
    ratio = slow / fast
    if ratio < 2:
        return "about the same"
    return "over 100x" if ratio > 100 else "between 2x and 100x"

t_list, t_tuple, t_set = cost(as_list), cost(as_tuple), cost(as_set)
print("tuple vs list:", verdict(max(t_list, t_tuple), min(t_list, t_tuple)))
print("list vs set:  ", verdict(t_list, t_set))
# tuple vs list: about the same
# list vs set:   over 100x
# on one machine, roughly; the verdicts held across runs, the ratios did not

On one machine, roughly, the set was more than a thousand times faster here, and the gap grows with n because one side is linear and the other is not. Finally a seeded cross-check that all three agree on membership, that a set keeps exactly the distinct values, and that dict.fromkeys deduplicates in first-seen order:

import random

def dedupe_keep_order(items):                  # set loses order; dict keeps insertion order
    return list(dict.fromkeys(items))

def first_seen(items):                         # the slow, obvious reference
    out = []
    for x in items:
        if x not in out:
            out.append(x)
    return out

random.seed(7)
ok = True
for _ in range(2000):
    items = [random.randint(0, 20) for _ in range(random.randint(0, 30))]
    as_tuple, as_set = tuple(items), set(items)
    for q in range(-2, 23):
        ok &= (q in items) == (q in as_tuple) == (q in as_set)
    ok &= len(as_set) == len(first_seen(items))
    ok &= dedupe_keep_order(items) == first_seen(items)
print(ok)                                      # True
print(dedupe_keep_order([3, 1, 3, 2, 1]))      # [3, 1, 2]

The complexity

• Index xs[i]: O(1) for list and tuple; a set has no index.
• Membership x in c: O(n) for list and tuple; O(1) average for a set, O(n) in the rare case where many items collide.
• Add: append amortised O(1), insert(0, x) O(n); tuple has no add; set.add O(1) average.
• Build a set from n items: O(n), so converting once is worth it as soon as you test more than a few values.
• Memory: tuple ≤ list < set for the same items.

Where it goes wrong

• A list as the visited structure. Every check is a scan; in a BFS over thousands of nodes that dominates the run time. Use a set.
• Expecting a set to keep order. Printing or returning list(set(xs)) gives an order that depends on hashes and table size. Sort it, or deduplicate with dict.fromkeys.
• A list as a dict key. It is unhashable by design: if it changed after insertion, the dict could no longer find it. Convert to a tuple, which is the documented way.
• "Tuples are faster." Creating a constant tuple is cheaper and it is a little smaller, but indexing and in are the same as on a list. Choose a tuple for meaning, not speed.
• {} for an empty set. That is an empty dict; write set().

When it shows up in interviews

Constantly, and usually indirectly: "why is your solution slow?" when a visited list hides an O(n) check, or "how do you key a memo on two arguments?" where the answer is a tuple. The dict side of hashing, and when a sorted structure beats it, is in hash map vs tree map; why a list's middle insert is costly, and why a linked list does not really fix it, is in array vs linked list. The layout itself is the Array Basics lesson.

How to say it in an interview

"A list and a tuple are both arrays of references, so indexing is O(1) and in is a linear scan. The list is mutable and meant for collections that grow; the tuple is immutable, so it is hashable when its items are, which makes it the right key for things like grid coordinates or memo arguments. A set is a hash table: in is O(1) on average, duplicates collapse and there is no order. So for visited I use a set, for a composite key a tuple, and for ordered results a list."

Frequently asked questions

What is the difference between a list, a tuple and a set in Python?

A list is an ordered, mutable sequence. A tuple is an ordered, immutable sequence that is hashable when its items are. A set is an unordered collection of unique hashable items with average O(1) membership tests. Lists and tuples allow duplicates and indexing; sets allow neither.

Is checking membership in a set faster than in a list?

Yes, for anything but tiny collections. x in some_list compares items one by one, O(n); x in some_set hashes x and checks a few slots, O(1) on average. Building the set costs O(n) once, so convert when you will test membership repeatedly.

Why can a tuple be a dictionary key but a list cannot?

Dict keys must be hashable, and a hash must not change while the key is stored. A list can change, so it has no hash. A tuple cannot change, so it is hashable, provided every item inside it is hashable too; (1, [2]) is not.

Sources

• Built-in Types: Sequence Types (list, tuple) and Set Types — Python Documentation
• Data Structures: tuples and sets — Python Documentation
• Glossary: hashable — Python Documentation
• sys.getsizeof — Python Documentation