vault

collections Data Structure Internals

15 min read

collections Data Structure Internals

The collections module provides specialized container datatypes that fill the gaps left by list, dict, tuple, and set. Several of them are not thin Python wrappers but hand-tuned C data structures whose internals are themselves CPython internals: deque is a doubly-linked list of fixed-size memory blocks (not a Python list); OrderedDict’s C implementation is a regular dict plus a separate doubly-linked list of key nodes; defaultdict is a dict subclass overriding __missing__ in C; namedtuple is a code-generated tuple subclass; and Counter and ChainMap are pure-Python compositions over dict (CPython Lib/collections/__init__.py, v3.14.5). This note traces each one to the source that implements it on CPython 3.14.5, with emphasis on the memory layouts that give them their complexity guarantees.

This is the sibling of functools and lru_cache Internals; that note covers the callable utilities, this one the containers. Both are stdlib modules whose internals are language internals.

Mental Model — The Right Layout for the Right Access Pattern

Each collections container exists because a built-in type has the wrong cost model for some access pattern. A list is a contiguous array: O(1) at the right end but O(n) to insert or pop at the left (everything shifts). deque fixes that with a block-linked list — O(1) at both ends. A plain dict remembers insertion order but cannot cheaply move a key to the end or compare order; OrderedDict adds an order list and order-sensitive equality. A tuple has no field names; namedtuple generates a subclass with named accessors at zero per-instance memory cost.

graph TD
    subgraph deque["deque: doubly-linked list of 64-slot blocks"]
        B1["block A<br/>_ _ x x x"] <--> B2["block B<br/>x x x x x"]
        B2 <--> B3["block C<br/>x x x _ _"]
        LI["leftindex →"] -.-> B1
        RI["rightindex →"] -.-> B3
    end
    subgraph odict["OrderedDict (C): dict + order list + mirror table"]
        D["regular dict<br/>(key → value)"]
        FN["od_fast_nodes[]<br/>(mirrors dict table:<br/>key slot → node*)"]
        LL["node list:<br/>first ⇄ ... ⇄ last"]
        D -.-> FN
        FN -.-> LL
    end

Figure: deque stores data in fixed 64-element blocks linked both ways, so appends/pops at either end never move other elements; only leftindex/rightindex and the end blocks change. OrderedDict (C) keeps a normal dict for value storage, a doubly-linked list of nodes for order, and a od_fast_nodes array that mirrors the dict’s hash table so any node can be located in O(1) for move_to_end/__delitem__. The insight: the cleverness is never in the algorithm but in choosing a layout whose cheap operations match the container’s purpose.

deque — A Linked List of Fixed-Size Blocks

deque (double-ended queue) is implemented entirely in C (Modules/_collectionsmodule.c). Its purpose is O(1) append and pop at both ends — something list cannot give you, because list.pop(0)/list.insert(0, v) are O(n) (they shift the whole backing array, as the docs note explicitly: lists “incur O(n) memory movement costs for pop(0) and insert(0, v)” (collections.rst:459 area)).

The block layout

The data lives in fixed-length blocks, each a small struct holding 64 object pointers plus left/right links (Modules/_collectionsmodule.c:78, :129):

#define BLOCKLEN 64
#define CENTER ((BLOCKLEN - 1) / 2)
 
typedef struct BLOCK {
    struct BLOCK *leftlink;
    PyObject *data[BLOCKLEN];   /* 64 element slots */
    struct BLOCK *rightlink;
} block;
 
struct dequeobject {
    PyObject_VAR_HEAD
    block *leftblock;
    block *rightblock;
    Py_ssize_t leftindex;     /* 0 <= leftindex < BLOCKLEN */
    Py_ssize_t rightindex;    /* 0 <= rightindex < BLOCKLEN */
    size_t state;             /* bumped on every index move; mutation guard */
    Py_ssize_t maxlen;        /* -1 means unbounded */
    Py_ssize_t numfreeblocks;
    block *freeblocks[MAXFREEBLOCKS];   /* up to 16 recycled blocks */
    PyObject *weakreflist;
};

The source comment (:82) explains the design rationale precisely: a textbook one-datum-per-node doubly-linked list has 200% pointer overhead (a prev and next per element) and one malloc per element. Packing 64 elements per block slashes the link-to-data ratio, makes consecutive elements cache-local, and crucially avoids realloc() entirely — appends never move existing data, so performance is predictable and no element’s address ever changes underneath you. The first element is at leftblock->data[leftindex], the last at rightblock->data[rightindex]; an empty deque has leftblock == rightblock, leftindex == CENTER + 1, rightindex == CENTER (so the first append in either direction lands near the block’s middle). To recycle memory, freed blocks are pushed onto a small freeblocks array (capacity MAXFREEBLOCKS == 16) rather than freed immediately (:80).

append, appendleft, and maxlen ring behavior

deque_append_lock_held (:341) shows the whole append: if the rightmost block is full (rightindex == BLOCKLEN - 1), allocate a new block, link it on, and reset rightindex = -1; then bump the size, increment rightindex, and store the item at rightblock->data[rightindex]. That is O(1) amortized — a new block is needed only once per 64 appends. appendleft is the mirror image working off leftblock/leftindex.

The maxlen parameter turns a deque into a fixed-size ring buffer: if set, after every append the macro NEEDS_TRIM(deque, maxlen) checks whether the size exceeded maxlen, and if so pops one item off the opposite end (:338, :356). So append on a full bounded deque silently drops the leftmost element. This makes deque(maxlen=N) the idiomatic “last N items” buffer (sliding windows, rolling logs). The maxlen attribute is documented as added in 3.1 (collections.rst:588).

Why middle indexing is O(n)

The price of the block-list layout is random access. deque[i] calls deque_item (:1419 → deque_item_lock_held), which special-cases i == 0 and i == len-1 as O(1) but for any middle index must walk the block chain: it computes which block ((leftindex + i) / BLOCKLEN) and which slot (% BLOCKLEN) the element lives in, then walks rightlink from the left end or leftlink from the right end, choosing whichever end is closer (if (index < Py_SIZE(deque) >> 1)). That walk is O(n/BLOCKLEN) block hops, i.e. O(n). The docs state this directly: “Indexed access is O(1) at both ends but slows to O(n) in the middle” (collections.rst). If you need fast random access, use a list; deque is for queue/stack workloads — contrast with CPython List Internals. Note also deque.insert/remove are O(n) and the state counter is bumped on every index move so that mutation-during-iteration raises RuntimeError.

OrderedDict — A Dict Plus an Order List

OrderedDict predates the language-level insertion-ordered dict (3.7) and survives because it offers order-aware semantics a plain dict does not (Dictionary Ordering Assumptions). The C implementation lives in Objects/odictobject.c, and its design doc is one of the clearest in the source tree (Objects/odictobject.c:1).

The three-part structure

An OrderedDict is a dict (it subclasses it for value storage), augmented with a doubly-linked list of key nodes for order, and — the clever part — an array that mirrors the dict’s hash table to make node lookup O(1) (:489):

struct _odictobject {
    PyDictObject od_dict;        /* the actual dict (inherited storage) */
    _ODictNode *od_first;        /* head of the order list */
    _ODictNode *od_last;         /* tail of the order list */
    _ODictNode **od_fast_nodes;  /* table mirroring dict's slots: key -> node* */
    Py_ssize_t od_fast_nodes_size;
    void *od_resize_sentinel;    /* changes when the mirror must be rebuilt */
    size_t od_state;             /* mutation guard */
    PyObject *od_inst_dict;      /* the instance __dict__ */
    PyObject *od_weakreflist;
};
struct _odictnode {            /* a node in the order list */
    PyObject *key;
    Py_hash_t hash;
    _ODictNode *next;
    _ODictNode *prev;
};

The design comment (:19) lays out the problem: a bare linked list on top of a dict would make __delitem__ O(n), because you must find the node for a key before unlinking it. The pure-Python OrderedDict solves this with a second dict mapping keys → nodes; the C version uses a leaner option (#2 in the comment): an array od_fast_nodes that mirrors the dict’s internal hash-table slots, so a key’s slot index — recovered via _Py_dict_lookup and pointer arithmetic — directly yields its node pointer in O(1). The catch is keeping the mirror in sync across dict resizes; the trick is to defer re-syncing (_odict_resize) until a lookup actually needs it (:50, :562). This way OrderedDict preserves dict’s O(1) complexity for all the dict operations.

move_to_end and popitem(last=)

move_to_end(key, last=True) is the operation that justifies the order list: it unlinks the key’s node and splices it onto either end of the list (pure-Python reference at Lib/collections/__init__.py:194; C equivalent in odictobject.c). popitem(last=True) pops and removes a (key, value) pair in LIFO order if last is true, FIFO if false (collections docs). Plain dict has neither. move_to_end was added in 3.2; OrderedDict itself is documented as added in 3.1 (collections.rst:1152, :1178).

Order-sensitive equality

The headline behavioral difference from dict: OrderedDict.__eq__ between two OrderedDicts is order-sensitive (“The equality operation for OrderedDict checks for matching order” — collections docs). _odict_keys_equal (Objects/odictobject.c) walks both order lists in lockstep, comparing keys position-by-position with PyObject_RichCompareBool, and returns unequal as soon as the sequences diverge (it also bumps a state check to raise RuntimeError on mutation during comparison). So OrderedDict([('a',1),('b',2)]) != OrderedDict([('b',2),('a',1)]), whereas the equivalent plain dicts compare equal. Crucially, an OrderedDict-vs-dict comparison falls back to order-insensitive dict equality — the order check only applies between two OrderedDicts.

Counter — A dict Subclass for Tallying

Counter is pure Python, a dict subclass mapping elements to integer counts (Lib/collections/__init__.py:551; added 3.1). Two design choices define it. First, __missing__(self, key) returns 0 rather than raising (:616), so c['absent'] is 0 instead of a KeyError — but note this means c['absent'] does not insert the key (only += does). Second, most_common(n) (:625) returns the n highest-count (element, count) pairs. With n is None it sorts all items by count (sorted(..., key=itemgetter(1), reverse=True), O(k log k)); with a finite n it uses heapq.nlargest(n, ...) — an O(k log n) partial selection via a size-n heap, which is the right tool when you want the top few of many (functools and lru_cache Internals is the sibling utility module; heapq is the heap implementation). elements() (:644) returns an iterator that repeats each element by its count using itertools.chain.from_iterable(starmap(repeat, items)), skipping non-positive counts. total() (added 3.10) sums the counts. As a dict subclass, Counter inherited insertion-order memory and order-preserving math operations in 3.7, and gained rich comparisons and zero-treatment-of-missing-elements in equality tests in 3.10 (collections.rst:276, :352).

defaultdict — __missing__ + default_factory in C

defaultdict is a dict subclass implemented in C (Modules/_collectionsmodule.c; imported at Lib/collections/__init__.py:58). It stores a default_factory callable and overrides __missing__ — the hook dict.__getitem__ invokes when a key is absent (The Sequence and Mapping Protocols). defdict_missing (Modules/_collectionsmodule.c) is the whole mechanism: if default_factory is None, raise KeyError(key); otherwise call the factory with no arguments, store the result as self[key] via PyDict_SetDefaultRef, and return it:

static PyObject *
defdict_missing(PyObject *op, PyObject *key) {
    defdictobject *dd = (defdictobject *)op;
    PyObject *factory = dd->default_factory;
    if (factory == NULL || factory == Py_None) {
        PyErr_SetObject(PyExc_KeyError, PyTuple_Pack(1, key));  /* simplified */
        return NULL;
    }
    PyObject *value = _PyObject_CallNoArgs(factory);   /* e.g. list(), int() */
    /* ... store self[key] = value and return it ... */
}

The key subtlety: __missing__ runs only for d[key] lookups (and operations routed through __getitem__), not for d.get(key). So defaultdict(list)[k] auto-creates and inserts an empty list, but defaultdict(list).get(k) returns None without inserting. This is also why ChainMap.__getitem__ (below) deliberately avoids key in mapping when chaining over a defaultdict.

namedtuple — A Code-Generated tuple Subclass

namedtuple(typename, field_names, ...) returns a brand-new tuple subclass with named field access (Lib/collections/__init__.py:361). It is the most metaprogramming-heavy thing in the module, but in 3.14 it is not the old “exec a giant class-template string” approach — that was replaced years ago.

How the class is built

After validating field names (rejecting keywords, duplicates, leading underscores unless rename=True), the factory builds the class with type(), not exec. The only dynamically-evaluated code is the __new__ constructor, generated as a lambda string and eval’d in a tiny namespace (:446):

code = f'lambda _cls, {arg_list}: _tuple_new(_cls, ({arg_list}))'
__new__ = eval(code, namespace)

For Point = namedtuple('Point', ['x','y']) that is lambda _cls, x, y: _tuple_new(_cls, (x, y)) — so construction is just tuple.__new__ of the values. The class namespace is then assembled as a plain dict and handed to type() (:497–:515):

class_namespace = {
    '__doc__': f'{typename}({arg_list})',
    '__slots__': (),                 # no per-instance __dict__ — zero extra memory
    '_fields': field_names,          # tuple of field-name strings
    '_field_defaults': field_defaults,
    '__new__': __new__,
    '_make': _make,                  # classmethod: build from an iterable
    '_replace': _replace,            # return a copy with some fields changed
    '__match_args__': field_names,   # enables positional pattern matching
    # ... __repr__, _asdict, __getnewargs__ ...
}
for index, name in enumerate(field_names):
    class_namespace[name] = _tuplegetter(index, doc)   # C descriptor per field
result = type(typename, (tuple,), class_namespace)

Three details carry the design. __slots__ = () means instances carry no __dict__ — a namedtuple is exactly as memory-cheap as a plain tuple. The per-field accessors are _tuplegetter(index, doc) objects — a C-accelerated descriptor from _collections (Modules/_collectionsmodule.c:2655) whose __get__ simply returns tuple[index], so p.x is as fast as p[0]. And __match_args__ = field_names lets the type participate in structural pattern matching (case Point(x=0, y=y):).

The introspection API

_fields is the tuple of field names; _field_defaults maps fields to their defaults (from the defaults= argument, applied right-to-left, added 3.7); _make(iterable) is a classmethod building an instance from an iterable; _replace(**kwds) returns a new instance with named fields overwritten (raising TypeError on unknown fields since 3.13); _asdict() returns a regular dict (it returned an OrderedDict from 3.1 until 3.8, when it reverted to plain dict since dicts became ordered) (collections.rst:969, :972, :993). The module= parameter (3.6) sets __module__ so the generated class pickles correctly.

Resolved (2026-06-01)

Confirmed against the v3.14.5 tag: namedtuple builds the class with a single eval(code, namespace) for the __new__ callable (line 447) and type(typename, (tuple,), class_namespace) for the class itself (line 515) — there is no _class_template string and no exec of a multi-method template (that approach was retired after ~3.6). The task brief’s “exec of a class template” description was stale; the prose above follows the actual source. Source: collections/init.py@v3.14.5.

ChainMap — A Layered View Over Multiple Mappings

ChainMap(*maps) (added 3.3) is the simplest container here: it groups several mappings into one updatable view without copying (Lib/collections/__init__.py:995; collections.rst:40). Its only state is self.maps, a public list of the underlying mappings (defaulting to a single empty dict). Lookups search the maps in order — __getitem__ tries each mapping until a key is found, raising KeyError (via __missing__) if none has it (:1019). Writes, updates, and deletions affect only the first map (self.maps[0]). This makes it ideal for layered configuration (command-line overrides → environment → defaults) or nested scopes. new_child() pushes a fresh writable map onto the front; parents returns a view skipping the first map. Note the implementation deliberately uses try: return mapping[key] rather than key in mapping so it behaves correctly even when a layer is a defaultdict (whose __contains__ and __getitem__ differ in side effects, as covered above).

Failure Modes and Common Misunderstandings

  • deque is not a list: deque[i] for a middle i is O(n), and deque has no slicing (d[1:3] raises TypeError). Reaching for deque to fix list performance only helps if your access is at the ends.
  • maxlen silently drops data: appending to a full bounded deque discards the opposite end without warning — fine for a sliding window, a silent bug if you expected an error.
  • Counter[missing] returns 0 but doesn’t insert: read access never creates the key; only augmented assignment (c[k] += 1) does. Iterating a Counter after a bunch of c[k] reads will not show those keys.
  • defaultdict.get bypasses the factory: dd.get(k) is None for a missing key; only dd[k] triggers default_factory. A surprisingly common source of “why didn’t my default appear?”
  • OrderedDict equality surprises: two OrderedDicts with the same items in different order are unequal, but each is equal to the corresponding plain dict. Mixing them in a set or as keys can behave non-transitively in intuition (though == itself is well-defined).
  • namedtuple needs valid identifiers: field names that are keywords, duplicates, or start with _ raise ValueError unless you pass rename=True (which silently renames them to _0, _1, …).

Alternatives and When to Choose Them

Use deque for FIFO/LIFO queues and sliding windows; use list for indexed/random access and slicing. Since dict is insertion-ordered (3.7+), reach for OrderedDict only when you need move_to_end, popitem(last=False), or order-sensitive equality — otherwise a plain dict is faster and lighter (Dictionary Ordering Assumptions). Use Counter for tallying over hand-rolling dict.get(k, 0) + 1. Use namedtuple for small immutable records where you also want tuple behavior (unpacking, indexing); for richer records prefer dataclasses or typing.NamedTuple. Use ChainMap for layered lookups instead of repeatedly merging dicts (which copies).

See Also

Graph View

Backlinks