annanya-mathur/lru-cache

LRU stands for least recently used

LRU-CACHE

Data Structure Used :- Doubly-Linked List and Hash Map.
Cache:- It is the fastest memory which is smaller in size and expensive . It has a fixed size.

---

It is real life data structure application. It is used for fast interaction between server and client:-
Implementing the LRU cache data structure , will allow the following operation in O(1).

• Insert (key , value)
• getvalue (key)
• getmostrecentlyused ()

---

Max Size Property:-

It represents the max key-value pairs that can be stored inside the cache at a time.
If key-value pair has to be inserted into the cache when cache is full then the least recently used key-value pair should be deleted, then only new pair will be inserted.
If key-value pair to be inserted already exist in cache, then simply update the value of key with new value.

---

Implementation:- LRU cache is implemented using doubly linked list storing key-value pair and unordered-map storing key along with its address.
Insert operation has 3 cases:-

1. If cache hits, then check and update the value of key.
2. If cache miss , then insert the key-value pair in cache at the top if cache is not full.
3. If cache miss and cache is full, insert key-value pair at the top and remove key-value which is LRU.