Lists and Tuples: Slicing, Mutation, and the Cost of Every Method

What a list actually is

CPython implements list as a contiguous array of pointers to objects, plus a length and a capacity. Elements are not stored inline, so a list can hold objects of different types and any element can be any size. When the array fills up, CPython allocates a larger one — with geometric over-allocation, so append is \(O(1)\) amortised, not \(O(1)\) in the worst case.

Everything else follows. Indexing is pointer arithmetic, so it is constant time. Inserting or deleting at position i must shift the \(n - i\) pointers after it, so it is \(O(n - i)\) — free at the end, expensive at the front. Searching has no index to exploit, so x in xs is \(O(n)\).

Indexing and slicing

Indices start at 0. Negative indices count back from the end, with -1 the last element.

xs = ["a", "b", "c", "d", "e"]
print(xs[0], xs[-1], xs[-2])   # -> a e d

A slice xs[start:stop:step] returns a new list containing start up to but not including stop. Every part is optional.

print(xs[1:4])    # -> ['b', 'c', 'd']
print(xs[:3])     # -> ['a', 'b', 'c']
print(xs[3:])     # -> ['d', 'e']
print(xs[::2])    # -> ['a', 'c', 'e']
print(xs[::-1])   # -> ['e', 'd', 'c', 'b', 'a']
print(xs[1:5:2])  # -> ['b', 'd']

Two idioms worth memorising: xs[:] is a shallow copy, and xs[::-1] is a reversed copy. Both are \(O(n)\) in time and space.

Slices never raise IndexError — out-of-range bounds are clamped, so xs[10:20] gives [] while xs[10] raises. That leniency is convenient and occasionally hides a bug.

Slices are also assignable, which lets you splice in place:

ys = [1, 2, 3, 4, 5]
ys[1:3] = ["x", "y", "z"]     # replacement need not be the same length
print(ys)                     # -> [1, 'x', 'y', 'z', 4, 5]
del ys[0:2]
print(ys)                     # -> ['y', 'z', 4, 5]

Every method, and what it costs

In one runnable sequence:

ys = [3, 1, 2]
ys.append(4)          # [3, 1, 2, 4]
ys.extend([5, 6])     # [3, 1, 2, 4, 5, 6]
ys.insert(1, 99)      # [3, 99, 1, 2, 4, 5, 6]
ys.remove(99)         # [3, 1, 2, 4, 5, 6]
print(ys.pop())       # -> 6      ys is now [3, 1, 2, 4, 5]
print(ys.pop(0))      # -> 3      ys is now [1, 2, 4, 5]
ys.reverse()          # [5, 4, 2, 1]
ys.sort()             # [1, 2, 4, 5]
print(ys.index(4), ys.count(2))   # -> 2 1
ys.clear()
print(ys)             # -> []

Note the asymmetry between append/extend: xs.append([1, 2]) adds one element that happens to be a list, while xs.extend([1, 2]) adds two. And if you find yourself calling insert(0, v) or pop(0) in a loop, you want collections.deque, which does both ends in \(O(1)\).

grid = [[0] * 3] * 3
grid[0][0] = 1
print(grid)   # -> [[1, 0, 0], [1, 0, 0], [1, 0, 0]]

grid = [[0] * 3 for _ in range(3)]
grid[0][0] = 1
print(grid)   # -> [[1, 0, 0], [0, 0, 0], [0, 0, 0]]

sort against sorted, and the key argument

xs.sort() sorts the list in place and returns None. sorted(iterable) leaves its input alone, accepts any iterable, and returns a new list. Both use Timsort, which is \(O(n \log n)\) worst case and close to \(O(n)\) on data that is already partially ordered.

words = ["banana", "kiwi", "apple", "fig"]
print(sorted(words))                     # -> ['apple', 'banana', 'fig', 'kiwi']
print(words.sort())                      # -> None      <- the trap
print(words)                             # -> ['apple', 'banana', 'fig', 'kiwi']

x = xs.sort() is one of the most common beginner bugs; it silently binds None.

key takes a function applied to each element, whose result is compared instead of the element. It is called exactly once per element, so it is cheap even when the function is not.

words = ["banana", "kiwi", "apple", "fig"]
print(sorted(words, key=len))                 # -> ['fig', 'kiwi', 'apple', 'banana']
print(sorted(words, key=len, reverse=True))   # -> ['banana', 'apple', 'kiwi', 'fig']

Return a tuple from key to sort by several fields at once. Timsort is stable — equal keys keep their original relative order — so descending by score then ascending by name is one call:

pairs = [("bob", 3), ("ann", 5), ("cid", 3)]
print(sorted(pairs, key=lambda p: (-p[1], p[0])))
# -> [('ann', 5), ('bob', 3), ('cid', 3)]

The -p[1] trick only works for numbers; for a descending string field, sort twice and let stability do the work, or use functools.cmp_to_key.

Tuples

A tuple is an immutable sequence. It supports indexing, slicing, in, len, count and index — everything a list does except the mutating half of the API.

t = (1, 2, 3)
t[0] = 9
# TypeError: 'tuple' object does not support item assignment

The commas make the tuple, not the parentheses, which produces the notorious one-element case:

print(type(("x",)).__name__)   # -> tuple
print(type(("x")).__name__)    # -> str    just a parenthesised string

A trailing comma is required for a singleton. The empty tuple is ().

Unpacking works on any iterable and is the reason tuples appear everywhere:

a, b, c = (1, 2, 3)
print(a, b, c)        # -> 1 2 3

a, b = b, a           # swap, no temporary needed

Starred unpacking (PEP 3132) absorbs a variable number of items into a list. Exactly one star is allowed:

first, *rest = [1, 2, 3, 4]
print(first, rest)      # -> 1 [2, 3, 4]

*init, last = [1, 2, 3, 4]
print(init, last)       # -> [1, 2, 3] 4

a, *mid, z = [1, 2, 3, 4, 5]
print(a, mid, z)        # -> 1 [2, 3, 4] 5

When the immutability matters

Tuples are hashable when their contents are, so they can be dictionary keys and set members — a list cannot:

d = {(0, 0): "origin"}
print(d[(0, 0)])      # -> origin

{[0, 0]: "x"}
# TypeError: unhashable type: 'list'

That is the main practical reason to reach for a tuple: coordinates, (row, col) cells, (year, month) buckets, memoisation keys. Multiple return values are also tuples — return x, y builds one, and the caller unpacks it. Beyond that, a tuple documents that a collection is a fixed record of heterogeneous fields rather than a homogeneous sequence you will iterate over. When the fields deserve names, collections.namedtuple or typing.NamedTuple gives you a tuple with attribute access at no extra memory cost.

Next up: dicts and sets, where hashing buys back the \(O(1)\) membership test that lists cannot offer.

References

1. Python Software Foundation. Data Structures: more on lists.
2. Python Software Foundation. Sequence Types — list, tuple, range.
3. Python Software Foundation. Sorting Techniques (the HOWTO).
4. Python Wiki. TimeComplexity — costs of the built-in container operations.
5. Hettinger, R. PEP 3132 — Extended Iterable Unpacking.
6. Peters, T. listsort.txt — the design notes for Timsort.