Lists & Tuples
Lists are ordered, mutable sequences; tuples are ordered, immutable ones. Knowing which to reach for — and the cost of each operation — is core Python fluency.
Learning objectives
- › Contrast list mutability with tuple immutability and choose the right one
- › Reason about the time complexity of common list operations
- › Use slicing and list comprehensions idiomatically
- › Avoid aliasing bugs and know when to shallow- vs deep-copy
Prerequisites
Version notes
- · `list.copy()` arrived in Python 3.3; before that, copy a list with `lst[:]` or `list(lst)`.
- · Starred assignment for unpacking (`first, *rest = seq`) has been available since Python 3.0 (PEP 3132).
Simple explanation
What it is. A list is an ordered, mutable sequence — you can grow it, shrink it and rewrite items in place. A tuple is an ordered, immutable sequence — once built, its slots are fixed. Both simply hold references to objects in insertion order.
Why it exists. Ordered collections are everywhere, and the mutable/immutable split lets you signal intent: a list says 'this will change', a tuple says 'this is a fixed record'. Immutability also unlocks hashability, so tuples can be dict keys and set members while lists cannot.
The problem it solves. A list gives you a growable, editable buffer for homogeneous data; a tuple gives you a fixed, safe-to-share record (coordinates, a multi-value return, a key) that no one can mutate underneath you.
How it works. CPython backs a list with a dynamic array of pointers that over-allocates spare capacity, so append is amortized O(1) while indexing lst[i] is O(1). A tuple is a fixed-size array allocated once. Membership (`x in lst`) and insert(0, x) are O(n) because they scan or shift every element.
Analogy: A list is a whiteboard you keep editing; a tuple is a printed receipt — fixed the moment it is made, and safe to file away (hash) as a key. Repainting a house you have several sticky-note references to is visible through all of them: that is aliasing.
Common misconceptions
- "A tuple is just a read-only list." — Its real value is being a fixed, hashable record; that hashability (not speed) is why it can be a dict key or set element.
- "A tuple's contents can never change." — The tuple's slots are fixed, but if a slot holds a mutable object (a list), that inner object can still be mutated.
- "Slicing gives you a view onto the original." — In core Python, `lst[a:b]` builds a brand-new (shallow) list; only NumPy-style objects return views.
- "Tuples are always much faster than lists." — The difference is marginal; choose by mutability and meaning, not micro-benchmarks.
Common alternatives
- collections.deque for O(1) appends and pops at BOTH ends
- array.array or NumPy arrays for large blocks of numeric data
- collections.namedtuple / typing.NamedTuple for readable, immutable records
Code examples
Note: Unpacking a tuple into names is packing/unpacking — the idiomatic way to return and receive several values.
Behind the scenes
- ▸A CPython list is a dynamic array of pointers (PyObject*), not the objects themselves; it over-allocates spare slots so most appends are amortized O(1).
- ▸When spare capacity runs out the list grows by roughly 1.125x and copies its pointers — the occasional O(n) resize is amortized across many cheap appends.
- ▸insert(0, x) and pop(0) are O(n) because every following pointer must shift; use collections.deque when you need fast operations at the front.
- ▸A tuple is a fixed-size array built once; its unchanging length lets CPython give it a smaller footprint and reuse small tuples.
- ▸A tuple is hashable only if ALL its elements are hashable — that is exactly what lets an all-immutable tuple serve as a dict key or set element.
Interview insights
Key definitions
- · List: an ordered, mutable sequence backed by a dynamic array of object references.
- · Tuple: an ordered, immutable sequence; hashable when every element it holds is hashable.
When would you use a tuple instead of a list?
Concise answer: Use a tuple for a fixed, often heterogeneous record that should not change — coordinates, a multi-value return, or a dict/set key (tuples are hashable). Use a list for a homogeneous, growable collection you will edit.
Detailed answer: The deciding factor is mutability and hashability, not speed. Immutability documents intent and prevents accidental mutation of shared data; hashability lets a tuple be a dict key or set member. Lists are the right tool when you append, sort, or rewrite items over time. Tuple packing/unpacking (x, y = point) is also the idiomatic way to return and receive several values at once.
Common mistake: Thinking a tuple is 'just a faster list' — the real reasons are immutability and hashability.
Follow-ups:
- · Can a tuple ever appear to change?
- · What makes a tuple hashable?
What is the time complexity of append, insert(0), membership, and index access on a list?
Concise answer: append is amortized O(1); insert(0, x) and pop(0) are O(n) because elements shift; `x in lst` is O(n); lst[i] index-by-position is O(1).
Detailed answer: A list is a dynamic array. Appending usually just writes into pre-allocated space (amortized O(1)), with an occasional O(n) resize. Inserting or removing at the front shifts every remaining pointer, so it is O(n). Membership and .index() scan linearly. Accessing by a known position is a direct array index, O(1). When you need O(1) at both ends, use collections.deque.
Common mistake: Assuming `in` or .index() is O(1) like a dict lookup — both scan the whole list.
Follow-ups:
- · How does the list grow when it fills up?
- · What structure gives O(1) appends at both ends?
Why does `[[]] * 3` create a bug, and how do you fix it?
Concise answer: The `*` operator repeats the SAME inner-list reference three times, so mutating one row mutates all of them. Fix it with a comprehension: [[] for _ in range(3)].
Detailed answer: Sequence repetition copies references, not objects, so all three slots alias one inner list. A comprehension evaluates [] afresh each iteration, producing distinct lists. The same aliasing idea explains shallow vs deep copy: lst[:] duplicates only the outer list, while copy.deepcopy duplicates nested objects too.
Common mistake: 'Fixing' it with a shallow copy of the outer list, which still shares the inner lists.
Follow-ups:
- · What is the difference between a shallow and a deep copy?
Knowledge check
What does this print?
a = [[]] * 2
a[0].append(1)
print(a)Which list operation is O(n)?
What does this print?
t = (1, [2, 3])
t[1].append(4)
print(t)Score: 0/3