What is LRU caching and how can I implement it in Python?

What is LRU caching and how can I implement it in Python?

LRU stands for Least Recently Used. It's a caching algorithm that removes the least recently used items first. In Python, you can implement it using a dictionary and a doubly linked list.

Can you show me a simple implementation?

Sure! Here's a basic example using a class:

class LRUCache:
    def __init__(self, capacity: int):
        self.cache = {}  # key: value
        self.capacity = capacity
        self.order = []  # to track the order of usage

    def get(self, key: int) -> int:
        if key in self.cache:
            self.order.remove(key)
            self.order.append(key)
            return self.cache[key]
        return -1

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.order.remove(key)
        elif len(self.cache) >= self.capacity:
            oldest = self.order.pop(0)
            del self.cache[oldest]
        self.cache[key] = value
        self.order.append(key)

How does this implementation handle capacity?

The put method checks if the cache has reached its capacity. If it has, it removes the oldest item (the first item in the order list) before adding the new item.