LRU (Least Recently Used) cache uklanja stavku na koju se nije pristupalo najduže kada dostigne kapacitet. Klasični dizajn kombinira hash mapu (O(1) lookup) s dvostruko povezanom listom (O(1) preuređivanje), dajući O(1) get i put.
The two-structure design
HashMap: key -> node DLL (recency order):
MRU <-> ... <-> LRU
get/put: map finds node move touched node to front (MRU)
in O(1); DLL splices it evict the tail (LRU) when full
to the front in O(1)
