LRU cache

A fixed-size cache that, when full, throws out the entry that has gone unused the longest.

In more detail

The classic implementation combines a dict, for O(1) lookup, with a doubly linked list kept in order of use, for O(1) moves and evictions. Every hit moves an entry to the front; every insert past capacity drops the entry at the back. Python's functools.lru_cache applies this to function results.

Related terms

Taught in

References