LRU Cache in Python
Learn to build an LRU (Least Recently Used) Cache in Python using OrderedDict. A really fun and simple guide to O(1) time complexity caching!
Try it yourself
Run this code directly in your browser. Click "Open in full editor" to experiment further.
Click Run to see output
Or press Ctrl + Enter
How it works
Have you ever wondered how your web browser manages its history without running out of memory? It probably uses an LRU (Least Recently Used) Cache!
How It Works
Imagine your brain as a tiny box that can only hold 3 items at a time.
1. You learn about Apples, Bananas, and Cherries. (Box is full!)
2. Now, you need to learn about Dates. Uh oh, no space!
3. You have to throw something out to make room. An LRU Cache says: "Throw out the thing we haven't thought about in the longest time." Since you learned about Apples first (and haven't thought about them since), Apples get tossed out, and Dates go in!
Why is this tricky?
To be a truly amazing cache, we want to look things up instantly (O(1) time) AND add/remove things instantly (O(1) time).
Python's Elegant Cheat Code
In many programming languages, you have to manually build a complex "Doubly Linked List" combined with a "Hash Map". But Python has a built-in superhero: collections.OrderedDict.
It remembers the exact order you added things, AND it's as fast as a dictionary!
Whenever we look at an item, we just use its built-in move_to_end() function to say "Hey! We just used this! It's important!" and it pops it to the back of the line so it won't get deleted.
If our cache gets too full, we just delete the item at the very front of the line (the least recently used one). So elegant and easy!
Related examples
Two Sum Algorithm in Python
Learn how to solve the classic Two Sum algorithm in Python! An incredibly fun tutorial on using Hash Maps to upgrade your code from slow O(n^2) to blazing fast O(n).
Reverse Linked List in Python
Learn how to reverse a linked list in Python! An easy, fun, beginner-friendly guide to solving this classic coding interview algorithm. Includes O(1) space iterative code.
