LRU Cache with OrderedDict in Python
Implement an LRU cache using collections.OrderedDict to track insertion order and evict the least-recently-used item when capacity is exceeded.
Python code
38 linesfrom collections import OrderedDict
class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
self.cache = OrderedDict()
def get(self, key):
if key not in self.cache:
return -1
self.cache.move_to_end(key)
return self.cache[key]
def put(self, key, value):
if key in self.cache:
self.cache.move_to_end(key)
self.cache[key] = value
if len(self.cache) > self.capacity:
self.cache.popitem(last=False)
if __name__ == "__main__":
cache = LRUCache(3)
for i in range(1, 6):
cache.put(f"key{i}", i * 10)
print("After inserting 5 items into capacity-3 cache:")
for k, v in cache.cache.items():
print(f"{k}: {v}")
cache.get("key4")
print("\nAfter accessing 'key4' (moved to most recent):")
for k, v in cache.cache.items():
print(f"{k}: {v}")
cache.put("key6", 60)
print("\nAfter inserting 'key6' (evicts least recently used):")
for k, v in cache.cache.items():
print(f"{k}: {v}")
Output
After inserting 5 items into capacity-3 cache:
key3: 30
key4: 40
key5: 50
After accessing 'key4' (moved to most recent):
key3: 30
key5: 50
key4: 40
After inserting 'key6' (evicts least recently used):
key5: 50
key4: 40
key6: 60
How it works
The OrderedDict preserves insertion order and provides move_to_end() to update recency, plus popitem(last=False) to remove the oldest entry. On get(), the key is moved to the end to mark it as most recently used. On put(), existing keys are moved to the end before updating, and if capacity is exceeded, the least-recently-used item (at the front) is evicted. This makes the implementation O(1) for both get and put operations. The demo shows how insertion and access order affect eviction.
Common mistakes
- forgetting to call move_to_end on existing keys in put()
- using popitem() without last=False, which removes the most recent item instead
- not checking if key exists before moving in get(), leading to KeyError
Variations
- Use a plain dict with manual timestamp tracking for older Python versions
- Implement with a doubly linked list and hash map for explicit control
Real-world use cases
- Caching API responses in a web server to reduce external network calls.
- Storing recently accessed database query results to speed up repeated lookups.
- Keeping frequently used configuration objects in memory while limiting memory usage.
Sponsored
More from Dictionaries & sets
- Build a Case-Insensitive Dict with a Wrapper Class in Python medium
- Build a defaultdict histogram of categories in Python easy
- Build adjacency dict graph from edges in Python easy
- Build an OrderedDict insertion order demo in Python 3 easy
- Check Invertible Mapping for Duplicate Values in Python easy
- Compare Two Dictionaries in Python easy
Keep learning
Related tutorials and quizzes for this topic.