Run it
The five containers measured rather than described: the operation each is fast at, the memory each uses for the same thousand integers, and the two errors that pick the container for you.
When to use each
list is the default. Random access, sorting, slicing, appending at the end — all good. Only reject it when you need something it cannot do.
tuple when the sequence is a fixed record rather than a collection, or when it must be hashable:
The hashability is the hard requirement — a list simply cannot be a dict key. The immutability is also a signal to the reader that the contents are not going to change, which is why returning a tuple from a function that produces a fixed set of values is idiomatic.
deque when you add or remove at the front:
maxlen is the underrated feature. A bounded deque discards from the opposite end automatically, which gives you a rolling window or a fixed-size log buffer with no bookkeeping at all.
list.pop(0) and list.insert(0, x) are O(n), because every remaining element shifts one position. Inside a loop, that makes the whole operation quadratic:
Roughly five billion element moves. Swapping in a deque makes it linear:
Any breadth-first search, task queue, or producer-consumer loop should use a deque. This is the single most common reason a straightforward-looking Python loop is slow, and it is invisible in small tests — a thousand elements finishes fine, and a hundred thousand does not.
The mirror-image mistake also exists: reaching for a deque and then indexing it in a loop. dq[i] walks the internal block list, so a positional loop over a deque is O(n²). Use a list when you index, a deque when you push and pop at the ends.
tuple versus list
The textbook answer is "tuples are immutable", which is true and not the point. The consequence is that a tuple is hashable (if its contents are), so it can be a dictionary key or a set member — which is why coordinates, database rows and cache keys are tuples.
The secondary signal is meaning. A list is a homogeneous sequence of unknown length; a tuple is a fixed-size record where position carries meaning. (x, y) is a point; [x, y] is two numbers.
deque versus list
collections.deque is a doubly linked list of blocks, so appendleft and popleft are O(1) where the list equivalents are O(n). Any queue, BFS frontier or "last N items" buffer should be a deque.
The trade is random access: d[5000] walks the blocks, so it is O(n). If you index into the middle, keep the list. A deque also takes maxlen, which turns it into a fixed-size ring buffer that discards the oldest entry automatically.
array and the memory question
A list holds references, so a list of a million integers is a million pointers plus a million integer objects. array.array packs the values inline in one typed block, which is several times smaller and much friendlier to the cache.
For real numeric work the answer is numpy, which adds vectorised operations on top of the same packed layout. Mentioning that a list of numbers is a list of pointers is usually the specific thing an interviewer is listening for.
Why tuples are smaller and faster
A list over-allocates so that append is amortised O(1), and it stores a capacity alongside its length. A tuple is fixed at creation, so it needs neither — less memory, one less indirection, and marginally faster iteration.
CPython also caches small tuples for reuse, and constant tuples are built at compile time:
So for x in (1, 2, 3) is very slightly faster than the list version. This is a real but tiny effect, and not a reason to choose a tuple — choose based on mutability and hashability, and take the memory win as a side benefit.
Immutability is shallow
A tuple's immutability applies to its own slots, not to what they point at:
The tuple guarantees its references will not change, and says nothing about the objects behind them. That is also why a tuple containing a list is unhashable: hashing recurses into the contents, so one mutable element makes the whole thing unhashable.
The practical rule: a tuple is only usable as a dict key if everything inside it is hashable too. Convert nested lists to tuples, and sets to frozenset.
The rest of the family
| Need | Use |
|---|
| Fixed record with named fields | NamedTuple or dataclass(frozen=True) |
| Queue between threads | queue.Queue — deque plus locking |
| Priority queue | heapq on a list |
| Array of numbers, compact | array.array or NumPy |
| Sorted insertion | bisect.insort on a list |
| Immutable set | frozenset |
| Ring buffer | deque(maxlen=n) |
NamedTuple is the natural upgrade once a tuple's positions acquire meaning. point.x beats point[0], it stays a tuple, and it costs no extra memory:
deque is thread-safe for append and popleft individually, because those are atomic at the C level. That does not make a check-then-pop sequence safe — use queue.Queue when several threads coordinate through it.
Questions people ask
Why is list.pop(0) slow? Every subsequent element shifts down one slot. Use deque.popleft.
Can I index a deque? Yes, and at O(n). Indexing in a loop is quadratic.
Why can a tuple not be a dict key sometimes? If it contains a mutable object, it is unhashable.
Is a tuple actually faster? Marginally, from less allocation and compile-time constants. Not a deciding factor.
What about slicing a deque? Unsupported. Use itertools.islice, or a list if slicing is central.
deque or queue.Queue for threads? Queue when threads coordinate; deque when a single owner mutates it.
Does tuple copying help? tuple(lst) snapshots the references — a shallow copy, so shared mutable elements are still shared.
Recap in one screen
list is the default; tuple when the sequence is a fixed record or must be hashable; deque when you touch both ends.list.pop(0) and insert(0, x) are O(n) and turn ordinary loops quadratic — use deque for queues and BFS.- Indexing a
deque is O(n), so do not loop over it positionally. - Tuple immutability is shallow: the slots are fixed, the objects inside may not be, and one mutable element makes it unhashable.
deque(maxlen=n) gives a rolling window for free; NamedTuple gives a tuple with named fields.