LRU Cache

Thought Process

To implement an LRU Cache, we use a combination of a doubly linked list and a hash map. The doubly linked list helps maintain the order of recently used items, while the hash map provides O(1) access to any node. When a 'get' operation is performed, the accessed node is moved to the front of the list to mark it as recently used. For a 'put' operation, if the cache is full, the least recently used node (at the tail) is removed. Finally, the new node is added to the front of the list as the most recent node. This ensures that the cache always maintains the most recently used items within the specified capacity.

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */
    
class LRUCache {
public:
    struct Node{
        int key;
        int val;
        Node *prev;
        Node *next;

        Node(int keey,int vaal){
        key = keey;
        val = vaal;
        prev = NULL;
        next = NULL;
    }
    };
    
    int cap;
    Node *head = new Node(-1,-1);
    Node *tail = new Node(-1,-1);
    map<int,Node*> mp;

    LRUCache(int capacity) {
        cap = capacity;
        head->next = tail;
        tail->prev = head;
    }
    
    void addNode(Node *nod){

        Node *tmp = head->next;

        head->next = nod;
        nod->prev = head;

        nod->next = tmp;
        tmp->prev = nod;
    }

    void removeNode(Node *nod){

        Node *prevv = nod->prev;
        Node *nextt = nod->next;

        prevv->next = nextt;
        nextt->prev = prevv;
    }

    int get(int key) {
        
        if(mp.count(key)){

            Node *nod = mp[key];
            int ans = nod->val;

            removeNode(nod);
            addNode(nod);

            return ans;
        }
        else
            return -1;
    }
    
    void put(int key, int value) {

        // Already present
        if(mp.contains(key)){

            Node *nod = mp[key];
            removeNode(nod);
            mp.erase(key);
            delete nod;
        }

        // Capacity is full
        if(mp.size()==cap){

            Node *nod = tail->prev;
            int key = nod->key;
            mp.erase(key);
            removeNode(nod);
            delete nod;

        }
        Node *nod = new Node(key,value);
        addNode(nod);
        mp.insert({key,nod});
        
    }
};

Code Complexity

Time Complexity: O(1)

Both get and put operations are performed in constant time due to the use of a hash map and a doubly linked list.

Space Complexity: O(capacity)

The space used is proportional to the capacity of the cache, as it stores nodes in both the hash map and the doubly linked list.

C++: LRU Cache

Thought Process

Code Complexity

Time Complexity: O(1)

Space Complexity: O(capacity)