GeeksForGeeks - LRU Cache

link

Problem

The task is to design and implement methods of an LRU cache. The class has two methods get() and set() which are defined as follows. get(x) : Returns the value of the key x if the key exists in the cache otherwise returns -1. set(x,y) : inserts the value if the key x is not already present. If the cache reaches its capacity it should invalidate the least recently used item before inserting the new item. In the constructor of the class the size of the cache should be intitialized.

Solution

Use Doubly Linked List and Unordered Map. DLL gives the advantage of removing nodes and changing the order while map can efficiently find if a key exists in the list.

struct Node{
    int key;
  int value;
  Node* next;
  Node* prev;
  
  Node(int key, int value):key(key), value(value){}
};

class LRUCache
{
private:
    Node* last;
    Node* first;
    unordered_map<int, Node*> map;
    int size;

public:
    LRUCache(int cap):size(cap)
    {}
    
     int get(int key)
    {
        // this function should return value corresponding to key
        auto it = map.find(key);
        if(it != map.end()){
            Node* cur = it->second;
            if(cur->prev){
                (cur->prev)->next = cur->next;    
            }
            if(cur->next){
                (cur->next)->prev = cur->prev;    
            }
            cur->next = first;
            first->prev = cur;
            first = cur;
            return (it->second)->value;
        }
        return -1;
    }
    
     void set(int key, int value)
    {
        // storing key, value pair
        
        auto it = map.find(key);
        if(it == map.end()){
            if(map.size() == size){
                int rem_key = first->key;
                auto it = map.find(rem_key);
                if(first->next){
                    (first->next)->prev = nullptr;    
                }
                first = first->next;
                map.erase(it);
            }
            Node* n = new Node(key, value);
            last->next = n;
            n->prev = last;
            last = n;
            if(!first){
                first = n;
            }
            map.insert(pair<int,Node*>(key, n));
        }else{
            Node* n = it->second;
            if(n->prev){
                (n->prev)->next = n->next;
            }
            if(n->next){
                (n->next)->prev = n->prev;
            }
            last->next = n;
            n->prev = last;
            last = n;
            if(first == n && map.size() > 1){
                first = n->next;
            }
        }
    }
};