Least Recently Used Cache

Description:

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1. put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

Follow up: Could you do both operations in O(1) time complexity?

Solution

Least Recently Used (LRU) Cache follows an eviction policy where the item that was least recently used is evicted when the cache becomes full. The general technique is to use a doubly-linked list and a hashmap/unordered_map. The cache takes keys and values, where the hashmap can find the value in O(1) by mapping the keys to the pointers of the nodes in the linked list which store the value. Each time a key-value pair is accessed, that node is moved to the head (also done in O(1) because of the finding the node is O(1) with the hashmap and the deletion and insertion are O(1) in a doubly linked list. Evict tail node when size is equal to capacity.

My Code

C++ (Self Implemented Doubly-Linked List)

class LRUCache {

    template <class T> class LRU {
        private:
            struct Node {
                int key;
                T value;
                Node* next;
                Node* prev;
                Node() {}
                Node(int key, T value) {
                    this->key = key;
                    this->value = value;
                }
            };
        
        public:
            int size;
            int capacity;
            unordered_map<int, Node*> cache;
            Node head;
            Node tail;
            T invalid;

        public:
            LRU() {}
            LRU(int capacity, T invalid) {
                size = 0;
                this->capacity = capacity;
                head.next = &tail;
                head.prev = NULL;
                tail.next = NULL;
                tail.prev = &head;
                this->invalid = invalid;
            }

        private:
            void add(int key, T value) {
                if (size == capacity) { // Max Size, Key DNE, Evict LRU
                    cache.erase(tail.prev->key);
                    tail.prev = tail.prev->prev;
                    tail.prev->next = &tail;
                } else {
                    size++;
                }

                Node* nodePtr = new Node(key, value);
                cache.insert(make_pair(key, nodePtr));
                
                nodePtr->next = head.next;
                nodePtr->prev = &head;
                nodePtr->next->prev = nodePtr;
                head.next = nodePtr;
            }

            void moveToHead(int key) {
                Node* nodePtr = cache.at(key);

                // Remove Node (link next and prev nodes)
                Node* nextNodePtr = nodePtr->next;
                Node* prevNodePtr = nodePtr->prev;
                prevNodePtr->next = nextNodePtr;
                nextNodePtr->prev = prevNodePtr;

                // Link to head.next
                nodePtr->next = head.next;
                head.next->prev = nodePtr;

                // Link to head
                nodePtr->prev = &head;
                head.next = nodePtr;
            }

        public:
            T get(int key) {
               if (!cache.count(key)) {
                   return invalid; // change to -1
               }
               moveToHead(key);
               return cache.at(key)->value;
            }

            void put(int key, T value) {
                if (!cache.count(key)) {
                    add(key, value);
                } else {
                    cache.at(key)->value = value;
                    moveToHead(key);
                }
            }
    };

public:
    LRUCache(int capacity) {
        lru = new LRU<int>(capacity, -1);
    }
    
    int get(int key) {
        return lru->get(key);
    }
    
    void put(int key, int value) {
        lru->put(key, value);
    }

private:
    LRU<int>* lru;
    
};

Code Blog Wasif Islam

Least Recently Used Cache