DSA Design: LRU Cache Implementation

Least Recently Used (LRU) Cache is a common interview problem requiring O(1) time for both get() and put() operations.

The Data Structure

To achieve O(1) for both, we combine two data structures:

1. Doubly Linked List (DLL): To maintain the order of access. Head is Most Recently Used, Tail is Least Recently Used.
2. Hash Map: To map keys to the corresponding Node in the DLL for O(1) access.

Implementation Logic

struct Node {
    int key, val;
    Node *prev, *next;
};

// get(key):
// 1. Look up in HashMap.
// 2. If present, move the Node to the Head of DLL. Return value.

// put(key, value):
// 1. If key exists, update value and move Node to Head.
// 2. If key is new:
//    - If at capacity, remove Tail of DLL and delete from HashMap.
//    - Create new Node at Head and add to HashMap.

Complexity: Time O(1) for all ops. Space O(Capacity) for storage.