LRU Caches: Constant-Time Eviction for Real Systems

An LRU (Least Recently Used) cache is a data store with a fixed capacity that tracks when each entry was last accessed. When the cache is full and new data arrives, the cache makes room by removing the entry that has gone unused for the longest time. This removal rule is called the eviction policy, and LRU is the most widely used one because data that was needed recently tends to be needed again.

We have already covered the two ingredients separately on this blog: HashMaps give us constant-time lookup by key, and linked lists give us constant-time reordering. An LRU cache is the classic payoff for learning both, because it needs each structure to cover the other one's weakness. This post builds one from those parts, shows the short version JavaScript gives you almost for free, and finishes with the workloads where LRU is the wrong choice.