Collections: Lists, Dicts, Sets and Tuples — Python Primer

Python gives you four built-in ways to hold a group of values. A list will hold any of them, and for a few hundred items the choice makes no difference at all.

At a few hundred thousand it makes an enormous difference, because the four types answer different questions at different costs. The difference between them is not style. It is speed.

flowchart TB
    Q{"What do you need?"}
    Q -->|"an ordered sequence<br/>you will change"| L["<b>list</b><br/>[1, 2, 3]"]
    Q -->|"a fixed record<br/>that must not change"| T["<b>tuple</b><br/>(1, 2, 3)"]
    Q -->|"look things up<br/>by a key"| D["<b>dict</b><br/>{'a': 1}"]
    Q -->|"membership and<br/>uniqueness only"| S["<b>set</b><br/>{1, 2, 3}"]
    style L fill:#eef1fc,stroke:#2141c8
    style D fill:#eef1fc,stroke:#2141c8

Lists

An ordered, changeable sequence. Your default when order matters.

cities = ['Delhi', 'Tokyo', 'Sydney']

cities[0]          # 'Delhi'    — first
cities[-1]         # 'Sydney'     — last
cities[1:]         # ['Tokyo', 'Sydney']
len(cities)        # 3

cities.append('Paris')     # add one to the end
cities.extend(['Lagos'])     # add several
cities.insert(0, 'Toronto')   # insert at a position — slow, see below
cities.remove('Sydney')        # remove by value
last = cities.pop()          # remove and return the last
cities.sort()                # sort in place

Slicing

Slicing takes [start:stop:step] and the stop is always excluded.

nums = [0, 1, 2, 3, 4, 5]

nums[2:5]      # [2, 3, 4]    — stop is not included
nums[:3]       # [0, 1, 2]
nums[3:]       # [3, 4, 5]
nums[::2]      # [0, 2, 4]    — every second
nums[::-1]     # [5, 4, 3, 2, 1, 0]  — reversed
nums[:]        # a shallow copy of the whole list

The excluded stop feels arbitrary at first and then becomes convenient: nums[:3] and nums[3:] together give you the whole list with no overlap and no gap.

The cost of list operations

This is the part that matters for real data.

Operation	Cost	Why
`lst[i]`	Instant	Direct memory offset
`lst.append(x)`	Instant	Room is usually already reserved
`lst.pop()`	Instant	Removes from the end
`x in lst`	Grows with length	Checks every element until found
`lst.insert(0, x)`	Grows with length	Every later element shifts along
`lst.pop(0)`	Grows with length	Same shifting problem

The two you must watch are membership testing and inserting at the front. Both look innocent and both turn a fast program into a slow one as data grows:

# If ids has 100,000 entries, this checks up to 100,000 items EVERY time
for record in records:
    if record.id in ids:        # slow
        ...

# Convert once to a set. Now each check is instant.
id_set = set(ids)
for record in records:
    if record.id in id_set:     # fast
        ...

That change alone has rescued more slow scripts than any other single fix.

To picture the difference, think about what happens when Amazon checks whether you already own something before recommending it. Against a list of a few hundred million products, “is this in here” asked as a list scan would be hopeless. Asked of a set, it is instant, and it is instant whether the catalogue holds a hundred items or a hundred million. Same question, same one-line change, completely different business.

Dictionaries

Keys mapped to values. The most useful data structure in Python and the one you will reach for most.

population = {'Delhi': 33.8, 'Tokyo': 37.1, 'Sydney': 5.3}

population['Delhi']              # 33.8
population['Lagos']              # KeyError — the key does not exist
population.get('Lagos')          # None — safe
population.get('Lagos', 0)       # 0 — safe with a default

population['Lagos'] = 16.5        # add or overwrite
del population['Sydney']           # remove
'Delhi' in population            # True — checks KEYS, and is instant

Prefer .get() when a missing key is a normal possibility. Use [] when a missing key means something has gone wrong and you want the error.

Looping over a dictionary gives you the keys unless you ask otherwise:

for city in population:                    # keys
    ...
for city, pop in population.items():       # both — usually what you want
    print(f"{city}: {pop}m")
for pop in population.values():            # values only
    ...

Dictionaries keep insertion order, which has been guaranteed since Python 3.7. You can rely on it.

Two patterns worth memorising

Counting things:

from collections import Counter

cities = ['Delhi', 'Sydney', 'Delhi', 'Tokyo', 'Delhi']
counts = Counter(cities)
counts                    # Counter({'Delhi': 3, 'Sydney': 1, 'Tokyo': 1})
counts.most_common(2)     # [('Delhi', 3), ('Sydney', 1)]

Grouping things:

from collections import defaultdict

by_tier = defaultdict(list)         # missing keys create an empty list
for city, tier in [('Delhi', 1), ('Sydney', 2), ('Tokyo', 1)]:
    by_tier[tier].append(city)

dict(by_tier)     # {1: ['Delhi', 'Tokyo'], 2: ['Sydney']}

Without defaultdict that loop needs an if key not in d check every time. With it, the check disappears.

Sets

Unordered, no duplicates, and membership testing is instant regardless of size.

tiers = {'gold', 'silver', 'gold', 'bronze'}
tiers                        # {'gold', 'silver', 'bronze'} — dupes gone

'gold' in tiers              # instant, even with a million entries
tiers.add('platinum')
tiers.discard('bronze')      # remove if present, no error if absent

The set operations replace a great deal of loop-writing:

a = {1, 2, 3, 4}
b = {3, 4, 5, 6}

a | b        # {1,2,3,4,5,6}  union — in either
a & b        # {3, 4}         intersection — in both
a - b        # {1, 2}         difference — in a but not b
a ^ b        # {1,2,5,6}      symmetric difference — in exactly one

These come up constantly in data work:

expected = set(reference_ids)
actual = set(df.customer_id)

missing = expected - actual          # in reference, absent from data
unexpected = actual - expected       # in data, not in reference
print(f"{len(missing)} missing, {len(unexpected)} unexpected")

Two lines that would otherwise be a nested loop.

Note that {} creates an empty dictionary, not a set. For an empty set you need set().

Tuples

Like a list, but cannot be changed after creation.

point = (10, 20)
point[0]           # 10
point[0] = 5       # TypeError — tuples are immutable

Three reasons they exist and matter.

They signal intent. A tuple says “this is a fixed record, not a growing collection”. A coordinate, a date pair, a row of results.

They can be dictionary keys. Lists cannot, because a key must not change underneath the dictionary.

distances = {('Delhi', 'Tokyo'): 1400, ('Delhi', 'Sydney'): 1450}
distances[('Delhi', 'Sydney')]      # 1450

Functions return them. Every time a function appears to return several values, it is returning one tuple.

def min_max(values):
    return min(values), max(values)      # this is a tuple

lo, hi = min_max([3, 1, 4])              # unpacked into two names

Named tuples, when a tuple gets confusing

Once a tuple has more than about three fields, positional access becomes unreadable. record[4] tells the reader nothing.

from collections import namedtuple

City = namedtuple('City', ['name', 'population', 'tier'])
delhi = City('Delhi', 33.8, 1)

delhi.population       # 33.8 — readable
delhi[1]               # 33.8 — still works

Choosing, in Practice

You need to	Use
Keep things in order and add to them	`list`
Look something up by a name or ID	`dict`
Check “have I seen this before”	`set`
Remove duplicates	`set`
Return several values from a function	`tuple`
Use a compound value as a dictionary key	`tuple`
Count occurrences	`Counter`
Group items under keys	`defaultdict(list)`

The single most valuable habit: if you find yourself writing if x in some_list inside a loop, make it a set first. That one change is the difference between a script that finishes and one you kill after twenty minutes.

Nesting

Real data is nested, and the combination you will meet most often is a list of dictionaries, which is exactly what an API returns.

records = [
    {'city': 'Delhi', 'pop': 33.8, 'tier': 1},
    {'city': 'Sydney',  'pop': 5.3,  'tier': 2},
]

for r in records:
    print(r['city'], r['pop'])

# And this is precisely what pandas expects
import pandas as pd
df = pd.DataFrame(records)

That last line is worth remembering. A list of dictionaries with consistent keys converts straight into a DataFrame, which makes it the natural shape to collect results in.

What Carries Forward

Membership in a list is slow; in a set or dict it is instant. This is the most common cause of unexpectedly slow beginner code.

Use .get() when a missing key is normal, and [] when it is a bug you want to hear about.

Counter and defaultdict remove a great deal of boilerplate. Learn those two and a lot of loops get shorter.

A list of dictionaries is the natural shape for collected results, and converts directly into a DataFrame.

Next: control flow, and the comprehensions that replace most of the loops you would otherwise write.