Multithreaaded LRU Cache | Notion

✅ What is an LRU Cache?

It stores key-value pairs.
If it exceeds a fixed capacity, it removes the least recently used (LRU) item.
On get(key):
- If present: return value and move it to the front (most recently used).
- If not: return nothing.
On put(key, value):
- If key exists: update value and move it to front.
- If not: add it to front. If size exceeds capacity, remove the least recently used item (from the back).

🧠 Data Structures Used

Structure	Why We Use It
`unordered_map<Key, Node*>`	To find any key in O(1) time
Doubly-linked list	To move nodes to front and remove from back in O(1)
`std::mutex`	To safely allow multiple threads to use the cache

💡 Real-World Analogy

Think of:

unordered_map as a table of contents — quickly finds where a book is.
The doubly-linked list as a queue of readers — when a book is read, move that reader to the front.
If the room is full and someone new comes in, kick out the person who's been sitting longest (at the back).

Now imagine multiple people using the room at the same time — we need to make sure no two people change the list at the same time ⇒ that’s what mutex is for.

✅ How the Code Solves It

Get operation (get(key)):
- Lock the mutex to protect shared data.
- Check if key exists in map:
  - If yes: move it to the front (MRU) and return its value.
  - If no: return nothing.
- Unlock happens automatically when lock guard goes out of scope.