LRU Cache

LRU Cache: Get & Put

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.cap = 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.cap:
            self.cache.popitem(last=False)

cache = LRUCache(3)
cache.put(1, 'a')
cache.put(2, 'b')
cache.put(3, 'c')
print(cache.get(1))    # a  (1 becomes most recent)
cache.put(4, 'd')      # evicts key 2 (least recent)
print(cache.get(2))    # -1 (evicted)
print(cache.get(4))    # d

Output

a
-1
d

The data structure combination

The doubly linked list keeps items in order of recency. The head holds the most recently used item; the tail holds the least recently used. Moving a node to the head or removing the tail node both take \(O(1)\) with a doubly linked list.

The hash map maps each key directly to its node in the linked list. This gives \(O(1)\) lookup — no need to scan the list to find a key.

get(key)

Look up the key in the hash map. If absent, return -1.
If found, move that node to the head of the list (mark it as most recently used).
Return its value.

put(key, value)

If the key already exists, update its value and move it to the head.
If the key is new: create a new node, add it to the head, and store it in the hash map.
If the cache is now over capacity: remove the node at the tail and delete its key from the hash map.

Sentinel nodes

A clean implementation uses two dummy nodes — a permanent head sentinel and a permanent tail sentinel. Real nodes live between them. This avoids null-pointer edge cases when inserting or removing the first/last real node.

LRU Cache: Hit Rate Simulation

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.cache = OrderedDict()
    def get(self, key):
        if key not in self.cache: return None
        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.cap: self.cache.popitem(last=False)

requests = [1, 2, 3, 1, 4, 2, 5, 1]
cache = LRUCache(3)
hits = 0
for key in requests:
    if cache.get(key) is not None:
        hits += 1
    else:
        cache.put(key, key)
print(f"Hit rate: {hits}/{len(requests)} = {hits/len(requests):.0%}")