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.

Medium Python 3.9+ Aug 9, 2026 Dictionaries & sets 14 views 0 copies

Python code

38 lines
Python 3.9+
from 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

stdout
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

  1. Use a plain dict with manual timestamp tracking for older Python versions
  2. 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

Run this sample

Open the browser IDE to tweak the example and see results without installing anything.

Open editor

More from Dictionaries & sets

Related tutorials and quizzes for this topic.