The Container Model Behind Python's Data Structures

Every page in this section covers a specific container - lists, dicts, sets, collections, heapq - but they all sit on top of the same small set of underlying implementation strategies.

Python's built-in containers split cleanly into two families: array-backed sequences (list, tuple) and hash-table-backed collections (dict, set), and almost every performance question about a container reduces to which family it belongs to.

This page explains that split, the shared protocols collections.abc names on top of it, and why the "right" container is really a question about implementation, not just syntax.

Choosing the Right Data Structure turns this into a decision checklist; this page explains the mechanics that checklist is quietly relying on.

Summary

• Python's built-in containers are implemented as either contiguous arrays (list, tuple) or hash tables (dict, set), and that implementation choice - not the container's name - determines its performance characteristics.
• Insight: Knowing which family a container belongs to lets you predict its Big-O behavior and memory shape without memorizing a table for every type.
• Key Concepts: array-backed sequence, hash table, amortized cost, protocol (Iterable, Sized, Sequence, Mapping), hashability.
• When to Use: Reasoning about why list insertion at the front is slow but dict lookup by key is fast, or deciding whether a custom object can safely be a dict key or set member.
• Limitations/Trade-offs: Hash tables trade memory overhead and unordered internal layout for near-constant-time lookup; arrays trade slower insertion/removal in the middle for compact, cache-friendly storage and fast indexing.
• Related Topics: algorithmic complexity, hashing and equality, memory layout, the iterator protocol.

Foundations

A list in CPython is backed by a resizable array of pointers to objects, stored contiguously in memory - indexing my_list[i] is a direct pointer-arithmetic lookup, which is why it's O(1) regardless of list size.

A tuple uses the same contiguous-array layout as a list, but its size is fixed at creation, so CPython can skip the extra bookkeeping a resizable structure needs - this is part of why tuples are slightly lighter-weight than equivalent lists.

A dict and a set are both backed by a hash table: each key (or set element) is run through a hash function, and that hash determines roughly where in an internal array the entry lives, which is what makes membership tests and key lookups close to O(1) on average rather than scanning every element.

The simplest analogy is a library: a list is a numbered shelf where item #12 is always twelve steps from the start, while a dict is a card catalog where you compute a code from the title and jump almost straight to the right drawer instead of walking the whole shelf.

collections.abc names the shared behaviors these concrete types provide - Iterable (supports for), Sized (supports len()), Container (supports in), Sequence (ordered, indexable), and Mapping (key-to-value lookup) - so that code can depend on "something Sequence-shaped" instead of hard-coding list.

Mechanics & Interactions

A list's O(1) append is only true on amortized terms: CPython over-allocates extra capacity when it grows a list, so most appends just write into already-reserved space, and only occasionally does a full reallocation-and-copy happen - averaged over many appends, the cost per append works out to constant time.

import sys
nums = []
sizes = set()
for i in range(20):
    nums.append(i)
    sizes.add(sys.getsizeof(nums))
print(len(sizes))  # far fewer than 20 - capacity jumps in chunks, not one at a time

Inserting or removing at the front of a list is the opposite story: every element after the insertion point has to physically shift over in memory, making list.insert(0, x) or list.pop(0) O(n) - this is precisely why collections.deque exists, backed by a doubly linked list of fixed-size blocks so both ends are O(1).

A dict's near-O(1) lookup depends on a good hash function spreading keys evenly across its internal array; a poor hash distribution (or, adversarially, hash collisions) degrades toward the table's collision-resolution cost, which is part of why only hashable objects (those with a stable __hash__ and __eq__) are valid dict keys or set members.

Since Python 3.7, dict insertion order is a guaranteed language feature, not an accidental implementation detail - CPython's compact dict layout (introduced in 3.6) keeps a separate insertion-ordered array of entries alongside the hash-indexed lookup table, so iteration order and O(1) lookup coexist rather than trading off against each other.

Sets deliberately do not preserve insertion order the way dicts do, because a set only needs the hash table half of that design - there's no parallel ordered-entries array backing it, so relying on set iteration order is relying on an implementation detail rather than a guarantee.

Advanced Considerations & Applications

Choosing a container at scale is really choosing an implementation strategy, and the trade-offs compound as data grows: a list scan for membership is O(n) per check, so testing membership against a large list repeatedly in a loop is a common accidental O(n^2), fixed by converting to a set once up front.

array.array and memoryview sit outside the list/dict split entirely - they store raw, homogeneously-typed values (all int, all float, and so on) instead of pointers to arbitrary Python objects, trading Python's per-element flexibility for a much smaller memory footprint, which matters once you're holding millions of numeric values.

heapq doesn't introduce a new physical layout either - it's a set of functions that maintain the heap invariant on top of an ordinary list, giving O(log n) push/pop for a priority queue without a dedicated heap type.

The practical upshot for reaching for collections (namedtuples, Counter, defaultdict, OrderedDict) is that none of them invent new storage strategies - Counter is a dict subclass, defaultdict is a dict with a factory hook, and namedtuple generates a tuple subclass with named field access - they layer ergonomics on the same two underlying engines rather than adding a third one.

Common Misconceptions

• "Tuples are just immutable lists with identical performance." They share the array layout, but a tuple's fixed size lets CPython skip resize bookkeeping, and small literal tuples of constants may even be cached/interned in ways lists never are.
• "Checking x in container costs the same for a list and a set." For a list it's O(n) (a linear scan); for a set or dict it's O(1) on average (a hash lookup) - the difference only grows more important as the container gets larger.
• "A set preserves insertion order like a dict does since 3.7." Only dict gained that guarantee; set iteration order is still unspecified and can appear to change between elements or Python versions.
• "Any object can be a dict key or set member." Only hashable objects qualify - mutable containers like list and plain dict are explicitly unhashable because their contents (and thus their hash) could change after insertion.
• "heapq is a special heap data type." It's a module of functions operating on a plain list, maintaining heap ordering through those function calls rather than through a distinct underlying structure.

FAQs

Related

• Choosing the Right Data Structure - a decision checklist built on the mechanics covered here
• Lists & Tuples - the array-backed sequence family in practice
• Dictionaries - the hash-table-backed mapping type up close
• Sets & Frozensets - the other hash-table-backed container
• Immutability & Hashability - what qualifies an object as a dict key or set member
• Collections Module - ergonomic layers built on these two engines

Stack versions: This page was written for Python 3.14 (stable) and Python 3.13 (maintenance), referencing the compact dict layout (3.6+) and guaranteed dict insertion ordering (3.7+).