Collections: lists, tuples, sets and dicts

You can represent almost anything with four containers, and choosing well is most of what separates fast code from slow code. The decision is rarely about what the data is and almost always about which operations must be cheap: order, membership, uniqueness, or lookup by key.

The explorer below stores the same additions in each container. Add duplicates and watch ordering, uniqueness and lookup cost diverge.

The four containers #

• A list [1, 2, 3] is ordered and mutable. append is amortised $O(1)$; membership and search are $O(n)$ because they scan.
• A tuple (1, 2, 3) is ordered and immutable. That immutability makes tuples usable as dictionary keys and signals "this record does not change".
• A set {1, 2, 3} is unordered and holds each element once. Membership is $O(1)$ on average because it hashes into buckets rather than scanning.
• A dict {"a": 1, "b": 2} maps unique keys to values, also with $O(1)$ average lookup. Since Python 3.7 it preserves insertion order, but that is a bonus, not the reason to use it.

Building the table #

Membership is where the difference bites. x in my_list walks the list one element at a time — $O(n)$. x in my_set hashes x, jumps to one bucket, and answers in $O(1)$ on average. Converting a list to a set before a loop of membership tests is one of the most common rewrites for speed:

seen = set()
for word in document:
    if word in seen:      # O(1), not O(n)
        continue
    seen.add(word)

Sharing, copying and mutation #

Assignment never copies a container; it binds another name to the same object.

a = [1, 2, 3]
b = a              # same object
b.append(4)        # a is now [1, 2, 3, 4] too
c = a[:]           # a shallow copy; c is independent

Because lists and dicts are mutable, passing one into a function lets that function change your data. Tuples and strings are immutable, so they cannot be changed in place — which is exactly why they are safer to share.

Where next: functions — naming a block of work, giving it inputs, and keeping its variables local.