Dictionaries
OrderedDict
Order-preserving dictionaries with order-dependent operations
Interview: Important for LRU cache design, understanding Python 3.7+ dict behavior, and legacy codebases
OrderedDict from the collections module is a dict subclass that remembers the order in which keys were first inserted. While regular dicts preserve insertion order since Python 3.7, OrderedDict provides additional order-dependent operations and different equality semantics that make it valuable in specific scenarios.
OrderedDict vs Regular Dict (Python 3.7+)
Since Python 3.7, regular dicts guarantee insertion order preservation. So when should you still use OrderedDict?
- Order-sensitive equality: Two OrderedDicts are equal only if they have the same key-value pairs AND same order
- move_to_end(): Reorder keys by moving existing keys to the end or beginning
- popitem(last=False): Pop from the beginning (FIFO) — regular dict only supports popitem() (LIFO)
- Intent signaling: Using OrderedDict makes it explicit that order matters in your algorithm
- Backward compatibility: Code that must work on Python < 3.7 needs OrderedDict for guaranteed order
When to Use OrderedDict Today
Use OrderedDict when you need: (1) move_to_end() for LRU cache implementation, (2) order-sensitive equality checks, (3) explicit signaling that key order is algorithmically significant. For all other cases, regular dict is faster and more Pythonic.
Key Methods
- move_to_end(key, last=True): Move an existing key to the end (or beginning if last=False). Raises KeyError if key doesn't exist
- popitem(last=True): Remove and return a (key, value) pair. last=True pops the last item (LIFO), last=False pops the first (FIFO)
- __reversed__(): Iterate keys in reverse insertion order —
for key in reversed(od)
LRU Cache Implementation
OrderedDict is the standard building block for implementing Least Recently Used (LRU) caches — a very common interview question:
- On access (get): move the key to the end (most recently used)
- On insert: if at capacity, popitem(last=False) to evict the least recently used item
- This gives O(1) get, put, and eviction — matching the optimal LRU cache performance
Performance Note
OrderedDict has slightly higher memory usage and slower operations than regular dict due to the doubly-linked list that tracks insertion order. Only use it when you specifically need its order-dependent features.
Order-Dependent Operations
- Sorting by insertion time: OrderedDict preserves the order keys were added, useful for time-ordered data
- Reinsertion trick: Delete and re-insert a key to move it to the end — an alternative to move_to_end()
- Ordered equality: OrderedDict([("a",1),("b",2)]) != OrderedDict([("b",2),("a",1)]) — order matters for ==
Use Cases
Implementing LRU (Least Recently Used) caches — classic interview problem
Maintaining sorted/ranked collections where order must be preserved
FIFO queue implementations using popitem(last=False)
Order-sensitive configuration where key order has semantic meaning
Working with legacy codebases that rely on OrderedDict guarantees
Common Mistakes
Using OrderedDict when regular dict suffices — adds overhead without benefit in Python 3.7+
Calling move_to_end() on a key that doesn't exist — raises KeyError, check first with "key in od"
Confusing popitem() behavior: OrderedDict pops LIFO by default, use last=False for FIFO
Assuming OrderedDict is faster than dict for ordered iteration — it's actually slightly slower
Not knowing that Python 3.7+ dicts preserve order — many developers still use OrderedDict unnecessarily