Python Data Structures: A Complete Reference

Choosing a data structure is choosing which operations will be cheap. A list is excellent at appending and terrible at checking whether it contains something; a set is the reverse. Python's standard library covers nearly every common job with a structure built for it, and most slow or convoluted code uses a general-purpose structure for a specialised job. This reference is organised by job, with the cost of the operations that matter.

The four built-ins

These four cover most code (Python tutorial: data structures). The detailed trade-offs between them, including when a tuple beats a list, are in lists vs tuples vs sets vs dictionaries. The rest of this guide covers the specialised structures in collections, heapq and bisect that the built-ins are often forced to imitate.

What operations cost

Average costs in CPython, from the Python wiki's complexity table (TimeComplexity), where n is the number of items:

Two rows explain most performance surprises. Removing from the front of a list shifts every other element, so a list used as a queue slows down as it grows. And in on a list scans every element, so checking membership inside a loop over another large list is quadratic. Switch to a deque or a set respectively.

Queues and recent history: deque

from collections import deque

jobs = deque(["resize-1", "resize-2"])
jobs.append("resize-3")          # add at the back
print(jobs.popleft(), list(jobs))   # take from the front

recent = deque(maxlen=3)         # keeps only the last three items
for page in ["home", "courses", "blog", "contact", "about"]:
    recent.append(page)
print(list(recent))

resize-1 ['resize-2', 'resize-3']
['blog', 'contact', 'about']

A double-ended queue supports fast appends and pops at both ends, and with maxlen it discards the oldest item automatically, which suits "last N events" and moving windows (Python docs: collections). The Python tutorial itself recommends deque over a list for queues.

Counting: Counter

from collections import Counter

words = "the cat sat on the mat the end".split()
counts = Counter(words)
print(counts.most_common(2))
print(counts["dog"], (Counter("aab") + Counter("abc"))["a"])

[('the', 3), ('cat', 1)]
0 3

Counter is a dictionary that counts. Missing keys read as 0 instead of raising KeyError, most_common(n) returns the top items, and counters can be added and subtracted. Ties in most_common keep the order in which items were first seen.

Grouping: defaultdict

from collections import defaultdict

orders = [("Hyderabad", 1200), ("Pune", 450), ("Hyderabad", 800)]
by_city = defaultdict(list)
for city, amount in orders:
    by_city[city].append(amount)
print(dict(by_city))

{'Hyderabad': [1200, 800], 'Pune': [450]}

A defaultdict creates a missing value with the factory you give it (list, int, set) the first time a key is used, which removes the "is the key there yet?" check from every grouping loop.

Priorities and top-k: heapq

import heapq

tasks = []
heapq.heappush(tasks, (2, "send weekly report"))
heapq.heappush(tasks, (1, "fix failed payment"))
heapq.heappush(tasks, (3, "archive logs"))
print(heapq.heappop(tasks))

sales = [420, 1800, 95, 1300, 760]
print(heapq.nlargest(2, sales), heapq.nsmallest(1, sales))

(1, 'fix failed payment')
[1800, 1300] [95]

A heap keeps its smallest item at the front, and pushing or popping costs O(log n) (Python docs: heapq). Storing (priority, task) tuples turns it into a priority queue, because tuples compare by their first element. nlargest and nsmallest find the top few items without sorting everything. If two priorities can be equal and the tasks cannot be compared, add a counter as a tie-breaker in the middle of the tuple.

Sorted lookups: bisect

import bisect

breakpoints = [40, 60, 75, 90]          # score thresholds
grades = ["F", "C", "B", "A", "A+"]
print([grades[bisect.bisect(breakpoints, s)] for s in (35, 60, 89, 97)])

prices = [99, 249, 499]
bisect.insort(prices, 300)
print(prices)

['F', 'B', 'A', 'A+']
[99, 249, 300, 499]

bisect performs binary search on a sorted list, which makes range lookups such as grade bands, tax slabs or price tiers a one-liner (Python docs: bisect). Note the score of exactly 60: it lands in the higher band, B, because bisect returns the position to the right of an equal value. If a score on the threshold should belong to the lower band, use bisect_left instead. Decide which rule your data needs and test the boundary values explicitly. The search is O(log n). insort keeps a list sorted as you add to it, but insertion still shifts elements, so for many insertions into a large collection, sort once at the end instead.

Records: namedtuple and dataclass

For a fixed group of named fields, a namedtuple gives tuple behaviour (immutable, unpackable, usable as a dictionary key) plus access by name:

from collections import namedtuple

Point = namedtuple("Point", ["lat", "lon"])
office = Point(17.385, 78.4867)
lat, lon = office
print(office.lat, office == Point(17.385, 78.4867), {office: "Hyderabad"}[office])

17.385 True Hyderabad

When records need defaults, validation, methods or mutability, a dataclass is the better fit; the object-oriented programming guide covers it. For very large numeric data, none of these is right: use NumPy arrays, which store numbers compactly and compute on whole arrays at once (NumPy guide).

Choosing quickly

Most of these appear in coding interviews for data roles, often as the difference between an O(n²) and an O(n) answer; see Python interview questions for data roles. Comprehensions, the usual way to build lists, dictionaries and sets, are covered in the list comprehensions guide.

Lists, tuples, sets, dictionaries and list comprehensions form the data structures module of the Python Programming course.

Sources

• Data Structures (tutorial) — Python documentation
• collections — Container datatypes — Python documentation
• heapq — Heap queue algorithm — Python documentation
• bisect — Array bisection algorithm — Python documentation
• TimeComplexity — Python wiki