Python data structures: lists, dictionaries, sets and tuples

Many performance and readability problems in code do not depend on the algorithm, but on a simpler choice: the wrong data structure. A list used where a set is needed can make a program painfully slow with real data; a dictionary used instead of a class can make code hard to understand. Knowing Python's basic structures well, and the cost of operations on each, is one of the most rewarding investments a programmer can make.

Lists: ordered, mutable sequences

The list is the most used structure: an ordered sequence of elements accessed by position.

tasks = ["read email", "meeting", "code review"]
tasks.append("update documentation")
first = tasks[0]

Operations have very different costs:

• access by index and appending at the end: fast, constant time (on average for append);
• inserting or removing at the start: slow, O(n), because every element must be shifted;
• membership check with in: O(n), because the list must be scanned.

The last point is the source of many slowdowns. Checking whether an element is in a list of a hundred thousand items, inside a loop, produces millions of comparisons.

Tuples: immutable sequences

A tuple is similar to a list, but cannot be changed after creation. It is used for groups of values that belong together and must not change: coordinates, a split-up date, a result row.

point = (12.5, 41.9)
latitude, longitude = point   # unpacking

Immutability has a practical advantage: tuples made of immutable values can be used as dictionary keys or set elements, lists cannot. For tuples with many fields, namedtuple or dataclasses make code more readable, because they let you write point.lat instead of point[0].

Dictionaries: access by key

A dictionary maps keys to values, and is probably Python's most powerful structure.

prices = {"coffee": 1.20, "croissant": 1.50}
prices["orange juice"] = 3.00
total = prices["coffee"] + prices.get("tea", 0)

Reading, writing and checking a key take constant time on average, regardless of the dictionary's size. Since Python 3.7, moreover, dictionaries preserve insertion order as a language guarantee.

The get method with a default value avoids a KeyError exception when a key may be missing. Keys must be immutable objects that compare reliably: strings, numbers, tuples of immutable values.

Sets: membership and uniqueness

A set contains unique elements, with no guaranteed order, and answers the question "is this element here?" in constant average time.

known_emails = {"a@example.com", "b@example.com"}
if new_email in known_emails:
    print("already registered")

Sets also offer set-theory operations, very handy for comparing collections:

course_a & course_b   # intersection: enrolled in both
course_a - course_b   # difference: only in course A

Removing duplicates from a list becomes trivial with set(items), with the caveat that the original order is lost; if you need to keep it, list(dict.fromkeys(items)) is a compact alternative.

Which one to choose

The collections module

The standard library offers specialised structures that save you from reinventing the wheel.

deque is a double-ended queue: adding and removing at the start or end costs constant time. It is the natural choice for processing queues or for keeping only the last N items, thanks to the maxlen parameter.

Counter counts occurrences in one line:

from collections import Counter
words = text.lower().split()
most_common = Counter(words).most_common(5)

defaultdict automatically creates an initial value for missing keys, removing repetitive checks when grouping data:

from collections import defaultdict
orders_by_customer = defaultdict(list)
for order in orders:
    orders_by_customer[order.customer].append(order)

A concrete example of choosing

You need to compare two lists of product codes, one from the warehouse and one from the online catalogue, each with fifty thousand entries, to find products that exist only in the warehouse. With two lists and a loop using in, the program performs a number of comparisons in the billions. By converting the catalogue into a set, each check becomes immediate and the result arrives in a fraction of a second. The code changes by one line; performance changes by orders of magnitude.

In short

• The choice of data structure affects performance and readability more than it seems.
• Lists are great for sequences, but membership checks cost O(n).
• Dictionaries and sets offer access and lookup in constant average time.
• Tuples represent fixed groups of values and can be dictionary keys.
• The collections module provides deque, Counter and defaultdict for common needs.