LRU Cache

Link

Description

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class:

• LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
• int get(int key) Return the value of the key if the key exists, otherwise return -1.
• void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.

The functions get and put must each run in \(O(1)\) average time complexity.

Example 1:

Input:

["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]

Output:

[null, null, null, 1, null, -1, null, -1, 3, 4]

Explanation:

LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // cache is {1=1}
lRUCache.put(2, 2); // cache is {1=1, 2=2}
lRUCache.get(1);    // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.get(2);    // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
lRUCache.get(1);    // return -1 (not found)
lRUCache.get(3);    // return 3
lRUCache.get(4);    // return 4

Constraints:

• 1 <= capacity <= 3000
• 0 <= key <= 10^4
• 0 <= value <= 10^5
• At most 2 * 10^5 calls will be made to get and put.

Solution

Way 1

See reference (Chinese).

struct LinkedNode {
    int key, value;
    LinkedNode* prev;
    LinkedNode* next;

    LinkedNode() : key(0), value(0), prev(nullptr), next(nullptr) {}
    LinkedNode(int _key, int _value) : key(_key), value(_value), prev(nullptr), next(nullptr) {}
};

class LRUCache {
private:
    unordered_map<int, LinkedNode*> cache;
    LinkedNode* head;
    LinkedNode* tail;
    int size;
    int capacity;

    void addToHead(LinkedNode* node) {
        node->prev = head;
        node->next = head->next;
        head->next->prev = node;
        head->next = node;
    }

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

    void moveToHead(LinkedNode* node) {
        removeNode(node);
        addToHead(node);
    }

    LinkedNode* removeTail() {
        LinkedNode* node = tail->prev;
        removeNode(node);
        return node;
    }

public:
    LRUCache(int _capacity) : capacity(_capacity), size(0) {
        head = new LinkedNode();
        tail = new LinkedNode();
        head->next = tail;
        tail->prev = head;
    }

    int get(int key) {
        // if key does not exist, return -1
        if (!cache.count(key)) return -1;
        // if key exists, use hash map to locate, and move to head
        LinkedNode* node = cache[key];
        moveToHead(node);
        return node->value;
    }

    void put(int key, int value) {
        if (!cache.count(key)) {
            // if key does not exist, create a new node
            LinkedNode* node = new LinkedNode(key, value);
            // add to hash map
            cache[key] = node;
            // add to head of double linked list
            addToHead(node);
            size++;

            if (size > capacity) {
                // delete tail node if size is larger than capacity
                LinkedNode* removed = removeTail();
                cache.erase(removed->key);
                delete removed;
                size--;
            }
        } else {
            // if key exists, locate through hash map and move the modified node to head
            LinkedNode* node = cache[key];
            node->value = value;
            moveToHead(node);
        }
    }
};

/**
 * 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);
 */

• Time complexity: \(O(1)\) for get and put;
• Space complexity: \(O(\mathrm{capacity})\).

Analysis:

• Initialization (LRUCache Constructor):
  • Initializes the dummy head and tail and links them. The cache starts empty with a specified capacity.
• Get Operation (get Method):
• If the key exists in the cache, the corresponding node is moved to the head of the list (indicating recent use) and its value is returned.
• If the key is not present, returns -1.
• Put Operation (put Method):
  • If the key is not in the cache, a new node is created and added to the head of the list. If this addition exceeds the capacity, the least recently used item (node before the tail) is removed.
  • If the key exists, its value is updated, and the node is moved to the head.

Note: we may also need to add the following deconstruction method to free the memory:

class LRUCache {
    // ... [rest of the existing code]

    ~LRUCache() {
        LinkedNode* current = head;
        while (current) {
            LinkedNode* temp = current;
            current = current->next;
            delete temp;
        }
    }
};

Way 2

class LRUCache {
private:
    list<pair<int, int>> cache;  // pair[key] == value
    unordered_map<int, list<pair<int, int>>::iterator> keyToNode;
    int capacity;

public:
    LRUCache(int _capacity) : capacity(_capacity) {}

    int get(int key) {
        if (keyToNode.find(key) == keyToNode.end()) return -1;

        auto keyValue = *keyToNode[key];
        cache.erase(keyToNode[key]);
        cache.emplace_front(keyValue);
        keyToNode[key] = cache.begin();

        return keyValue.second;
    }

    void put(int key, int value) {
        if (keyToNode.find(key) != keyToNode.end()) {
            cache.erase(keyToNode[key]);
        } else {
            if (cache.size() == capacity) {
                keyToNode.erase(cache.back().first);
                cache.pop_back();
            }
        }

        cache.emplace_front(key, value);
        keyToNode[key] = cache.begin();
    }
};

/**
 * 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);
 */