Collections

Lists: ordered and changeable

A list is an ordered sequence of items that can grow, shrink, and change in place. Write one with square brackets. Items can be any type, though in practice a list usually holds items of one kind.

groceries = ["eggs", "milk", "bread"]
empty = []
mixed = [1, "two", 3.0, None]     # legal, but usually a sign a tuple or dict fits better

Indexing and slicing work exactly as they did for strings in M03: xs[0] is the first item, xs[-1] the last, xs[1:3] a new list with items 1 and 2, xs[::-1] a reversed copy. The difference is that lists are mutable: you can assign to an index or a slice.

Methods that change a list in place, such as append, sort, and reverse, return None. This is deliberate: it reminds you that no new list was made.

How fast are list operations?

A list is stored as a contiguous array of references, with some spare capacity at the end. That design makes some operations very fast and others slow. "O(1)" means the time does not depend on the list's length; "O(n)" means it grows in proportion to the length (Part 3 makes this precise).

Watch what append really does: most appends drop into spare space, and once in a while the list allocates a bigger block and copies everything across. Averaged over many appends the cost per append stays constant.

Tuples: fixed records, packing, and unpacking

A tuple is an ordered, immutable sequence. Once created it cannot change. Use a tuple for a fixed group of related values (a record) where the position means something: a point (x, y), an RGB colour (255, 128, 0), a row ("Ada", 36, "London"). Use a list for a variable-length collection of similar things.

It is the comma that makes a tuple; the parentheses are usually optional. This is called packing. The reverse, unpacking, assigns each item to its own name.

Star-unpacking

A starred name collects "everything else" into a list. It is handy for splitting off a head or a tail.

Because they are immutable, tuples can be dictionary keys and set members (as long as everything inside is also immutable), while lists cannot. Immutability also signals intent: readers know the record will not change.

Dictionaries: look things up by key

A dict maps keys to values. Instead of asking for "item number 3", you ask for "the value stored under "Ada"". Looking up, adding, and deleting a key are all O(1) on average, no matter how big the dict grows, because dicts are hash tables: Python computes a number (the hash) from the key and uses it to jump straight to the right slot.

Keys must be hashable: strings, numbers, booleans, None, and tuples of hashable things. Lists, dicts, and sets cannot be keys. Values can be anything. Since Python 3.7, dicts remember insertion order, so iterating gives keys in the order they were added.

Iterating

for name in ages:                 # keys
for value in ages.values():       # values
for name, age in ages.items():    # (key, value) pairs: by far the most common

Counting and grouping: get and setdefault

Two patterns appear constantly. Counting uses get with a default of 0. Grouping uses setdefault, which returns the existing value for a key or inserts and returns a default.

Merging

The | operator merges two dicts into a new one; when keys clash, the right-hand side wins. |= (like update) merges in place.

Sets: uniqueness and fast membership

A set is an unordered collection of unique, hashable items. It is a dict with keys and no values. Write one with braces ({1, 2, 3}), but note that {} is an empty dict; an empty set is set().

The real superpower is speed. Checking x in some_list scans the list item by item, but x in some_set computes a hash and checks one slot. Try it:

A frozenset is an immutable set, so it is hashable and can be a dict key or a member of another set.

Comprehensions

A comprehension builds a new collection from an iterable in one expression. It reads almost like English: "the square of n, for each n in nums, if n is even".

squares = []
for n in nums:
    if n % 2 == 0:
        squares.append(n * n)

squares = [n * n for n in nums if n % 2 == 0]

There are list ([...]), set ({...}), and dict ({k: v ...}) comprehensions. Two different uses of if are easy to confuse:

• Filter at the end: [x for x in xs if x > 0] keeps only some items.
• Choose in the expression: [x if x > 0 else 0 for x in xs] keeps every item but transforms it with a conditional expression.

Nested comprehensions

Multiple for clauses run in the same order as nested loops, outermost first.

Wrapping a comprehension in parentheses instead of brackets makes a generator expression, which produces items one at a time without building a list: sum(n * n for n in range(1_000_000)). You will study these in M14.

Sorting, zip, and enumerate

sorted(iterable) returns a new sorted list from any iterable. list.sort() sorts a list in place and returns None. Both accept key= (a function that produces the value to compare) and reverse=True.

Python's sort is stable: items that compare equal keep their original order. That is why sorting by a tuple key, or sorting twice (secondary key first, then primary key), gives predictable results.

enumerate and zip

enumerate(xs, start=0) gives (index, item) pairs, so you never need range(len(xs)). zip(a, b, ...) walks several iterables in step, producing tuples, and stops at the shortest one. Pass strict=True to raise ValueError if the lengths differ, which catches bugs early.

Aliases, shallow copies, and deep copies

Recall from M02 that assignment never copies; it binds another name to the same object. With mutable collections this matters enormously.

• Alias: b = a. Two names, one object. Mutating through either is visible through both.
• Shallow copy: b = a.copy(), list(a), a[:], dict(a), copy.copy(a). A new outer container whose slots refer to the same inner objects.
• Deep copy: copy.deepcopy(a). A new outer container and, recursively, new copies of everything inside.

Step through a shallow copy. The outer lists are different objects, but they share their contents:

With nested data, a shallow copy shares the inner lists, so changing an inner list shows up in both:

A deep copy duplicates every level:

Use the tracer to confirm with object identity tags: alias shares the outer object's tag; shallow has its own outer tag but its rows share tags with board's rows.

A preview of the collections module

The standard library's collections module provides specialized containers for jobs you just did by hand. Part 3 studies the data structures behind them.

Practice

def dedupe(items):
    seen = set()
    result = []
    for item in items:
        if item not in seen:
            seen.add(item)
            result.append(item)
    return result

def word_counts(text):
    counts = {}
    for raw in text.split():
        word = raw.strip(".,!?;:\"'").lower()
        if word:
            counts[word] = counts.get(word, 0) + 1
    return counts

def invert(d):
    result = {}
    for key, value in d.items():
        result.setdefault(value, []).append(key)
    return {value: sorted(keys) for value, keys in result.items()}

def top_n(scores, n):
    ranked = sorted(scores.items(), key=lambda kv: (-kv[1], kv[0]))
    return ranked[:n]

def transpose(matrix):
    return [list(column) for column in zip(*matrix)]

import copy

def merge_settings(defaults, overrides):
    result = copy.deepcopy(defaults)
    for key, value in overrides.items():
        if isinstance(value, dict) and isinstance(result.get(key), dict):
            result[key] = merge_settings(result[key], value)
        else:
            result[key] = copy.deepcopy(value)
    return result

Mini-project: an in-memory contact book

mkdir contacts && cd contacts
pixi init
pixi add python=3.14
pixi run python contacts.py

Quiz

Recap

• Lists: ordered, mutable, cheap at the end, O(n) at the front and for searching.
• Tuples: immutable records; packing with commas, unpacking with names, *rest for the remainder.
• Dicts: O(1) average lookup by hashable key; get, setdefault, items(), |.
• Sets: unique items, O(1) membership, union/intersection/difference.
• Comprehensions build lists, sets, and dicts; trailing if filters, a if c else b chooses.
• sorted(key=..., reverse=...) is stable; use tuple keys for multi-level sorts; zip/enumerate replace index juggling.
• Assignment aliases; .copy() is shallow; copy.deepcopy copies every level.

Going further

• Python tutorial: Data structures
• Library reference: Sequence types and Mapping types
• Sorting HOW TO
• copy: shallow and deep copy operations
• collections: container datatypes
• Python wiki: Time complexity of built-in operations
• Next: M07 Errors & Exceptions