A LRU cache is a special kind of cache that defines the way of evicting item from the cache when it is full. Its policy is to evict the least recently used item.
For example,
- a cache having capacity of 4 and is currently storing
[[1, '101'], [2, '102'], [3, '103'], [4, '104']],- where the 1st (leftmost) item [1, '101'] is the least recently used and
- the last (rightmost) item [4, '104'] is the most recently used.
- When the item [2, '102'] is accessed,
- the cache becomes 1, '101'], [3, '103'], [4, '104'], [2, '102' as the item [2, '102'] becomes the most recently used.
- When another item [10, '110'] is pushed into the cache,
- the cache cannot hold all of the items and
- must evict the least recently used item which is [1, '101'] and
- the cache becomes 3, '103'], [4, '104'], [2, '102'], [10, '110'.