Data structures

Python’s built-in data structures — list, tuple, dict, set, frozenset, plus bytes and bytearray — cover the conventional needs of most programs. Beyond these, the collections module provides deque, Counter, OrderedDict, defaultdict, and namedtuple; the heapq module provides priority-queue operations on lists; the bisect module provides binary search; the array module provides packed numeric arrays. The standard library is broad enough that most non-trivial programs use only the built-ins; non-standard alternatives (NumPy arrays, pandas DataFrames) are conventional in numeric and data-science contexts.

This page covers the principal data structures, the choice among them, and the standard-library extensions.

list

A mutable, ordered, heterogeneous sequence:

xs = [1, 2, 3]
xs.append(4)
xs.insert(0, 0)
xs.pop()                  # remove and return last
xs.pop(0)                 # remove and return first

xs[0]                      # 1
xs[-1]                     # 3
xs[1:3]                    # slicing

xs + [5, 6]                # concatenation (new list)
xs * 2                     # repetition

len(xs)
3 in xs
xs.index(3)                # position; raises if absent
xs.count(2)                # number of occurrences
xs.reverse()               # in place
xs.sort()                  # in place
sorted(xs)                 # new list, sorted

list(range(10))            # [0, 1, 2, ..., 9]
list("hello")              # ['h', 'e', 'l', 'l', 'o']

Performance:

Operation	Complexity
xs[i]	O(1)
xs.append(x)	Amortised O(1)
xs.insert(0, x)	O(n)
xs.pop()	O(1)
xs.pop(0)	O(n)
xs.remove(value)	O(n)
x in xs	O(n)
xs.sort()	O(n log n)

list is the conventional default sequence; it is implemented as a dynamic array. For frequent insertion at the front, collections.deque (treated below).

tuple

An immutable ordered sequence:

t = (1, 2, 3)
t = 1, 2, 3              # parens optional in many contexts
empty = ()
single = (1,)            # trailing comma required for one-element tuple

t[0]                      # 1
t[1:]                     # (2, 3)

# Unpacking:
a, b, c = (1, 2, 3)
a, *rest = (1, 2, 3, 4)   # a=1, rest=[2, 3, 4]

Tuples are conventionally for fixed-shape records (the type’s structure is stable). The principal uses:

• Multiple return values: def divmod(a, b): return a // b, a % b.
• Dictionary keys: tuples are hashable (if their contents are).
• Heterogeneous fixed-shape data: ("alice", 30, "alice@example.com").

For named fixed-shape data, dataclass or typing.NamedTuple is preferable:

from typing import NamedTuple

class Point(NamedTuple):
    x: float
    y: float

p = Point(3.0, 4.0)
p.x                # 3.0
p.y                # 4.0
p[0]               # 3.0; also indexable

NamedTuple and dataclass admit named access; the latter is more capable.

dict

A mutable key-value mapping:

ages = {"alice": 30, "bob": 28}
ages["alice"]              # 30
ages["carol"] = 35
del ages["bob"]
ages.get("dave", 0)         # default if absent
"alice" in ages             # True

# Iteration:
for key in ages:                # iterates keys
    print(key)
for value in ages.values():
    print(value)
for key, value in ages.items():
    print(f"{key}: {value}")

# Comprehension:
squares = {n: n ** 2 for n in range(10)}

# Merging (3.9+):
merged = a | b              # b's values override a's
inplace = a | b              # same; produces a new dict
a |= b                       # in-place

# Unpacking:
combined = {**a, **b}        # equivalent for the merge

Insertion order is preserved (since Python 3.7). Keys must be hashable; values may be anything.

Performance:

Operation	Complexity
d[k]	Average O(1)
k in d	Average O(1)
d[k] = v	Average O(1)
del d[k]	Average O(1)

dict is the principal Python container; nearly every program uses it heavily.

Common patterns

# Increment a counter:
counts = {}
for word in words:
    counts[word] = counts.get(word, 0) + 1

# Conditional initialisation:
groups = {}
for item in items:
    if item.category not in groups:
        groups[item.category] = []
    groups[item.category].append(item)

# Cleaner alternatives in `collections`:
from collections import Counter, defaultdict

counts = Counter(words)                # Counter
groups = defaultdict(list)
for item in items:
    groups[item.category].append(item)

The collections module’s Counter and defaultdict (treated below) replace the patterns above with shorter, clearer equivalents.

set and frozenset

Unordered collections of unique hashable elements:

s = {1, 2, 3}
s.add(4)
s.remove(2)
2 in s                       # False

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

a <= b                        # subset
a < b                         # proper subset
a.isdisjoint(b)               # True if no overlap

# Comprehension:
unique_lengths = {len(s) for s in strings}

# Empty set (NOT {}, which is dict):
empty = set()

The frozenset is the immutable variant — admits use as a dict key or as a member of another set:

points = {frozenset({1, 2}), frozenset({3, 4})}

Both require their elements to be hashable.

bytes and bytearray

Sequences of bytes:

b = b"hello"               # bytes; immutable
b[0]                        # 104 (the byte value, an int)

ba = bytearray(b"hello")    # mutable
ba[0] = ord("H")
bytes(ba)                   # b"Hello"

# Conversion to/from str:
"hello".encode("utf-8")
b"hello".decode("utf-8")

# Construction:
bytes([1, 2, 3, 4])         # b"\x01\x02\x03\x04"
bytes(range(5))              # b"\x00\x01\x02\x03\x04"

bytes is for byte data — files, network protocols, binary formats. bytearray is the mutable variant, useful when in-place modification matters.

range

A lazy integer sequence:

r = range(10)              # 0, 1, ..., 9
r = range(1, 11)           # 1, 2, ..., 10
r = range(0, 100, 5)       # 0, 5, 10, ..., 95
r = range(10, 0, -1)       # 10, 9, ..., 1

list(r)                    # materialise as list
sum(range(1, 101))         # 5050
1 in range(10)             # True

range produces values on demand; the entire sequence is not stored. The conventional iteration source for numeric for-loops.

collections module

The standard library extends the built-ins with several specialised types:

deque

A double-ended queue with O(1) operations at both ends:

from collections import deque

dq = deque([1, 2, 3])
dq.append(4)               # right; O(1)
dq.appendleft(0)           # left; O(1)
dq.pop()                   # O(1) right
dq.popleft()               # O(1) left

dq.rotate(2)               # rotate right by 2
dq.extend([5, 6])
dq.extendleft([0, -1])     # adds in reverse order

# Bounded:
recent = deque(maxlen=10)  # keeps only the last 10

deque is the conventional choice for queues, stacks (pop is O(1) for the right; for the left, use popleft), and bounded recent-history buffers.

Counter

A dict subclass for counting hashable objects:

from collections import Counter

words = ["apple", "banana", "apple", "cherry", "apple", "banana"]
counts = Counter(words)
# Counter({'apple': 3, 'banana': 2, 'cherry': 1})

counts.most_common(2)        # [('apple', 3), ('banana', 2)]
counts["apple"]              # 3
counts["unknown"]            # 0 (no KeyError)

counts.update(["apple", "date"])     # add to counts
counts["apple"]              # 4

# Arithmetic between counters:
c1 = Counter(a=3, b=1)
c2 = Counter(a=1, b=2)
c1 + c2                      # Counter(a=4, b=3)
c1 - c2                      # Counter(a=2)
c1 & c2                      # Counter(a=1, b=1) — minimum
c1 | c2                      # Counter(a=3, b=2) — maximum

The conventional choice for “count occurrences of each”.

defaultdict

A dict that supplies a default for missing keys:

from collections import defaultdict

groups = defaultdict(list)
for item in items:
    groups[item.category].append(item)
# missing keys are created with [] on first access

string_lengths = defaultdict(int)
for s in strings:
    string_lengths[s] += 1
# missing keys default to 0

The constructor takes a factory (a callable returning the default); each missing key is created with the factory’s result.

OrderedDict

A dict that preserves insertion order. As of Python 3.7, regular dict also preserves insertion order, so OrderedDict is rarely needed. It does have one advantage: equality is order-sensitive (OrderedDict([("a", 1), ("b", 2)]) != OrderedDict([("b", 2), ("a", 1)])).

from collections import OrderedDict

od = OrderedDict()
od["a"] = 1
od["b"] = 2
od.move_to_end("a")        # move "a" to the end
od.popitem(last=False)      # pop the first item (FIFO)

namedtuple

Tuple subclass with named fields:

from collections import namedtuple

Point = namedtuple("Point", ["x", "y"])
p = Point(3, 4)
p.x                          # 3
p.y                          # 4
p[0]                         # 3 (also indexable)

p2 = p._replace(y=0)         # immutable, but produces a new tuple

namedtuple is the older form; typing.NamedTuple (with type hints) and @dataclass are conventionally preferable in modern code.

ChainMap

A view that combines multiple dicts:

from collections import ChainMap

defaults = {"color": "red", "size": 10}
overrides = {"size": 20}

config = ChainMap(overrides, defaults)
config["color"]              # "red" (from defaults)
config["size"]               # 20 (from overrides)

Lookups walk through the maps in order. The mechanism is occasionally useful for hierarchical configuration (CLI > env > defaults).

heapq

The heapq module provides priority-queue operations on lists:

import heapq

xs = [3, 1, 4, 1, 5, 9, 2, 6]
heapq.heapify(xs)            # turn into a min-heap; in place
heapq.heappush(xs, 0)         # add
smallest = heapq.heappop(xs)  # remove and return smallest

# n smallest / largest:
heapq.nsmallest(3, xs)        # [0, 1, 1]
heapq.nlargest(3, xs)         # [9, 6, 5]

# With key:
heapq.nsmallest(3, items, key=lambda x: x.priority)

The heap is a list ordered as a binary heap; heapq operations maintain the invariant. The module is the conventional Python priority-queue implementation; for thread-safe priority queues, queue.PriorityQueue.

bisect

The bisect module provides binary search on sorted sequences:

import bisect

xs = [1, 3, 5, 7, 9]
i = bisect.bisect_left(xs, 4)     # 2 (where to insert 4)
bisect.insort_left(xs, 4)          # insert in sorted order
# xs is now [1, 3, 4, 5, 7, 9]

# Find the first element >= value:
i = bisect.bisect_left(sorted_xs, value)
if i < len(sorted_xs) and sorted_xs[i] == value:
    # found

The module is the conventional Python binary-search facility.

array

Packed homogeneous numeric arrays:

import array

a = array.array("i", [1, 2, 3, 4])    # signed ints
a = array.array("d", [1.0, 2.0, 3.0])  # doubles

The array module is more memory-efficient than list for large numeric arrays. For substantial numeric work, NumPy is the conventional choice.

enum

Named enumerated constants:

from enum import Enum, auto

class Color(Enum):
    RED = auto()
    GREEN = auto()
    BLUE = auto()

c = Color.RED
c.name                       # "RED"
c.value                       # 1

for color in Color:
    print(color)

The Enum is the conventional Python idiom for closed sets of named constants. The auto() admits automatic value assignment.

For flag-style enums (bitwise combinations), IntFlag:

from enum import IntFlag

class Permission(IntFlag):
    READ = 1
    WRITE = 2
    EXECUTE = 4

p = Permission.READ | Permission.WRITE
Permission.READ in p          # True

Choice of container

The conventional decision tree:

Need	Container
Default sequence	list
Fixed-shape data	tuple (or dataclass)
Lookup by key	dict
Set membership	set
Frozen set	frozenset
Counting	Counter
Default values for missing keys	defaultdict
Both ends fast	deque
Bounded recent	deque(maxlen=N)
Priority queue	heapq
Sorted sequence with binary search	list + bisect
Numeric arrays	array (small), NumPy (large)
Named values	Enum
Combined dicts	ChainMap

The default for “I need a collection” is list for sequences, dict for keyed lookup, set for membership.

Iterator-friendly patterns

Counting occurrences

from collections import Counter

counts = Counter(words)
top_three = counts.most_common(3)

Grouping

from collections import defaultdict

groups = defaultdict(list)
for item in items:
    groups[item.category].append(item)

Or with itertools.groupby (requires sorted input):

from itertools import groupby

for category, group in groupby(sorted(items, key=lambda x: x.category),
                                 key=lambda x: x.category):
    print(category, list(group))

Building a lookup

by_id = {item.id: item for item in items}

A dict comprehension produces an id-indexed map.

Removing duplicates while preserving order

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

# Or, in modern Python (3.7+, with hashable items):
def unique(items):
    return list(dict.fromkeys(items))

The dict.fromkeys form admits “deduplicate while preserving order” in one expression.

Partitioning

def partition(predicate, items):
    yes, no = [], []
    for item in items:
        (yes if predicate(item) else no).append(item)
    return yes, no

Python does not have a built-in partition for lists; the manual implementation is straightforward.

Index of items

indexed = list(enumerate(items))   # [(0, a), (1, b), (2, c)]

A note on persistence

Python’s built-in containers are not persistent — modifications mutate the data in place. The conventional contrast is:

• Immutable: tuple, frozenset, bytes. New values are produced; the old is unchanged.
• Mutable: list, set, dict, bytearray. Operations modify in place.

For functional-style updates (build a new structure without modifying the old), the conventional Python approach is to copy:

new_dict = {**old_dict, "new_key": "new_value"}
new_list = old_list + [new_item]

For substantial persistent structures, third-party libraries (pyrsistent) provide them; the conventional Python style accepts mutation in most cases.