LRU (Least recently used) cache ![test](https://github.com/pmareke/lru-cache/actions/workflows/test.yml/badge.svg)
- This type of cache discards least-recently-used items first.0
- This algorithm requires keeping track of what was used and when.
![LRU Cache](https://camo.githubusercontent.com/ef123cf871a11aecacc217596ee17d97c7044c5b7b29cf50252757c86d124214/68747470733a2f2f6d69726f2e6d656469756d2e636f6d2f76322f726573697a653a6669743a3735332f312a62554a6b51772d664e496b51767552567449386a6c674032782e6a706567)
- The cache should have a capacity.
- The latest element read from the cache should be the most-recently-use item in the cache.
- The
get
function must run in O(1) average time complexity.
Node
: basic unit of information with the value, next and previous.
DoubleLinkedList
: a list with nodes connected in a double way (previuos and next).
LRUCache
: main component, it has a DoubleLinkedList
and hash to stores the Nodes
.
$ bundle install # Install the dependencies
$ rake # Run the tests