Least Recently Used

LRU (Least Recently Used) is a cache eviction policy: when the cache is full, evict the item that was used longest ago. It assumes temporal locality—recently used items are more likely to be used again. Simple to implement (e.g. doubly linked list + hash map) and often near-optimal in practice for request sequences with locality. Belady's algorithm (evict the page used farthest in the future) is optimal but unrealisable without a crystal ball; LRU is a practical heuristic that performs well when the workload has recency. Used everywhere: CPU caches, CDNs, in-memory caches, and any bounded buffer where you must choose what to keep.

When you have a fixed-size store and must evict something, LRU is the default when recency predicts future use. Implement with O(1) lookup and move-to-front on access. If the workload has different locality (e.g. scan-heavy), consider variants (LRU-K, adaptive) or a different policy. In decisions: "what have we not looked at lately?" often identifies candidates to deprioritise or drop.

LRU evicts the least recently used item when capacity is full. It assumes temporal locality and is easy to implement with O(1) operations. Use it for caches and any bounded buffer where recency predicts future use; tune or replace when the access pattern differs.