LRU (Least Recently Used) usuwa element, którego najdłużej nie używano. Typowa implementacja w O(1): HashMap do lookupu key→węzeł + lista dwukierunkowa, aby po użyciu przesuwać element na początek i usuwać z końca.
type Node = { key: string; prev?: Node; next?: Node }
// idea:
// map: key -> node
// list: head <-> ... <-> tail
// get(key): move node to head (O(1))
// put(key): insert/move to head; if over capacity, evict tail (O(1))
Odpowiedź zaawansowana
Głębiej
Rozwinięcie krótkiej odpowiedzi — co zwykle ma znaczenie w praktyce: