CPython's OrderedDict in C: O(1) Insertion Order That Just Works

TL;DR: OrderedDict is a C-level dict subclass in Objects/odictobject.c. It bolts a doubly-linked list of keys onto the dict and mirrors that list into an od_fast_nodes array so node lookups stay O(1) — even after the dict resizes underneath it.

Python’s collections.OrderedDict remembers insertion order. You might assume it lives in Lib/collections, but it doesn’t: it’s a built-in type written in C, in Objects/odictobject.c, and it subclasses dict. Let’s trace how it works in CPython 3.15.

Why OrderedDict still exists (dicts are already ordered)

Since 3.7, a plain dict already preserves insertion order. So why bother with OrderedDict?

Because it offers operations a plain dict simply doesn’t have: move_to_end(), FIFO/LIFO popitem(last=...), and order-sensitive equality. It also gives you a stable, explicitly ordered contract that subclasses and tooling can lean on.

Implementing it as a C type that inherits from dict keeps it fast and interoperable with the dict C-API surface wherever possible.

Bottom line: plain dicts handle the common case, but OrderedDict hands you explicit ordering guarantees and order-specific tools a plain dict won’t.

The struct: a dict plus a linked list

PyODictObject embeds a PyDictObject as its first member, so an OrderedDict is a dict at the C level — pass it anywhere that wants a PyDictObject *. On top of that it carries a doubly-linked list of keys plus a “fast node” lookup table:

c
// Objects/odictobject.c
struct _odictobject {
    PyDictObject od_dict;        /* the underlying dict */
    _ODictNode *od_first;        /* first node in the linked list, if any */
    _ODictNode *od_last;         /* last node in the linked list, if any */
    _ODictNode **od_fast_nodes;  /* hash table that mirrors the dict table */
    Py_ssize_t od_fast_nodes_size;
    void *od_resize_sentinel;    /* changes if odict should be resized */
    size_t od_state;             /* incremented whenever the LL changes */
    PyObject *od_inst_dict;      /* OrderedDict().__dict__ */
    PyObject *od_weakreflist;    /* holds weakrefs to the odict */
};

The od_dict member is what makes PyDict_* calls work on an OrderedDict instance. The linked list and fast-node table are the order-preserving layer bolted on top.

Think of it this way: the dict does the heavy lifting — hashing, storage, lookups — and the linked list is only there to remember which key came first.

Nodes store keys, not values

Each node holds a key (owned reference), its hash, and prev/next pointers:

c
// Objects/odictobject.c
struct _odictnode {
    PyObject *key;
    Py_hash_t hash;
    _ODictNode *next;
    _ODictNode *prev;
};

#define _odictnode_KEY(node)     (node->key)
#define _odictnode_HASH(node)    (node->hash)
/* borrowed reference */
#define _odictnode_VALUE(node, od) \
    PyODict_GetItemWithError((PyObject *)od, _odictnode_KEY(node))
#define _odictnode_PREV(node)    (node->prev)
#define _odictnode_NEXT(node)    (node->next)

#define _odict_FIRST(od)  (_PyODictObject_CAST(od)->od_first)
#define _odict_LAST(od)   (_PyODictObject_CAST(od)->od_last)
#define _odict_EMPTY(od)  (_odict_FIRST(od) == NULL)
#define _odict_FOREACH(od, node) \
    for (node = _odict_FIRST(od); node != NULL; node = _odictnode_NEXT(node))

Notice that a node stores only the key. Values still live in the underlying dict, which keeps the linked list cheap and avoids duplicating value storage. _odictnode_VALUE is just a PyODict_GetItemWithError call away.

O(1) node lookup with od_fast_nodes

A naive linked list on top of dict would make __delitem__ O(n): you have to find the node for a key before you can unlink it. To keep it O(1), CPython mirrors dict’s hash-table layout with an array of node pointers, od_fast_nodes, indexed exactly the way dict’s dk_indices/entries are.

The index for a key comes from running dict’s own lookup and then using pointer arithmetic on the returned entry index:

c
// Objects/odictobject.c
static Py_ssize_t
_odict_get_index_raw(PyODictObject *od, PyObject *key, Py_hash_t hash)
{
    PyObject *value = NULL;
    PyDictKeysObject *keys = ((PyDictObject *)od)->ma_keys;
    Py_ssize_t ix;
    ix = _Py_dict_lookup((PyDictObject *)od, key, hash, &value);
    Py_XDECREF(value);
    if (ix == DKIX_EMPTY) {
        return keys->dk_nentries;  /* index of new entry */
    }
    if (ix < 0)
        return -1;
    /* We use pointer arithmetic to get the entry's index into the table. */
    return ix;
}

_odict_find_node then just indexes into od_fast_nodes:

c
// Objects/odictobject.c
static _ODictNode *
_odict_find_node(PyODictObject *od, PyObject *key)
{
    if (_odict_EMPTY(od)) return NULL;
    Py_hash_t hash = PyObject_Hash(key);
    if (hash == -1) return NULL;
    Py_ssize_t index = _odict_get_index(od, key, hash);
    if (index < 0) return NULL;
    assert(od->od_fast_nodes != NULL);
    return od->od_fast_nodes[index];
}

Here’s the thing: without that mirror array, deleting a key would mean walking the entire list to find its node. With it, you jump straight to the node.

Keeping the mirror in sync when dict resizes

Dict resizes invalidate the correspondence between od_fast_nodes and ma_keys. Instead of updating eagerly, CPython defers: od_resize_sentinel stores the current ma_keys pointer, and _odict_get_index checks whether the sentinel still matches (and whether the table size still matches 1 << dk_log2_size). If not, it rebuilds the whole fast-node table:

c
// Objects/odictobject.c
static int
_odict_resize(PyODictObject *od)
{
    Py_ssize_t size, i;
    _ODictNode **fast_nodes, *node;

    size = ONE << (((PyDictObject *)od)->ma_keys->dk_log2_size);
    fast_nodes = PyMem_NEW(_ODictNode *, size);
    if (fast_nodes == NULL) { PyErr_NoMemory(); return -1; }
    for (i = 0; i < size; i++)
        fast_nodes[i] = NULL;

    /* Copy the current nodes into the table. */
    _odict_FOREACH(od, node) {
        i = _odict_get_index_raw(od, _odictnode_KEY(node),
                                 _odictnode_HASH(node));
        if (i < 0) { PyMem_Free(fast_nodes); return -1; }
        fast_nodes[i] = node;
    }

    PyMem_Free(od->od_fast_nodes);
    od->od_fast_nodes = fast_nodes;
    od->od_fast_nodes_size = size;
    od->od_resize_sentinel = ((PyDictObject *)od)->ma_keys;
    return 0;
}

This lazy rebuild is what lets node lookup stay O(1) amortized without hooking into every dict resize.

Gotcha: the mirror doesn’t update on every dict operation. It’s rebuilt lazily, which means od_fast_nodes can be stale until the next lookup forces a rebuild.

Adding and removing nodes

Insertion appends a node at the tail of the list and records it in the fast table:

c
// Objects/odictobject.c
static int
_odict_add_new_node(PyODictObject *od, PyObject *key, Py_hash_t hash)
{
    Py_INCREF(key);
    Py_ssize_t i = _odict_get_index(od, key, hash);
    if (i < 0) { ... Py_DECREF(key); return -1; }
    assert(od->od_fast_nodes != NULL);
    if (od->od_fast_nodes[i] != NULL) {
        /* We already have a node for the key so there's no need to add one. */
        Py_DECREF(key);
        return 0;
    }

    _ODictNode *node = (_ODictNode *)PyMem_Malloc(sizeof(_ODictNode));
    if (node == NULL) { Py_DECREF(key); PyErr_NoMemory(); return -1; }

    _odictnode_KEY(node) = key;
    _odictnode_HASH(node) = hash;
    _odict_add_tail(od, node);
    od->od_fast_nodes[i] = node;
    return 0;
}

Removal is the delicate part. Because of hash collisions, dict’s probe result for a key can change after a different key is deleted — a slot becomes a tombstone and the probe chain shifts. So _odict_clear_node clears the fast-node entry before PyDict_DelItem runs:

c
// Objects/odictobject.c
static int
_odict_clear_node(PyODictObject *od, _ODictNode *node, PyObject *key,
                  Py_hash_t hash)
{
    Py_ssize_t i = _odict_get_index(od, key, hash);
    if (i < 0) return PyErr_Occurred() ? -1 : 0;

    assert(od->od_fast_nodes != NULL);
    if (node == NULL)
        node = od->od_fast_nodes[i];
    assert(node == od->od_fast_nodes[i]);
    if (node == NULL) return 0;

    // Now clear the node.
    od->od_fast_nodes[i] = NULL;
    _odict_remove_node(od, node);
    _odictnode_DEALLOC(node);   /* Py_DECREF(key); PyMem_Free(node) */
    return 0;
}

The public entry points combine this with the underlying dict mutation:

c
// Objects/odictobject.c
int
PyODict_DelItem_LockHeld(PyObject *od, PyObject *key)
{
    Py_hash_t hash = PyObject_Hash(key);
    if (hash == -1) return -1;
    int res = _odict_clear_node(_PyODictObject_CAST(od), NULL, key, hash);
    if (res < 0) return -1;
    return _PyDict_DelItem_KnownHash_LockHeld(od, key, hash);
}

static int
_PyODict_SetItem_KnownHash_LockHeld(PyObject *od, PyObject *key,
                                    PyObject *value, Py_hash_t hash)
{
    int res = _PyDict_SetItem_KnownHash_LockHeld((PyDictObject *)od, key, value, hash);
    if (res == 0) {
        res = _odict_add_new_node(_PyODictObject_CAST(od), key, hash);
        if (res < 0) {
            /* Revert setting the value on the dict */
            PyObject *exc = PyErr_GetRaisedException();
            (void) _PyDict_DelItem_KnownHash(od, key, hash);
            _PyErr_ChainExceptions1(exc);
        }
    }
    return res;
}

Notice the rollback in _PyODict_SetItem_KnownHash_LockHeld: if node creation fails, the dict insertion is undone and the original exception is re-raised.

If you’ve ever been burned by half-applied mutations, this is the pattern to copy: set the dict value first, add the node second, and undo the dict change if the node can’t be created.

od_state: the mutation counter that keeps iterators honest

Every linked-list change bumps od_state. That’s how iterators and internal loops detect concurrent mutation. The iterator snapshots od_state and the size it started with, then compares:

c
// Objects/odictobject.c
static PyObject *
odictiter_nextkey_lock_held(odictiterobject *di)
{
    ...
    if (di->di_odict->od_state != di->di_state) {
        PyErr_SetString(PyExc_RuntimeError,
                        "OrderedDict mutated during iteration");
        goto done;
    }
    if (di->di_size != PyODict_SIZE(di->di_odict)) {
        PyErr_SetString(PyExc_RuntimeError,
                        "OrderedDict changed size during iteration");
        ...
    }
    ...
}

Internal loops such as OrderedDict_copy_impl do the same check after each step, raising RuntimeError("OrderedDict mutated during iteration") if the state changed. __eq__’s _odict_keys_equal likewise snapshots both states and checks them on every key comparison.

The real win: you get the same “dictionary changed size during iteration” safety net plain dicts give you — but for the linked-list order too.

Iterators track keys, not node pointers

A subtlety the source calls out: holding a node pointer across code that might delete it can dangle. So iterators store the current key and re-look-up the node on each step:

c
// Objects/odictobject.c
/* In order to protect against modifications during iteration, we track
 * the current key instead of the current node. */
node = _odict_find_node(di->di_odict, di->di_current);
if (node == NULL) { ... /* Must have been deleted. */ ... }
key = di->di_current;
node = reversed ? _odictnode_PREV(node) : _odictnode_NEXT(node);
if (node == NULL) {
    di->di_current = NULL;
} else {
    di->di_current = Py_NewRef(_odictnode_KEY(node));
}

This is the “keep the key in the variable” solution straight from the file’s design notes.

Gotcha: never cache a node pointer across iteration steps. Keep the key, re-look-up the node.

move_to_end: reorder without touching values

move_to_end unlinks the node and re-appends it (at head or tail), but only when it isn’t already there:

c
// Objects/odictobject.c
static PyObject *
OrderedDict_move_to_end_impl(PyODictObject *self, PyObject *key, int last)
{
    _ODictNode *node;
    if (_odict_EMPTY(self)) { PyErr_SetObject(PyExc_KeyError, key); return NULL; }
    node = last ? _odict_LAST(self) : _odict_FIRST(self);
    if (key != _odictnode_KEY(node)) {
        node = _odict_find_node(self, key);
        if (node == NULL) { ... return NULL; }
        if (last) {
            if (node != _odict_LAST(self)) {
                _odict_remove_node(self, node);
                _odict_add_tail(self, node);
            }
        } else {
            if (node != _odict_FIRST(self)) {
                _odict_remove_node(self, node);
                _odict_add_head(self, node);
            }
        }
    }
    Py_RETURN_NONE;
}

Because _odict_remove_node/_odict_add_tail only relink pointers and bump od_state — they never touch the dict — the value side is completely unaffected.

Think of it as moving a bookmark: the page (value) stays put, you’re just changing where it sits in the list.

popitem: FIFO/LIFO pops, node first

popitem(last) picks the first or last node, then routes through _odict_popkey_hash, which clears the node first (to avoid a dict resize/reentrancy hazard) and then pops the value from the dict:

c
// Objects/odictobject.c
static PyObject *
OrderedDict_popitem_impl(PyODictObject *self, int last)
{
    PyObject *key, *value;
    _ODictNode *node;

    if (_odict_EMPTY(self)) {
        PyErr_SetString(PyExc_KeyError, "dictionary is empty");
        return NULL;
    }

    node = last ? _odict_LAST(self) : _odict_FIRST(self);
    key = Py_NewRef(_odictnode_KEY(node));
    value = _odict_popkey_hash((PyObject *)self, key, NULL,
                               _odictnode_HASH(node));
    if (value == NULL) { Py_DECREF(key); return NULL; }
    return _PyTuple_FromPairSteal(key, value);
}

c
// Objects/odictobject.c  (_odict_popkey_hash)
_ODictNode *node = _odict_find_node_hash(...);
if (node != NULL) {
    int res = _odict_clear_node(..., node, key, hash);   /* unlink + free node */
    if (res < 0) goto done;
    if (_PyDict_Pop_KnownHash(...) == 0) {
        value = Py_NewRef(failobj);
    }
}

The ordering matters: clear the node before touching the dict, so a resize can’t invalidate the pointer you’re holding.

Equality: order-sensitive, but cheap to short-circuit

odict_richcompare first delegates to dict’s richcompare — so unequal key sets or values short-circuit — and only if both sides are OrderedDicts and the dict comparison didn’t already decide does it compare key order via _odict_keys_equal:

c
// Objects/odictobject.c
static PyObject *
odict_richcompare_lock_held(PyObject *v, PyObject *w, int op)
{
    if (!PyODict_Check(v) || !PyAnyDict_Check(w))
        Py_RETURN_NOTIMPLEMENTED;

    if (op == Py_EQ || op == Py_NE) {
        PyObject *cmp = PyDict_Type.tp_richcompare(v, w, op);
        if (cmp == NULL) return NULL;
        if (!PyODict_Check(w)) return cmp;
        if (op == Py_EQ && cmp == Py_False) return cmp;
        if (op == Py_NE && cmp == Py_True) return cmp;
        Py_DECREF(cmp);

        int eq = _odict_keys_equal(_PyODictObject_CAST(v),
                                   _PyODictObject_CAST(w));
        if (eq < 0) return NULL;
        PyObject *res = (eq == (op == Py_EQ)) ? Py_True : Py_False;
        return Py_NewRef(res);
    } else {
        Py_RETURN_NOTIMPLEMENTED;
    }
}

Bottom line: two OrderedDicts with the same keys and values are not equal if the insertion order differs. But when the dict-level comparison already fails, you never pay for the order check at all.

Views and reversed()

keys(), values(), and items() return views whose type objects (PyODictKeys_Type and friends) base on the dict view types but override tp_iter to produce an odict_iterator that walks the linked list instead of dk_entries. The iterator supports __reversed__ by starting at _odict_LAST and following prev pointers. The views themselves also expose __reversed__.

Deallocation and GC

odict_dealloc untracks from the GC, clears the instance dict and weakrefs, frees all the nodes, and then chains to dict’s dealloc:

c
// Objects/odictobject.c
static void
odict_dealloc(PyObject *op)
{
    PyODictObject *self = _PyODictObject_CAST(op);
    PyObject_GC_UnTrack(self);

    Py_XDECREF(self->od_inst_dict);
    FT_CLEAR_WEAKREFS(op, self->od_weakreflist);

    _odict_clear_nodes(self);          /* frees od_fast_nodes + all nodes */
    PyDict_Type.tp_dealloc((PyObject *)self);
}

_odict_clear_nodes frees the fast-node array and walks the list deallocating every node (decrefing its key). odict_traverse visits od_inst_dict and every node’s key so the GC can find cycles.

sizeof

Size accounting adds the fast-node array and the node structs on top of dict’s size:

c
// Objects/odictobject.c
static Py_ssize_t
OrderedDict___sizeof___impl(PyODictObject *self)
{
    Py_ssize_t res = _PyDict_SizeOf_LockHeld((PyDictObject *)self);
    res += sizeof(_ODictNode *) * self->od_fast_nodes_size;  /* od_fast_nodes */
    if (!_odict_EMPTY(self)) {
        res += sizeof(_ODictNode) * PyODict_SIZE(self);  /* linked-list */
    }
    return res;
}

Type registration and the public C API

PyODict_Type has tp_base = &PyDict_Type, tp_name = "collections.OrderedDict", and overrides tp_dealloc, tp_repr, mp_ass_subscript, tp_traverse, tp_clear, tp_richcompare, tp_iter, tp_init, and others. The public C API is small: PyODict_New, PyODict_SetItem/..._LockHeld, PyODict_DelItem/..._LockHeld, plus the PyODict_Check/PyODict_CheckExact macros.

Wrapping up

collections.OrderedDict lives in Objects/odictobject.c as PyODict_Type, a subclass of PyDict_Type. A PyODictObject is a PyDictObject plus a doubly-linked list of _ODictNode (key + hash + prev/next) and an od_fast_nodes array of node pointers mirroring dict’s hash table for O(1) lookup.

The details worth remembering: the mirror is rebuilt lazily when the dict resizes (detected via od_resize_sentinel), keeping node lookup O(1) amortized. Removals clear the fast-node slot before mutating the dict, so collisions can’t corrupt the mapping. od_state plus size snapshots let iterators and internal loops detect mutation and raise RuntimeError. Iterators track the current key rather than a node pointer to avoid dangling pointers. And move_to_end/popitem operate purely on the linked list — values never move.

If you need explicit, order-sensitive semantics beyond what a plain dict offers, OrderedDict delivers them in C, with the same performance discipline as the dict it inherits from.