Python list vs tuple vs set | Mutability· Performance

Introduction

Collections are the backbone of almost every Python program. Whether you are buffering log lines, representing database rows, or tracking unique user IDs, you choose between list, tuple, and set dozens of times per day. Picking the wrong type rarely makes code “wrong” in the sense of failing tests, but it can quietly inflate memory, turn O(1) operations into O(n) scans, or make your APIs harder to reason about when multiple threads or dict keys are involved.

This article is a deep, practical comparison—less “reference table,” more how I have learned to choose after shipping enough code the slow way. You will see how each type is created and used, how Python’s C implementation shapes real-world performance on CPython, and how to convert between types without subtle bugs. Where CPython behavior differs from the abstract data type (for example, set iteration order), the distinction is called out explicitly.

What you will learn

• How ordering, mutability, and hashability constrain your design.
• Concrete time and space characteristics, with reproducible benchmarks.
• Patterns for conversion, nesting, and deduplication in data pipelines.
• Mistakes that pass code review but fail in production (mutable defaults, accidental O(n²) dedup, set ordering assumptions).

Who this is for

Intermediate Python users who already write list comprehensions and basic sets, but want a single reference that ties syntax, complexity, and memory together. All examples target Python 3.10+ unless noted; micro-benchmarks were written for CPython and may differ on PyPy or other implementations.

---

Table of contents

1. Quick refresher
2. List: deep dive
3. Tuple: deep dive
4. Set: deep dive
5. Side-by-side comparison
6. Performance benchmarks
7. Memory comparison
8. Use cases and decision guide
9. Conversion patterns
10. Advanced patterns
11. Common mistakes (and ones I’ve made)
12. How I actually choose in real code
13. Real-world examples
14. Troubleshooting
15. Closing thoughts

---

Quick refresher

If you only read one paragraph before the deep dives: lists are your mutable, ordered workhorse—index, slice, append, duplicate values allowed, but membership is a linear scan. Tuples are immutable sequences: same indexing story, often a bit lighter, and they can be dict keys when every item is hashable. Sets are hash tables: average O(1) membership and enforced uniqueness, but no s[0], and you should not treat iteration order as part of your API contract even when CPython happens to preserve it.

Mutability is nuanced for sets: you do not assign s[i] = x, but you do mutate via add / remove. For a hashable set-like value, reach for frozenset.

Try this yourself: in a REPL, build the same thousand integers as a list, tuple, and set, then time needle in container for the worst-case needle. You do not need my numbers below to feel the gap between linear and ~constant-time membership.

The rest of the article unpacks each of these tradeoffs with examples and measurements.

---

List: deep dive

A list is a dynamic array: contiguous over-allocated storage of object references, exposed as a mutable sequence. Lists are the default “workhorse” when you need position, duplication, and in-place growth.

Creation, indexing, and slicing

# Literal and constructor
empty: list[int] = []
from_iter = list(range(5))  # [0, 1, 2, 3, 4]
copy_list = list(from_iter)

# Indexing: O(1) — direct offset into the array of pointers
first = from_iter[0]
last = from_iter[-1]

# Slicing returns a NEW list; bounds are forgiving
sub = from_iter[1:4]      # [1, 2, 3]
step = from_iter[::2]     # [0, 2, 4]

Why it matters: slicing always allocates a new list. In hot loops, prefer explicit start/stop indices or itertools.islice when you do not need a materialized copy. Indexing is fast, but scanning for membership is linear in the length of the list.

Mutating methods

xs: list[int] = [1, 2]

xs.append(3)        # add one element at end — amortized O(1)
xs.extend([4, 5])   # append each element of iterable — O(k) for k items
xs.insert(0, 0)     # insert at index — O(n) due to shifting tail
last = xs.pop()     # remove and return last — O(1) amortized
first = xs.pop(0)   # remove first — O(n)

xs.remove(2)        # remove first occurrence by value — O(n) search + O(n) shift
# xs.remove(99)     # ValueError if missing

xs.clear()          # release references; O(1) to clear size, dealloc may batch

append vs extend: append([1, 2]) nests a list; extend([1, 2]) adds two integers. This is one of the most common beginner bugs in data cleaning scripts.

List comprehensions and patterns

List comprehensions are both idiomatic and fast on CPython because the loop runs in optimized C.

squares = [x * x for x in range(10)]
even = [x for x in range(20) if x % 2 == 0]

# Prefer comprehensions over repeated append in a loop for simple transforms
# Bad (Python-level loop with attribute lookup each time):
result: list[int] = []
for x in range(1000):
    result.append(x * 2)

# Better (single comprehension; still creates the list eagerly)
result = [x * 2 for x in range(1000)]

Use generator expressions when you only need one pass and want lazy evaluation: (x * 2 for x in range(1000)).

Performance characteristics (lists)

Indexing is O(1) in the usual sense (bounds check, then pointer fetch). Membership x in lst is O(n)—there is no shortcut from “order” unless you have extra structure. append is O(1) amortized because the array over-allocates; insert(0, x) and pop(0) are O(n) because the tail shifts. sort is O(n log n) (Timsort) and often embarrasses hand-rolled sorts on real data. Taking a slice or copying k elements costs O(k) because you materialize a new list.

Memory behavior (lists)

Each list object stores a pointer array. When growth is needed, CPython over-allocates to keep append amortized constant time. sys.getsizeof on a list returns the size of the list object including the allocated array capacity, not the size of the objects the list references.

import sys

small: list[int | str] = []
print(sys.getsizeof(small))  # small base overhead

nums = list(range(10_000))
print(sys.getsizeof(nums))   # grows with allocated capacity

# Total memory is getsizeof(list) + sum of objects (ints may be shared/small-int cached)

For huge numeric arrays, consider array.array or NumPy—plain lists store PyObject* pointers, not packed C doubles.

---

Tuple: deep dive

A tuple is an immutable sequence. Once created, you cannot change its length or replace its items. Tuples are ideal for fixed records, multiple return values, and hashable keys when their elements are hashable.

Creation and immutability

t = (1, 2, 3)
singleton = (42,)      # trailing comma — NOT (42) which is int
no_parens = 1, 2, 3    # still a tuple

# t[0] = 10  # TypeError

# Beware: mutability of CONTENTS if items are mutable
bad_key = ([1], 2)
# bad_key[0].append(2)  # allowed — mutates the list inside the tuple

Shallow immutability: a tuple containing a list is still “immutable” as a sequence, but the list inside can change. That breaks hashability and is a common source of subtle dict key bugs.

Packing and unpacking

point = 10, 20
x, y = point

# Extended unpacking
first, *rest = (1, 2, 3, 4)
# first == 1, rest == [2, 3, 4]

# Star in the middle
a, *mid, b = (1, 2, 3, 4, 5)
# a == 1, mid == [2, 3, 4], b == 5

# Swapping without temp — tuple packing
a, b = 1, 2
a, b = b, a

Unpacking is implemented efficiently and is preferred over index spaghetti for small fixed arity.

Named tuples

collections.namedtuple and typing.NamedTuple attach field names to tuple slots, improving readability for structured data without the weight of a full class.

from collections import namedtuple
from typing import NamedTuple

User = namedtuple("User", ["id", "name", "email"])
u = User(1, "Ada", "[email protected]")
print(u.name, u[1])

class Point(NamedTuple):
    x: float
    y: float

p = Point(1.0, 2.0)
print(p.x)

Use NamedTuple or dataclasses when you want type hints and optional methods; use plain tuples for hot inner loops or interop with C extensions that expect tuples.

When to use tuple vs list

So which should you use? Here is how I think about it. I reach for a tuple when the shape is fixed—multiple return values, a point (x, y), a composite key (user_id, shard)—and I want either hashability or a strong “this is a snapshot” signal. I reach for a list when I am still building the collection, when I need in-place sorts or reversals, or when duplicates and position are part of the meaning. If two parts of the code share a structure and only one side must mutate it, the tuple side is the one I do not want accidentally .append’d on.

Performance advantages

Indexing and length are O(1) like lists. Tuples are often slightly faster to construct and iterate in micro-benchmarks because their size is fixed. The larger win is semantic: immutability makes data flow easier to follow and enables hashing when all elements are hashable.

locations = {
    (0, 0): "origin",
    (1, 0): "east",
}

---

Set: deep dive

A set is an unordered collection of unique hashable items, backed by a hash table (similar to dict keys). Membership, add, and discard are average O(1); iteration is O(n).

Creation and uniqueness

s = {1, 2, 3, 2, 1}        # {1, 2, 3}
from_str = set("hello")    # {'h', 'e', 'l', 'o'}
from_list = set([1, 1, 2])

# Empty set MUST be set() — {} is a dict
empty: set[int] = set()

Uniqueness is by hash + equality: objects that compare equal collapse to one entry. For user-defined classes, ensure __hash__ and __eq__ are consistent.

Set operations: algebra in code

a = {1, 2, 3, 4}
b = {3, 4, 5, 6}

a | b    # union: {1..6}
a & b    # intersection: {3, 4}
a - b    # difference: {1, 2}
a ^ b    # symmetric difference: {1, 2, 5, 6}

# In-place variants update the left operand
a |= b

These operations are linear in the size of the operands in the worst case, but with good constants for typical sizes. For two large sets, consider the smaller one for the inner side of nested patterns (see benchmarks).

frozenset

frozenset is an immutable set. It is hashable if all elements are hashable, so you can use it as a dict key or store it inside another set.

fs = frozenset([1, 2, 3])
registry: dict[frozenset[str], str] = {}
registry[frozenset(["read", "write"])] = "rw-role"

Use frozenset when you need set semantics but also need immutability as a value object.

Hash requirements

Only hashable objects may be placed in a set: typically None, numbers, strings, bytes, tuples of hashables, and frozenset. Lists, dicts, and regular sets are not hashable.

# ok = {[], 1}       # TypeError: unhashable type: 'list'
ok = { (1, 2), "x" }

Performance characteristics (sets)

Membership x in s, add, and discard are O(1) on average; the rare worst case is O(n) when hashes collide badly. Union and intersection scale roughly with the sizes of the operands—O(n + m) in typical implementations, with constants that matter in real code. Iteration is O(n), but order is not part of the abstract contract, so do not encode business rules in “first item from the set.”

---

Side-by-side comparison

So which should you use? Here is the short version I run through when I am tired and just need a default. Literals: [1, 2] for list, (1, 2) or 1, 2 for tuple, {1, 2} for set; empty set is set(), not {}, because {} is a dict. Mutability: list and set are mutable in their own ways; tuple is not. Indexing and slicing: lists and tuples yes; sets no—no set[0]. Duplicates: allowed in list and tuple; sets enforce uniqueness. Membership: O(n) for list and tuple, O(1) average for set. Sorting: lists can sort in place; for tuples you typically build sorted(t); sets do not have a meaningful “sort in place.” As dict keys: tuple (if items are hashable) or frozenset; plain list and set are out. Memory: for the same n integers, sets usually cost more than lists or tuples because of hash table bookkeeping—see the memory section below.

The mermaid diagram in the next section is the same decision, just drawn.

Performance benchmarks

Micro-benchmarks are environment-sensitive. Run them on your target Python version and hardware; use them to compare relative costs, not absolute truth. The following script uses timeit for stable timing.

I was surprised the first time I ran something like this: list and tuple membership in the worst case were in the same ballpark (both linear scans), but the set line looked almost free next to them at n = 200_000. Not because sets are magic—because hash lookups scale differently than “compare every element.” The exact microsecond numbers will change on your laptop; the shape of the comparison usually does not.

Try this yourself: change n, try a needle at index 0 instead of n - 1, and watch how “fast” list membership looks when the scan ends early. That is a good reminder that big-O is not the whole story, but also that worst-case behavior still matters when your data is adversarial or unlucky.

import timeit

n = 200_000
needle = n - 1
lst = list(range(n))
tup = tuple(range(n))
st = set(range(n))

def bench(name: str, stmt: str, setup: str = "pass", number: int = 50) -> None:
    t = timeit.timeit(stmt, setup, number=number) / number
    print(f"{name:28s} {t * 1e6:8.1f} µs/iter")

setup_all = f"""
n = {n}
needle = {needle}
lst = list(range(n))
tup = tuple(range(n))
st = set(range(n))
"""

bench("list membership (worst)", "needle in lst", setup_all)
bench("tuple membership (worst)", "needle in tup", setup_all)
bench("set membership", "needle in st", setup_all)

bench("list 1k appends", "for i in range(1000): xs.append(i)", "xs = []", number=200)
bench("set 1k adds", "for i in range(1000): s.add(i)", "s = set()", number=200)

# Build unique from a list with duplicates — keep size moderate for the setup string
m = 50_000
setup_dup = f"dup = list(range({m // 2})) * 2"
bench("dedup via set", "list(set(dup))", setup_dup, number=30)
bench("dedup preserve order (dict)", "list(dict.fromkeys(dup))", setup_dup, number=30)

How to read results: For large n, needle in lst grows linearly; needle in st stays nearly flat. Building list(set(xs)) is fast for uniqueness but destroys order; dict.fromkeys preserves insertion order (Python 3.7+) while deduplicating.

Optional: perf_counter for end-to-end tasks

import time
from contextlib import contextmanager

@contextmanager
def time_block(name: str):
    t0 = time.perf_counter()
    yield
    dt = time.perf_counter() - t0
    print(f"{name}: {dt * 1000:.2f} ms")

# Example usage:
with time_block("build + scan"):
    data = list(range(500_000))
    _ = 499_999 in data

Use this when I/O or large object creation dominates and timeit micro-slices are misleading.

---

Memory comparison

sys.getsizeof returns the size of the container object itself, not a full deep size. For a more complete view, also consider pympler or tracemalloc in long-running services.

import sys

def describe(name: str, obj: object) -> None:
    r = repr(obj)
    tail = "..." if len(r) > 40 else ""
    print(f"{name:20s} getsizeof={sys.getsizeof(obj):8d}  repr={r[:40]}{tail}")

n = 10_000
rng = range(n)

describe("empty list", [])
describe("list(range(10k))", list(rng))
describe("tuple(range(10k))", tuple(rng))
describe("set(range(10k))", set(rng))

# Single large int vs many small ints — small int cache affects repeatability
describe("one int 10**18", 10**18)

Typical pattern: for the same n unique integers, tuple often uses less overhead than list (no overallocation for future appends). set uses more memory per element because each slot stores hash table metadata in addition to object references.

Try this yourself: run the snippet, then compare empty containers: getsizeof([]), getsizeof(()), and getsizeof(set()). Fill each with the same range(10_000) and compare again—sets are usually the chunkiest, and that matches what you will see in RSS if you build huge structures in a long-running process.

---

Use cases and decision guide

The flowchart below is what I use when I am not sure—order for the API is the fork that saves me from reaching for a set when I still care about display order.

graph TD
    A[Pick a structure] --> B{Order matters for your API?}
    B -->|Yes| C{Need in-place edits or dynamic size?}
    B -->|No| D{Need unique elements or fast membership?}
    C -->|Yes| E[list]
    C -->|No| F{Need as dict/set key?}
    F -->|Yes| G[tuple or NamedTuple]
    F -->|No| H{Need immutability for safety?}
    H -->|Yes| G
    H -->|No| E
    D -->|Yes| I[set or frozenset]
    D -->|No| J[Revisit — order may still matter for display]

Practical defaults: for streaming input when I do not know the final size, I almost always use a list (if I need fast pops from both ends, a deque is the next step, but that is a different article). For coordinates, RGB triples, or composite primary keys, tuple feels right. Tags, permissions, and “have I seen this node?” are set problems. JSON only has arrays, so the wire format maps to list; I dedupe on ingest if the domain really wants uniqueness.

---

Conversion patterns

List ↔ Tuple

xs = [1, 2, 3]
t = tuple(xs)          # copy if xs is a list — O(n)
back = list(t)         # new list

# “Freeze” for consumers
def process(items: list[int]) -> tuple[int, ...]:
    return tuple(sorted(items))

Iterable → Set (dedup)

raw = [1, 2, 2, 3, 1]
unique = set(raw)              # unordered
unique_list = list(dict.fromkeys(raw))  # preserve first-seen order (3.7+)

Set ↔ List for sorting

s = {3, 1, 2}
sorted_values = sorted(s)      # list, ascending

Nested structures

# list of tuples — common CSV / SQL row shape
rows: list[tuple[str, int]] = [("ada", 1), ("bob", 2)]

# set of tuples — if rows need uniqueness by full row
unique_rows = set(rows)

Caution: converting a list of lists to a set fails because inner lists are unhashable. Convert inner lists to tuples first if the rows should be hashable.

---

Advanced patterns

Nested collections

from collections import defaultdict

# Adjacency list: node -> list of neighbors
graph: dict[str, list[str]] = {
    "A": ["B", "C"],
    "B": ["A"],
}

# Invert index: token -> set of document ids
inverted: dict[str, set[int]] = defaultdict(set)
for doc_id, text in [(1, "aa bb"), (2, "bb cc")]:
    for token in text.split():
        inverted[token].add(doc_id)

defaultdict avoids if key not in d: d[key] = … boilerplate. Pick set as the inner factory when uniqueness is natural (ids, tags); pick list when duplicates matter.

dict + set patterns for counting

For frequencies, collections.Counter is ideal; it is built on dict and designed for this use case.

from collections import Counter

words = ["a", "b", "a", "c", "b", "a"]
c = Counter(words)
print(c.most_common(2))

Type hints for collections

from typing import Iterable

def unique_sorted(values: Iterable[int]) -> list[int]:
    return sorted(set(values))

---

Common mistakes

I used to default to lists for almost everything—mutable, familiar, easy to log—and only later paid the price when membership checks or deduplication sat in a hot loop. I also used to assume “set iterates in insertion order” was something I could rely on in reviews; it is safer to treat sets as unordered unless your project explicitly documents otherwise.

Mutable default arguments

# BAD: shared list across calls
def append_item_bad(item, acc=[]):  # noqa: B006 — intentional bad example
    acc.append(item)
    return acc

# GOOD: new list each time
def append_item_good(item, acc: list[int] | None = None) -> list[int]:
    if acc is None:
        acc = []
    acc.append(item)
    return acc

Assuming set order is stable for business logic

Even if CPython preserves insertion order for sets in many versions, your program’s correctness should not depend on “the first element of a set” unless you explicitly sort or use dict.fromkeys / an ordered structure.

Membership on the wrong container

needles = range(1000)
haystack_list = list(range(1_000_000))
haystack_set = set(haystack_list)

# Slow: O(len(needles) * len(haystack))
# [n in haystack_list for n in needles]

# Fast for lookups: O(len(needles)) average for set
[n in haystack_set for n in needles]

tuple “immutability” with mutable elements

t = ([1],)
t[0].append(2)   # tuple unchanged, list inside changed — key may break

Accidental O(n²) dedup in a loop

# Bad: repeated scans
out: list[int] = []
for x in some_big_iterable:
    if x not in out:   # O(len(out)) each time
        out.append(x)

# Better: amortized single pass with seen set
seen: set[int] = set()
out2: list[int] = []
for x in some_big_iterable:
    if x not in seen:
        seen.add(x)
        out2.append(x)

---

How I actually choose in real code

This is not documentation; it is what I tell myself when I am about to ship. For simple transforms I default to comprehensions or, if the data is numeric and huge, something vectorized—not because lists are “slow,” but because Python-level loops add up. If I will ask x in container many times and the collection is large and stable, I build a set once and query it many times; the O(1) vs O(n) split is the one that has actually shown up in profiling for me. For fixed-shape returns from a function, I like tuples because the type says “this bundle is one thing,” and callers get a hashable value for free when the items allow it. In public APIs I try to say out loud whether order is contract—otherwise someone will “fix” performance in a way that changes behavior. I do not ship business rules that depend on “the first element of a set.” And I profile before I rewrite hot paths; the bottleneck is often I/O or something I did not expect, not list vs tuple.

---

Real-world examples

Data processing: parsing and cleaning

def clean_tokens(raw: str) -> list[str]:
    # normalize, split, dedup preserving order
    tokens = [t.lower().strip(",.") for t in raw.split()]
    return list(dict.fromkeys(tokens))

Graph or web crawl: visited tracking

def crawl(start: str, neighbors: dict[str, list[str]]) -> list[str]:
    visited: set[str] = set()
    order: list[str] = []

    stack = [start]
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        order.append(node)
        stack.extend(neighbors.get(node, []))
    return order

Relational-style join with set intersection

users_with_role_a = {1, 2, 3, 5}
users_with_role_b = {3, 4, 5, 6}
both = users_with_role_a & users_with_role_b

---

Troubleshooting

TypeError: unhashable type: 'list' usually means you put a list in a set or used a list as a dict key. I fix that by converting to tuple (if the row should be hashable), using frozenset for set-of-sets cases, or storing a string key if that is what the domain actually needs.

Slow in on a huge list is almost always “you are doing a linear scan.” If the collection is static and you query it many times, build a set once.

KeyError on set.remove means the element was not there; if “missing is fine,” I use discard instead.

Flaky tests around sets often come from asserting on iteration order. I compare with sorted(s) or assert set equality with rules that do not depend on order.

Memory spikes when building a large set are often the hash table tax. Sometimes that is worth it; sometimes I batch, chunk, or keep a Bloom filter or other structure—depends on the problem.

Duplicates that will not go away usually mean the objects are not equal when you think they are. I normalize before dedup or fix __eq__ / __hash__ for custom types.

---

Closing thoughts

list, tuple, and set are not rivals—they are tools with different invariants. Lists give you a mutable, ordered sequence; tuples give you a lightweight, fixed record with optional hashability; sets give you uniqueness and fast membership at the cost of ordering semantics and memory. When in doubt, write the smallest code that expresses your intent, then measure if profiling shows a hot path.

If you take one habit from this article, take this: build a set once for many membership checks, and be explicit in your APIs about whether order is part of the contract. Those two choices prevent the majority of accidental quadratic behavior and ordering bugs in production Python.

---

Related posts

• Python data structures
• Python performance
• Python collections

---

Keywords

Python, list, tuple, set, data structures, time complexity, memory, comparison, frozenset, namedtuple, defaultdict, benchmark