09 - Python for Data 2: Lists, Tuples, Dictionaries, Sets

A list is not right for everything. Looking for a number in a list of 100,000 elements means comparing it, in the worst case, with all of them; in a set it means computing an address and looking there. Further down, a listing measures the difference. First it helps to understand how Python's four structures are built (list, tuple, dict, set), what "mutable" means and which bugs come from this distinction. This is the second lesson of the "Python for data" module of the Machine Learning Engineer course; all you need is Python 3 and the standard library (collections, copy, timeit), with nothing to install.

The four structures, their analogy, their use

When NOT to use them. A list as a "database" to query many times by value (use dict or set); a dict where positional order matters and the keys are 0, 1, 2… (use a list); a set when you need order or duplicates.

Installation

Standard library only: collections, copy, timeit. Nothing to install.

First example: list, tuple, slicing

l = [10, 20, 30, 40, 50]
print(l[0], l[-1], l[1:3], l[::-1], l[::2])

t = (1, 2, 3)
try:
    t[0] = 9
except TypeError as e:
    print("TypeError:", e)

Output: 10 50 [20, 30] [50, 40, 30, 20, 10] [10, 30, 50], then TypeError: 'tuple' object does not support item assignment.

Slicing l[start:stop:step] includes the start and excludes the stop. Reason for the "excluded stop": l[:k] + l[k:] == l for every k, and l[a:b] has exactly b − a elements. It is a convention that avoids "one too many, one too few" errors (the same one as range). Negative indices count from the end; a negative step runs backwards.

Why do tuples exist, if they are lists that cannot be modified? For three reasons: (1) they communicate intent ("this record does not change"); (2) they can be used as dictionary keys or set elements, because they are hashable (see the hash table section); (3) they take less memory: on CPython 3.14.4 sys.getsizeof((1, 2, 3)) gives 72 bytes against the 88 of sys.getsizeof([1, 2, 3]) (the author's measurement, it changes between versions).

Theory: mutable versus immutable

Analogy. A list is a blackboard: you can erase and rewrite, and anyone looking at it sees the change. A tuple is a photograph: it can show things, it cannot change.

The definition is about the behaviour of the object: an object is mutable if its value can change while remaining the same object (the same identity). Mutable: list, dict, set. Immutable: int, float, str, tuple, frozenset, bool, None.

Trap 1: the matrix with identical rows

righe = [[0] * 3] * 3          # WRONG: three references to the same list
righe[0][0] = 1
print(righe)

ok = [[0] * 3 for _ in range(3)]   # RIGHT: three distinct lists
ok[0][0] = 1
print(ok)

Output: [[1, 0, 0], [1, 0, 0], [1, 0, 0]] versus [[1, 0, 0], [0, 0, 0], [0, 0, 0]].

[0] * 3 creates a new list; then * 3 repeats the same list object three times (it does not copy it). The three rows are a single object. The comprehension evaluates [0] * 3 on every pass, creating three lists.

Trap 2: shallow and deep copy

import copy

x = [1, [2, 3]]
superficiale = list(x)             # copies the container, NOT the inner objects
profonda = copy.deepcopy(x)        # copies everything recursively
x[1].append(99)
print(superficiale, profonda)

Output: [1, [2, 3, 99]] [1, [2, 3]]. The shallow copy shares the inner list [2, 3] with the original. With nested structures (lists of lists, dictionaries of lists) use copy.deepcopy, or rebuild with a comprehension.

Trap 2 bis: modifying a list while iterating over it

Another trap tied to mutability: removing elements from a list while you iterate over it with a loop. The iterator keeps a numeric position; if you remove an element, the following ones shift by one position and the loop skips one.

numeri = [2, 4, 6, 8, 1]
for n in numeri:
    if n % 2 == 0:
        numeri.remove(n)
print("modifying during the loop:", numeri)

numeri = [2, 4, 6, 8, 1]
dispari = [n for n in numeri if n % 2 != 0]
print("building a new list      :", dispari)

Output obtained:

modifying during the loop: [4, 8, 1]
building a new list      : [1]

How to read the code. In the first loop, when the 2 is removed (position 0), the 4 slides into position 0, but the iterator moves on to position 1, which now holds the 6: the 4 is skipped and stays in the list. At the end [4, 8, 1] remain, a wrong result without any error message. The second way builds a new list by filtering: it is correct, readable and usually faster. The rule: do not modify a collection while you iterate over it; build a new collection, or iterate over a copy.

Trap 3: the mutable default argument

def aggiungi(v, lst=[]):           # BUG: the default is created ONCE, at definition time
    lst.append(v)
    return lst

print(aggiungi(1), aggiungi(2))    # [1, 2] [1, 2]

def aggiungi_ok(v, lst=None):
    lst = [] if lst is None else lst
    lst.append(v)
    return lst

print(aggiungi_ok(1), aggiungi_ok(2))   # [1] [2]

Output: [1, 2] [1, 2] versus [1] [2]. In the buggy version, both calls return the same object, the default list; print evaluates the two calls before printing, so it shows twice the list already holding both elements. Python evaluates default values only once, when the function is defined: the default [] is a single object that survives between calls. The idiomatic remedy is None as a sentinel value, with the list created inside the function.

Theory: the hash table, and why x in set is instant

The problem

You have 100,000 elements and want to know whether 99999 is among them. In a list you have to compare it with the elements one by one until you find it: on average you scan a sizeable fraction of the list, in the worst case all of it: time proportional to n, written O(n).

The analogy: the archive with labelled drawers

Imagine an archive with 1000 numbered drawers. A function (the hash function) turns every object into a number, and that number (modulo 1000) says which drawer to put it in. To look for an object you do not open all the drawers: you compute the number and go straight to the right drawer. The cost is independent of the total number of objects, as long as the drawers do not fill up too much. It is O(1) on average.

How it works, step by step

1. Compute h = hash(object), an integer.
2. Take i = h mod m, where m is the number of drawers (the size of the table).
3. Look at drawer i. If it is empty, the object is not there. If it holds an object, compare with ==. If the objects are different but have the same i (a collision), continue with a resolution strategy (Python uses open addressing with probing).
4. If the table fills beyond a threshold, it is resized (more drawers) and the elements are put back in.

The steps have a fixed order: the index comes from the hash, and only then do you look at the drawer. The two points where a real table departs from the ideal model are step 3, where collisions lengthen the road, and step 4, where resizing costs once so as not to be paid on every search. The experiment that follows measures how much each one weighs.

Let's build one: a toy hash table

The best way to understand a mechanism is to build it. Here is a minimal hash table with m drawers; each drawer is a list of (key, value) pairs, so collisions are handled simply by lengthening the list (this is called chaining). To get reproducible results we use a deterministic CRC as the hash function (zlib.crc32): the built-in hash of strings changes at every run for security reasons, and the experiment's numbers would not be repeatable.

import math
import zlib

class TabellaHash:
    def __init__(self, m=8):
        self.m = m
        self.cassetti = [[] for _ in range(m)]
        self.n = 0

    def _indice(self, chiave):
        return zlib.crc32(str(chiave).encode()) % self.m          # hash function -> bucket number

    def inserisci(self, chiave, valore):
        cassetto = self.cassetti[self._indice(chiave)]
        for i, (k, _) in enumerate(cassetto):
            if k == chiave:
                cassetto[i] = (chiave, valore)                    # key already present: overwrite
                return
        cassetto.append((chiave, valore))
        self.n += 1

    def cerca(self, chiave, default=None):
        for k, v in self.cassetti[self._indice(chiave)]:
            if k == chiave:
                return v
        return default

    def rimuovi(self, chiave):
        cassetto = self.cassetti[self._indice(chiave)]
        for i, (k, _) in enumerate(cassetto):
            if k == chiave:
                del cassetto[i]
                self.n -= 1
                return True
        return False

t = TabellaHash(m=8)
for nome, eta in (("Anna", 31), ("Luca", 25), ("Marta", 40)):
    t.inserisci(nome, eta)
print("look up Anna:", t.cerca("Anna"), "| look up Zoe:", t.cerca("Zoe", "missing"))
t.rimuovi("Luca")
print("after removing Luca ->", t.cerca("Luca", "missing"), "| items:", t.n)

# experiment: fixed m, growing n
m = 1000
print(f"{'n':>6} {'n/m':>6} {'avg chain':>10} {'max chain':>10} {'empty buckets':>14} {'expected e^-n/m':>16}")
for n in (500, 1000, 2000, 4000, 8000):
    tab = TabellaHash(m)
    for i in range(n):
        tab.inserisci(f"user-{i}", i)
    lunghezze = [len(c) for c in tab.cassetti]
    vuoti = sum(1 for x in lunghezze if x == 0) / m
    print(f"{n:>6} {n / m:>6.1f} {sum(lunghezze) / m:>10.2f} {max(lunghezze):>10} {vuoti:>14.3f} {math.exp(-n / m):>16.3f}")

Output obtained:

look up Anna: 31 | look up Zoe: missing
after removing Luca -> missing | items: 2
     n    n/m  avg chain  max chain  empty buckets  expected e^-n/m
   500    0.5       0.50          4          0.610            0.607
  1000    1.0       1.00          5          0.374            0.368
  2000    2.0       2.00          7          0.139            0.135
  4000    4.0       4.00         11          0.016            0.018
  8000    8.0       8.00         18          0.000            0.000

How to read the code. _indice turns any key into an integer (the CRC of its text) and reduces it to the number of drawers with the modulo operator: it is the hash function followed by step 2 of the procedure described above. inserisci looks at the drawer: if it finds the same key it overwrites it, otherwise it appends at the end (this is how collisions coexist). cerca and rimuovi walk only the drawer the hash points to, never the whole table: this is the heart of the efficiency. The experiment fixes 1000 drawers and inserts from 500 to 8000 elements. The load factor n/m is the average length of a chain (by construction: n elements in m drawers): with n/m = 1 every search looks at about one element on average; with n/m = 8 it looks at about eight, still very few compared with the 8000 of a scan.

The share of empty drawers follows e^{-n/m} closely, the probability that a given drawer receives none of n elements spread at random (it is the probability of zero events in a Poisson distribution, which you will meet in the probability lesson). The longest chain is however much longer than the average: an excellent hash function does not eliminate collisions, it spreads them.

Why implementations resize. If n grows and m stays fixed, the load factor grows, the chains lengthen and the search becomes linear in n again. This is why real hash tables, Python's included, enlarge m when the load exceeds a threshold set by the implementation, and re-insert the elements: the cost of this operation, spread over all the insertions, is small and the load stays bounded, so the search stays constant-time on average.

Why keys must be hashable

The hash value decides which drawer the object sits in. If the object were mutable and changed after insertion, its hash would change, and you would look for it in the wrong drawer: the object would be "lost" in the table. This is why Python requires keys (and the elements of a set) to be hashable, that is, to have a hash that does not change during the life of the object. In practice: immutables yes (with tuples hashable only if they contain hashable elements), lists no.

try:
    {[1, 2]: 1}
except TypeError as e:
    print("TypeError:", e)           # the exact text varies across Python versions

d = {(1, 2): "point"}                # a tuple can be a key
print(d[(1, 2)])

Output: a TypeError saying that the type list is not hashable, and point.

What O(n) and O(1) mean. The notation O(n) (read "order of n") says how the work grows as the size n of the data grows: linear means that doubling the data doubles the work; O(1) (constant) means that the work does not depend on n. It does not say how many seconds are needed, it says how it scales. Counting comparisons is a machine-independent way to see it:

def confronti_lista(lista, x):
    n = 0
    for e in lista:
        n += 1
        if e == x:
            break
    return n

for N in (1_000, 10_000, 100_000):
    print(f"N = {N:>7}: comparisons to find the last element in a list = {confronti_lista(list(range(N)), N - 1):>7}")

Output obtained:

N =    1000: comparisons to find the last element in a list =    1000
N =   10000: comparisons to find the last element in a list =   10000
N =  100000: comparisons to find the last element in a list =  100000

How to read the code. confronti_lista walks the list counting the comparisons made before finding x; in the worst case (the last element) they are N. Multiplying the length by ten multiplies the comparisons by ten: this is linear behaviour. With the hash table of the previous experiment, looking up an element examines a few elements on average, whatever N is, as long as the load stays bounded. This difference of scale (not of absolute speed) is what makes sets and dictionaries indispensable on large data.

Measurement: the difference between O(n) and O(1)

import timeit

N = 100_000
lista = list(range(N))
insieme = set(lista)

t_lista = timeit.timeit(lambda: (N - 1) in lista, number=200)       # worst case: the last one
t_insieme = timeit.timeit(lambda: (N - 1) in insieme, number=200)
print("the set is at least 100 times faster:", t_lista / t_insieme > 100)

Output: True. I do not print the ratio because it depends on the computer and on the Python version; on any machine the value is orders of magnitude. Run the code printing t_lista / t_insieme to see yours.

Trade-off. The set takes more memory (the table has empty slots) and costs time to build (O(n)). It pays off when you query several times; if you have to search only once, scanning the list costs less than building the set.

Code: dictionaries and sets at work

Counting with a dictionary

from collections import Counter, defaultdict

testo = "the cat and the dog and the mouse"

conteggio = {}
for parola in testo.split():
    conteggio[parola] = conteggio.get(parola, 0) + 1
print(conteggio)
print(Counter(testo.split()).most_common(2))

gruppi = defaultdict(list)           # for each length, the list of words
for p in testo.split():
    gruppi[len(p)].append(p)
print(dict(gruppi))

Output obtained (two identical runs): {'the': 3, 'cat': 1, 'and': 2, 'dog': 1, 'mouse': 1}, then [('the', 3), ('and', 2)], then {3: ['the', 'cat', 'and', 'the', 'dog', 'and', 'the'], 5: ['mouse']}. The dictionary keys follow insertion order, guaranteed by the language since version 3.7 (Built-in Types, mapping types).

• dict.get(key, default) avoids the KeyError for missing keys.
• Counter is a dictionary specialised in counting; most_common(k) returns the k most frequent.
• defaultdict(list) automatically creates the empty list at the first new key: the "group by" pattern in one line.

The three entries answer the same question, "how many times and where?", with decreasing code cost. get is the explicit version, useful to see the mechanism; Counter is the one to use when you only need to count; defaultdict is for when you must group, not just count. They are all dictionaries, so the search by key stays constant-time on average even with millions of words. Counting and grouping like this is the by-hand version of groupby, which you will meet again in the article on Pandas.

Set operations

a, b = {1, 2, 3, 4}, {3, 4, 5}
print(a | b, a & b, a - b, a ^ b)

Output: {1, 2, 3, 4, 5} {3, 4} {1, 2} {1, 2, 5} (union, intersection, difference, symmetric difference). The print order of a set is not guaranteed: do not count on it. The article Sets and logic formalises these operations as set theory and ties them to probability.

Comprehensions

A comprehension builds a collection by describing how to obtain each element, in analogy with the set-builder notation { x² | x ∈ [0,10), x even }.

testo = "the cat and the dog and the mouse"
quadrati = [x * x for x in range(10) if x % 2 == 0]
mappa = {c: ord(c) for c in "abc"}
lunghezze = {len(p) for p in testo.split()}
print(quadrati, mappa, lunghezze)

Output: [0, 4, 16, 36, 64] {'a': 97, 'b': 98, 'c': 99} {3, 5}.

When NOT to: do not nest more than two levels; if you cannot read it in one breath, write a normal loop. For large sequences used only once, a generator expression (x*x for x in ...) does not create the list in memory.

Sorting with a key

sorted(iterable, key=function) sorts without modifying the original; list.sort() modifies in place and returns None. The sort is stable: elements with the same key keep their original relative order. To sort by several criteria use a tuple as the key; the sign − reverses the order of a numeric field.

studenti = [("Anna", 28), ("Luca", 21), ("Gio", 28)]
print(sorted(studenti, key=lambda s: (-s[1], s[0])))     # grade descending, then name

Output: [('Anna', 28), ('Gio', 28), ('Luca', 21)].

Classic trap: y = lista.sort() assigns None to y. If you want a sorted copy use sorted.

The annotated solution of the mini-project: the inverted index

The inverted index is the structure underlying every search engine: instead of associating each line with its words, it associates each word with the set of lines it appears in. Answering "which lines contain all these words?" becomes the intersection of sets (for the formal treatment, Sets and logic).

from collections import Counter, defaultdict
import string

testo = """The cat sleeps on the sofa
The dog runs in the garden
The cat and the dog play in the garden
In the evening the cat sleeps"""

traduzione = str.maketrans("", "", string.punctuation)
righe = [r.lower().translate(traduzione) for r in testo.splitlines()]

frequenze = Counter(p for riga in righe for p in riga.split())
print("top 5 words:", frequenze.most_common(5))

indice = defaultdict(set)
for numero, riga in enumerate(righe):
    for parola in riga.split():
        indice[parola].add(numero)

def righe_con_tutte(indice, parole):
    insiemi = [indice.get(p, set()) for p in parole]
    return sorted(set.intersection(*insiemi)) if insiemi else []

print("lines with 'cat' and 'sleeps':", righe_con_tutte(indice, ["cat", "sleeps"]))
print("lines with 'dog' and 'garden':", righe_con_tutte(indice, ["dog", "garden"]))
print("lines with 'cat' and 'garden':", righe_con_tutte(indice, ["cat", "garden"]))
print("nonexistent word:", righe_con_tutte(indice, ["cat", "elephant"]))

Output obtained:

top 5 words: [('the', 9), ('cat', 3), ('in', 3), ('sleeps', 2), ('dog', 2)]
lines with 'cat' and 'sleeps': [0, 3]
lines with 'dog' and 'garden': [1, 2]
lines with 'cat' and 'garden': [2]
nonexistent word: []

How to read the solution. str.maketrans("", "", string.punctuation) builds a translation table that removes all punctuation marks; translate applies it. Counter(... for ... in ...) counts the words of all the lines with a nested generator expression (first the lines, then the words of each). The index is a defaultdict(set): at the first occurrence of a word it creates the empty set by itself, and add adds the line number (since it is a set, a second add of the same number creates no duplicates). righe_con_tutte takes for each word the set of line numbers (indice.get(p, set()) returns the empty set for a word never seen, avoiding the KeyError) and intersects them with set.intersection(*insiemi), where * unpacks the list into separate arguments. Each search costs one set intersection, not a scan of the text.

Choosing the structure: five questions and a table of costs

Faced with a new task, five questions are almost always enough to choose the right structure, and it pays to ask them in this order.

1. Does the order of the data matter? If so (a time series, a job queue) you need a sequence: list or tuple. If not, a set or a dictionary may be more suitable.
2. Do I search by value or by key? If the typical question is "is this element there?" or "what is the value for this key?", look up directly with set or dict. A list forces you to scan.
3. Can I have duplicates, and do I care about them? If duplicates are an error or must be ignored, a set removes them by itself. If they must be counted, you need a Counter.
4. Does the content change after creation? If a record must not change, a tuple (or a dataclass with frozen=True) guarantees it and makes it usable as a key.
5. How much data is there, and how many times do I query it? With few elements any choice is fine; with many elements and many queries, the cost per operation becomes decisive.

For the last question you need to know the typical costs. The following table gives the average order of magnitude of each operation, with n the number of elements. The rows on the list and on the deque at the ends are the ones the official tutorial describes; the membership row is the one the listings above count and measure; sorting is n · log n because it is a comparison of pairs over n elements:

Two practical readings. The first: if you remove elements from the head of a list (lista.pop(0)), each removal shifts all the others by one position: in a loop over millions of elements it becomes very slow; for queues you use collections.deque, designed to add and remove at both ends in constant time. The second: "constant on average" means that, under normal conditions, the search in a set or a dictionary does not depend on n; in the worst case (many collisions) it can degrade, but with a good hash function it is a case you do not meet in common use.

A rule of common sense. Do not optimise before measuring: if the list has a hundred elements, no choice of structure will make a perceptible difference. But knowing the table saves you from writing, out of habit, a membership test on a list inside a loop that runs millions of times: it is the classic source of programs that "work in testing and never finish in production".

Typical mistakes

Best practices

• Choose the structure from the task: sequence (list), fixed record (tuple), lookup by key (dict), membership/uniqueness (set).
• For composite keys use tuples, not concatenated strings.
• Prefer comprehensions to loops with append when they stay readable.
• Do not mutate the arguments passed to a function without stating it in the name or in the documentation.
• For records with named fields consider dataclass or NamedTuple instead of anonymous tuples.

The five rules descend from a single one: choose the structure by looking at what you will do most often with the data, not the one that comes to mind first. The cheapest to apply in review is the second: a composite key as a string ("2026-09-24|Milano") has to be split at every read, while a tuple (date, city) is already ready and comparable.

Mini-project

Given a text (of your own choosing, pasted into a string):

1. Normalise it (lowercase, remove punctuation with str.translate or a comprehension).
2. Count the frequency of each word with Counter and print the top 5.
3. Build an inverted index: a dictionary word → set of line numbers where it appears.
4. Write a function righe_con_tutte(indice, parole) that returns the lines containing all the words (set intersection).

The mini-project follows the order of a miniature search engine: clean, count, index, query. Write it first with a text of your own and only then compare it with the annotated solution above; check that the fourth function gives an empty list when one of the words does not exist, because that is the case that breaks the first versions.

Challenge

• Easy. Remove the duplicates from a list keeping the original order (hint: dict.fromkeys).
• Medium. Write a function that transposes a matrix (list of lists) with zip(*m) and explain what * does.
• Hard. Implement a toy hash table with m drawers and lists for collisions, with inserisci, cerca, rimuovi. Measure the average chain length as the number of elements varies.
• Expert. Show with an experiment that a hash table with m drawers and n elements has an average chain length of n/m (the load factor), and explain why implementations resize when it exceeds a threshold.
• Enterprise. Write a one-page style guide for your team on which structures to use for which purposes and which traps to check in code review.

The five challenges grow in ambition, not in syntax. Easy and Medium use what you have already seen; Hard rewrites the article's hash table with your own hands; Expert asks you to measure the load factor and explain it; Enterprise moves the problem from the code to the rules a team can enforce in review. If you do only one, choose Hard, because it is the one that makes you really understand dictionaries.

What you can do now

You can choose between list, tuple, dictionary and set by looking at the question you will ask of the data, and you can explain why x in set scans nothing: the hash says which drawer to look in. You recognise the three mutability traps (shared matrix rows, shallow copy, mutable default) and the iteration-with-removal one, and you know which remedy to use for each. The next step is organising the code: functions, files, exceptions and objects.

The same series also includes: 08 - Python for Data 1: Environment and Fundamentals (the previous lesson), 11 - Floating-Point Numbers: Why 0.1 + 0.2 Is Not 0.3, 14 - Visualising Data with Matplotlib, 15 - scikit-learn: Estimators, Pipelines and Validation (which refer back to this lesson).

Sources