Data Structures

Python ships four built-in containers that cover almost every need: list, tuple, dict, and set. Knowing which to pick, and how each behaves when copied or mutated, is most of what “knowing Python data structures” means.

list

A mutable, ordered sequence backed by a dynamic array of pointers. It can hold mixed types, though homogeneous lists are the norm.

nums = [3, 1, 4, 1, 5]
nums[0]        # => 3
nums[-1]       # => 5
len(nums)      # => 5

Methods

xs = [1, 2, 3]

xs.append(4)          # [1, 2, 3, 4]        — add one item, O(1) amortised
xs.extend([5, 6])     # [1, 2, 3, 4, 5, 6]  — add every item of an iterable
xs.insert(0, 0)       # [0, 1, ...]         — O(n), shifts everything right
xs.pop()              # removes and returns the LAST item, O(1)
xs.pop(0)             # removes and returns index 0, O(n)
xs.remove(3)          # removes the FIRST item equal to 3; ValueError if absent
xs.index(4)           # first index of 4; ValueError if absent
xs.count(1)           # how many times 1 appears
xs.reverse()          # in place, returns None
xs.sort()             # in place, returns None
xs.clear()            # empty it
xs.copy()             # shallow copy — same as xs[:]

Caution

append adds a single element; extend adds each element of an iterable. xs.append([1,2]) gives [..., [1, 2]], xs.extend([1,2]) gives [..., 1, 2]. And extend("ab") adds 'a' and 'b', because a string is an iterable of characters.

Caution

Mutating methods return None. xs = xs.sort() throws away your list. Use sorted(xs) when you want a value back.

Slicing, including assignment

Slices read as covered in types and variables, but on lists they are also assignable and deletable.

xs = [0, 1, 2, 3, 4, 5]
xs[1:3]             # => [1, 2]        a NEW list (shallow copy of that region)
xs[1:3] = ["a"]     # => [0, 'a', 3, 4, 5]   — replacement may change length
del xs[::2]         # delete every other element
xs[:] = [9, 9]      # replace CONTENTS in place — all aliases see the change

The last line matters: xs = [9, 9] rebinds the name, xs[:] = [9, 9] mutates the object other references share.

Sorting

list.sort() sorts in place; sorted(iterable) returns a new list and works on anything iterable. Both accept key and reverse, and both are stable — equal elements keep their relative order.

words = ["banana", "Kiwi", "apple"]

sorted(words)                        # => ['Kiwi', 'apple', 'banana']  — capitals sort first
sorted(words, key=str.lower)         # => ['apple', 'banana', 'Kiwi']
sorted(words, key=len)               # => ['Kiwi', 'apple', 'banana']
sorted(words, reverse=True)

people = [{"name": "Ada", "age": 36}, {"name": "Linus", "age": 28}]
sorted(people, key=lambda p: p["age"])

from operator import itemgetter, attrgetter
sorted(people, key=itemgetter("age"))     # faster and clearer than a lambda
sorted(objs, key=attrgetter("created_at"))

Multi-key sorting: return a tuple. Tuples compare element by element.

sorted(people, key=lambda p: (p["age"], p["name"]))          # age asc, then name asc
sorted(people, key=lambda p: (-p["age"], p["name"]))         # age DESC, then name asc

Tip

For a descending sort on a non-numeric key you cannot negate, exploit stability: sort by the secondary key first, then by the primary with reverse=True.

tuple

An immutable sequence. Same indexing and slicing as a list, no mutating methods.

point = (3, 4)
point[0]         # => 3
point[0] = 9     # TypeError

()               # empty tuple
(1,)             # ONE-element tuple — the comma makes it, not the parens
(1)              # just the integer 1

Parentheses are usually optional; the comma is what creates a tuple:

t = 1, 2, 3      # => (1, 2, 3)

Why tuples exist

• Immutability as a contract. A tuple signals “this is a fixed record”, not a growable collection.
• Hashability. A tuple of hashable items is hashable, so it can be a dict key or set member. A list cannot.
• Packing and unpacking. Multiple return values are just tuples.

counts = {}
counts[(2024, "Q1")] = 10          # composite key

def min_max(xs):
    return min(xs), max(xs)        # returns a tuple

lo, hi = min_max([3, 1, 4])

Caution

“Immutable” means the tuple’s bindings cannot change; the objects inside can still be mutable. t = ([1], [2]); t[0].append(9) works fine — and such a tuple is not hashable.

namedtuple and NamedTuple

When a tuple’s positions have meaning, name them. collections.namedtuple builds a tuple subclass with attribute access.

from collections import namedtuple

Point = namedtuple("Point", ["x", "y"])
p = Point(3, 4)
p.x            # => 3
p[0]           # => 3   — still a tuple
x, y = p       # still unpacks
p._replace(x=10)     # => Point(x=10, y=4) — a new instance
p._asdict()          # => {'x': 3, 'y': 4}

The typed version reads better in modern code:

from typing import NamedTuple

class Point(NamedTuple):
    x: int
    y: int = 0        # defaults allowed, trailing only

Use a NamedTuple when you want a lightweight immutable record that still behaves as a tuple; use a dataclass when you want a mutable object with methods.

dict

A mapping from hashable keys to arbitrary values, implemented as a hash table. Lookup, insert, and delete are O(1) on average.

user = {"name": "Ada", "age": 36}
user["name"]              # => 'Ada'
user["email"]             # KeyError
user["email"] = "a@b.c"   # insert or overwrite
del user["age"]
"name" in user            # => True — membership tests KEYS
len(user)

Ordering

Since Python 3.7 dicts preserve insertion order as a language guarantee (CPython 3.6 had it as an implementation detail). Iteration, keys(), values(), and repr all follow insertion order. Re-assigning an existing key does not move it; deleting and re-inserting does.

collections.OrderedDict is now needed only for its extras: move_to_end(), popitem(last=False), and order-sensitive ==.

Methods

d = {"a": 1, "b": 2}

d.get("z")                # => None    — no KeyError
d.get("z", 0)             # => 0       — with a default
d.setdefault("c", [])     # returns d['c'], inserting [] first if missing
d.pop("a")                # remove and return; optional default
d.popitem()               # remove and return the LAST (key, value) pair
d.update({"c": 3})        # merge another mapping (or kwargs, or pairs)
d.keys(), d.values(), d.items()    # dynamic views, not lists
dict.fromkeys(["a", "b"], 0)       # => {'a': 0, 'b': 0}

Merging, 3.9+:

merged = {"a": 1} | {"b": 2}      # => {'a': 1, 'b': 2}
d |= {"c": 3}                      # in-place merge
{**a, **b}                          # works on all versions

Danger

dict.fromkeys(["a", "b"], []) gives every key the same list object. Mutating one mutates all. Build with a comprehension instead: {k: [] for k in keys}.

Views are live windows onto the dict, and key views support set operations:

d = {"a": 1}
ks = d.keys()
d["b"] = 2
list(ks)              # => ['a', 'b']  — the view updated
d.keys() & {"a", "z"} # => {'a'}       — set intersection on keys

Iteration

for key in d: ...                 # keys, by default
for key, value in d.items(): ...  # the idiomatic form
for value in d.values(): ...

Caution

Never add or remove keys while iterating — RuntimeError: dictionary changed size during iteration. Iterate a snapshot: for k in list(d): ....

Keys must be hashable

A key must implement __hash__ and __eq__, and its hash must not change over its lifetime. All immutable built-ins qualify; lists, dicts, and sets do not.

{[1, 2]: "x"}      # TypeError: unhashable type: 'list'
{(1, 2): "x"}      # fine

set and frozenset

An unordered collection of unique, hashable elements. Membership testing is O(1), against O(n) for a list.

s = {1, 2, 3}
empty = set()      # {} is an empty DICT, not a set
s.add(4)
s.discard(9)       # no error if absent
s.remove(9)        # KeyError if absent
s.pop()            # removes an arbitrary element
3 in s             # => True

Set algebra, with operator and method forms:

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

a | b    # a.union(b)                => {1, 2, 3, 4}
a & b    # a.intersection(b)         => {3}
a - b    # a.difference(b)           => {1, 2}
a ^ b    # a.symmetric_difference(b) => {1, 2, 4}

a <= b   # a.issubset(b)
a >= b   # a.issuperset(b)
a.isdisjoint(b)

The method forms accept any iterable; the operator forms require both sides to be sets.

{1, 2}.union([2, 3])   # => {1, 2, 3}
{1, 2} | [2, 3]        # TypeError

A common use is deduplication, at the price of losing order:

list(set(items))                 # unique, order lost
list(dict.fromkeys(items))       # unique, ORDER PRESERVED

frozenset is the immutable, hashable version — usable as a dict key or inside another set.

regions = {frozenset({"eu", "uk"}): "europe"}

Comprehensions

A comprehension builds a container from an iterable in one expression. It is faster than the equivalent append loop and, when short, easier to read.

# list
squares = [n * n for n in range(10)]
evens   = [n for n in range(20) if n % 2 == 0]
pairs   = [(x, y) for x in "ab" for y in (1, 2)]   # nested loops, outer first

# dict
lengths = {w: len(w) for w in words}
inverted = {v: k for k, v in d.items()}

# set
initials = {name[0] for name in names}

# generator expression — lazy, no brackets needed as a sole argument
total = sum(n * n for n in range(1_000_000))

The if filters; a conditional expression goes before the for when you want to transform rather than filter:

[n if n > 0 else 0 for n in nums]          # transform every element
[n for n in nums if n > 0]                 # keep only some

The generator version allocates nothing:

sum([n * n for n in range(10_000_000)])    # builds a 10M-element list first
sum(n * n for n in range(10_000_000))      # constant memory

Tip

Comprehensions have their own scope, so the loop variable does not leak — unlike a for statement, where it persists afterwards. [x for x in range(3)] leaves no x behind.

Caution

If a comprehension needs more than two clauses, or a comment to explain it, write a loop. Readability is the entire point.

Python 3.12 (PEP 709) inlines list, dict, and set comprehensions rather than creating a hidden function, making them noticeably faster. Behaviour is unchanged.

Choosing the right structure

Need	Use	Why
Ordered, growable sequence	list	Append/pop at end O(1)
Fixed record, or a dict key	tuple	Immutable, hashable
Named fixed record	NamedTuple	Self-documenting, still a tuple
Key → value lookup	dict	O(1) average lookup
Uniqueness / fast membership	set	O(1) in
Immutable set	frozenset	Hashable
Queue / deque, appends at both ends	collections.deque	O(1) appendleft/popleft
Counting occurrences	collections.Counter	Built-in tallying
Default value per missing key	collections.defaultdict	No setdefault boilerplate

Complexity cheat sheet:

Operation	list	dict	set
x in c	O(n)	O(1) avg	O(1) avg
index / key lookup	O(1)	O(1) avg	—
append / add	O(1) amortised	O(1) avg	O(1) avg
insert / delete at front	O(n)	—	—

Caution

item in some_list scans the whole list. If you test membership inside a loop over n items, you have written an O(n²) algorithm. Convert the haystack to a set first.

Shallow vs deep copy

Assignment does not copy. A shallow copy makes a new outer container holding the same inner objects. A deep copy recursively copies everything.

original = [[1, 2], [3, 4]]

alias   = original                 # not a copy at all
shallow = original.copy()          # also list(original) or original[:]

shallow[0].append(99)
original      # => [[1, 2, 99], [3, 4]]   — inner list is shared!

import copy
deep = copy.deepcopy(original)
deep[0].append(99)
original      # unchanged

Shallow-copy recipes: list(x), x[:], x.copy(), dict(d), set(s), copy.copy(obj).

Use deepcopy when the structure is nested and you must isolate it fully. Be aware it is slow, it follows __deepcopy__ if defined, and it handles cycles correctly (it memoises objects it has already copied). It cannot copy things like open sockets or file handles.

Tip

The best defence against copy bugs is not copying at all: prefer immutable values and functions that return new objects instead of mutating their arguments.

Key points

• Lists mutate in place and their mutating methods return None.
• sort()/sorted() are stable and take key; tuple keys give multi-level sorts.
• A tuple is defined by the comma, is hashable, and makes a good record or dict key.
• Dicts preserve insertion order since 3.7; use get/setdefault to avoid KeyError.
• Sets give O(1) membership; dict.fromkeys dedupes while keeping order.
• Comprehensions build containers in one expression; generator expressions do it lazily.
• Copies are shallow unless you ask for copy.deepcopy.