OrderedDict - Insertion-Order Preserving Dictionary

The OrderedDict class from collections maintains insertion order of keys, guaranteeing that iteration order matches insertion order even in older Python versions.

Python 3.7+ Note

Regular dict maintains insertion order as a language guarantee. Use OrderedDict for backwards compatibility with Python 3.6 and earlier, or when you need specialized methods like move_to_end().

Complexity Reference

Operation	Time	Space	Notes
OrderedDict()	O(n)	O(n)	Create from dict/iterable
__getitem__	O(1)	O(1)	Access by key
__setitem__	O(1)	O(1)	Set/update item
__delitem__	O(1)	O(1)	Delete item (uses doubly-linked list)
move_to_end()	O(1)	O(1)	Move key to end
popitem(last=True)	O(1)	O(1)	Remove last (LIFO). last=False pops the first in O(1) too, which dict.popitem() cannot do at all
Iteration	O(n)	O(1)	Iterate in insertion order

Basic Usage

from collections import OrderedDict

# Create empty OrderedDict - O(1)
od = OrderedDict()

# Create from dict - O(n)
od = OrderedDict([('a', 1), ('b', 2), ('c', 3)])
# Order: a, b, c (insertion order)

# Create from kwargs - O(n)
od = OrderedDict(a=1, b=2, c=3)

# Access - O(1)
print(od['a'])  # 1

# Update - O(1)
od['d'] = 4

# Iterate maintains insertion order - O(n)
for key, value in od.items():  # O(n)
    print(key, value)

Move to End

from collections import OrderedDict

# Create OrderedDict - O(n)
od = OrderedDict([('a', 1), ('b', 2), ('c', 3)])

# Move to end - O(1)
od.move_to_end('a')
# Order: b, c, a

# Move to beginning - O(1)
od.move_to_end('b', last=False)
# Order: b, c, a (stays at front)

FIFO / LIFO Access

from collections import OrderedDict

# Create OrderedDict - O(n)
od = OrderedDict([('a', 1), ('b', 2), ('c', 3)])

# Pop last (LIFO stack) - O(1)
last = od.popitem()  # ('c', 3)

# Pop first (FIFO queue) - O(1)
first = od.popitem(last=False)  # ('a', 1)

# Remaining order: b

Reversing Insertion Order

from collections import OrderedDict

# Create OrderedDict - O(n)
od = OrderedDict([('a', 1), ('b', 2), ('c', 3)])

# Reverse iteration - O(n)
for key in reversed(od):  # O(n)
    print(key, od[key])
# Output: c, b, a

# Create reversed OrderedDict - O(n)
reversed_od = OrderedDict(reversed(od.items()))
# Order: c, b, a

Equality Comparison

from collections import OrderedDict

# Create OrderedDicts with same keys but different order
od1 = OrderedDict([('a', 1), ('b', 2), ('c', 3)])
od2 = OrderedDict([('c', 3), ('a', 1), ('b', 2)])

# Order matters for equality - O(n) comparison
print(od1 == od2)  # False (different order)

# Same order - O(n) comparison
od3 = OrderedDict([('a', 1), ('b', 2), ('c', 3)])
print(od1 == od3)  # True

# Regular dict doesn't care about order - O(n)
d = {'a': 1, 'b': 2, 'c': 3}
print(od1 == d)  # True (same keys/values, order ignored)

LRU Cache Pattern

from collections import OrderedDict

class LRUCache:
    """Simple LRU cache using OrderedDict - O(1) operations"""

    def __init__(self, capacity):
        self.cache = OrderedDict()  # O(1)
        self.capacity = capacity

    def get(self, key):
        """Get value and mark as recently used - O(1)"""
        if key not in self.cache:  # O(1)
            return None
        # Move to end (most recent) - O(1)
        self.cache.move_to_end(key)
        return self.cache[key]  # O(1)

    def put(self, key, value):
        """Put value and evict if over capacity - O(1)"""
        if key in self.cache:  # O(1)
            # Update and move to end - O(1)
            self.cache.move_to_end(key)
        self.cache[key] = value  # O(1)

        # Evict least recently used if over capacity - O(1)
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)  # O(1) - remove first

# Usage
cache = LRUCache(2)
cache.put('a', 1)   # O(1)
cache.put('b', 2)   # O(1)
print(cache.get('a'))  # O(1), marks 'a' as recent
cache.put('c', 3)   # O(1), evicts 'b' (least recent)

Common Patterns

Preserving Insertion Order

from collections import OrderedDict

# Creating from list of tuples preserves insertion order - O(n)
data = [('name', 'Alice'), ('age', 30), ('city', 'NYC')]
od = OrderedDict(data)  # O(n)

# Iteration order guaranteed - O(n)
for key in od:  # O(n)
    print(f"{key}: {od[key]}")
# Output: name: Alice, age: 30, city: NYC

Deep Copy Preserving Order

from collections import OrderedDict
import copy

# Original OrderedDict - O(n)
od1 = OrderedDict([('a', 1), ('b', 2), ('c', 3)])

# Deep copy preserves order - O(n)
od2 = copy.deepcopy(od1)

# Same order guaranteed
assert list(od1.keys()) == list(od2.keys())

Comparison with Regular Dict

from collections import OrderedDict

# Python 3.7+ - regular dict preserves insertion order
regular_dict = {'a': 1, 'b': 2, 'c': 3}

# OrderedDict also preserves insertion order
ordered_dict = OrderedDict([('a', 1), ('b', 2), ('c', 3)])

# Both maintain insertion order - O(n)
print(list(regular_dict.keys()))  # ['a', 'b', 'c']
print(list(ordered_dict.keys()))  # ['a', 'b', 'c']

# Key difference: OrderedDict has move_to_end() and stricter equality
ordered_dict.move_to_end('a')  # Available in OrderedDict
# regular_dict.move_to_end('a')  # Not available

When to Use OrderedDict

Good For:

• Backwards compatibility (Python 3.6 and earlier)
• Using move_to_end() for LRU/MRU patterns
• Explicit intent to preserve order
• JSON serialization with guaranteed order
• Strict equality based on insertion order

Not Good For:

• Python 3.7+ without special ordering needs (use dict)
• When order doesn't matter (use dict)
• Memory-constrained environments: the linked list roughly doubles it, at 100,000 entries 9.1 MB against a dict's 3.8 MB (64-bit CPython)
• Iteration-heavy code, where the gap is largest

How much slower, exactly

"Regular dict is faster" is true but uneven. Mappings of 100,000 entries, on 64-bit CPython 3.11 on one Linux machine - illustrative, not portable:

Measured	dict	OrderedDict
10,000 lookups of one key	240 µs	252 µs	1.05x - the same code, inherited
10,000 assignments to one key	599 µs	722 µs	1.21x
build 1,000 entries, then delete all	54 µs	102 µs	1.89x
one construction from 100,000 pairs	4970 µs	12961 µs	2.61x
one list() over all 100,000 keys	619 µs	3522 µs	5.69x

Lookups cost the same, because OrderedDict inherits them unchanged. What you pay for is maintaining and walking the doubly-linked list, so the cost lands on construction, mutation and above all iteration.

Comparison with Alternatives

from collections import OrderedDict, defaultdict

# OrderedDict - for insertion-order preservation
od = OrderedDict([('a', 1), ('b', 2)])  # O(n)
od.move_to_end('a')  # O(1)

# defaultdict - for default values
dd = defaultdict(int)  # O(1)
dd['count'] += 1  # O(1)

# Regular dict - for simplicity in Python 3.7+
d = {'a': 1, 'b': 2}  # O(n)

Version Notes

• Python 2.7+: OrderedDict available
• Python 3.7+: Regular dict maintains insertion order, but OrderedDict still useful for explicit semantics
• All versions: O(1) operations for access, insertion, deletion

Related Modules

• dict - Standard dictionary
• defaultdict - Dict with default values
• Counter - Dict subclass for counting
• collections - Container data types

Best Practices

✅ Do:

• Use for backwards compatibility with Python 3.6
• Use for LRU/MRU cache patterns with move_to_end()
• Use when strict insertion-order equality matters
• Use for explicit code intent

❌ Avoid:

• Using instead of regular dict in Python 3.7+ without special needs
• Assuming faster than regular dict
• Using for non-ordered operations
• Frequent copying (use references when possible)