LRU (Least Recently Used) cache inaondoa kipengele ambacho hakikuzoishi kwa muda mrefu zaidi wakati inapofikia uwezo wake. Muundo wa kawaida unachanganya hash map (O(1) lookup) na orodha iliyounganisha mara mbili (O(1) upya), ukitoa O(1) get na put.
Muundo wa miundo miwili
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)
