LRU Cache (Least Recently Used)

one of the cache eviction policy is lru. least recently used.

this is one of the widest used cache eviction policies of all.

you can implement it in a basic way here: leetcode 146.

note: the below explanation is limited to the above problem description.

Thought process:

requirements:

we need to store key-value pairs. obviously.
there are two methods, one is get and another is put.
parameters for the get function is a key.
parameters for the put function is a key and a value.
we need to do both these operations on average $O(1)$ complexity.
also, whenever the capacity is reached for the whatever the data structure we are maintaining, we need to remove the least recently used key-value pair from the data structure. this is nothing but cache eviction policy.

immediate things to notice:

whenever the get function is called, we need to update that key as the recently used one as it is just been used.
same goes with put function, whenever the put is used, we update the key-"new value" pair as the recently used one as it is just been used.
also, when the capacity is reached, we have to remove the least recently used one. in order for the operation to work in $O(1)$ , we need to have an immediate access to the least recently used element.

Intuition:

what if we need to have is a pointer always pointing to the least recently used element.
also, to the most recently used element, because we have to move the middle elements to last when we update their value or we have to add new key-value pairs pointers to the last.
also, we should be able to remove a pointer in the middle without knowing the previous and the next pointers properly.
so, the immediate data structure we can use are a hash map to store the key-value pairs and a linked list. more specifically, a doubly linked list that allows us to remove any element from the middle if we just know the pointer to that element.
one more thing to consider is, we need to store the pointer pointing to the linked list node as the value in the hash map which is having both the key and the value. this is a proper way to store because when the capacity is reached we have to remove the least recently used. but, the lru reference point for us is only from the linked list. so, from the linked list, we will get to know the key and we will remove the key from the hash map.
and we can store the value also in the hash map but, it is unnecessary as we are pointing our linked list node from the key in the hash map and that already contains the value.

structure:

we will have a hash map which is having key as our key and the value as the pointer to the linked list node containing both the key and the value. the linked list node also contains the previous and the next pointers
one more thing to do here to make the design concise is that, have a dummy head and a dummy tail.
(dummy head -> next) stores our least recently used and the (dummy tail -> prev) stores our recently used
everything in between are the remaining nodes storing key value pairs.
this allows us to avoid the extra conditions we need to keep in order to check for empty lists and lists with only a single element.

important things:

we chose a hash map to store the key-value pairs and retrieve them in O(1) average time
we chose a linked list here to get a pointer directly pointing to both least recently used and most recently used
we chose a doubly linked list in order to easily remove a middle node so that we can make it the most recently used one without any extra computation
we are having extra dummy head and dummy tail to make our design concise and also to avoid the extra conditions we need to keep to maintain the list with no nodes or only a single node

Code:

class Node {
public:
    int key;
    int val;
    Node* next;
    Node* prev;
    Node() : key(0), val(0), next(nullptr), prev(nullptr) {};
    Node(int key, int val) : key(key), val(val), next(nullptr), prev(nullptr) {};
};

class LRUCache {
    unordered_map<int, Node*> mp;
    int capacity;
    Node* head; 
    Node* tail;

    void removeNode(Node* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }

    void addBeforeTheTail(Node* node) {
        node->prev = tail->prev; 
        node->next = tail;
        tail->prev->next = node;
        tail->prev = node;
    }
public:
    LRUCache(int capacity) {
        this->capacity = capacity;
        this->head = new Node(); 
        this->tail = new Node();
        head->next = tail;
        tail->prev = head;
    }

    int get(int key) {
        if (!mp.count(key)) return -1;
        Node* curr = mp[key];
        removeNode(curr);
        addBeforeTheTail(curr);
        return curr->val;
    }

    void put(int key, int value) {
        if (mp.count(key)) {
            Node* curr = mp[key];
            curr->val = value;
            removeNode(curr);
            addBeforeTheTail(curr);
        } else {
            if (mp.size() == capacity) {
                Node* lru = head->next;
                removeNode(lru);
                mp.erase(lru->key);
                delete lru;
            }

            Node* curr = new Node(key, value);
            addBeforeTheTail(curr);
            mp[key] = curr;
        }
    }
};

good luck!