LRU Cache

lru_cache.cpp

class Node {
public:
    int key;
    int val;
    Node *prev;
    Node *next;
    
    Node (int key, int val, Node *prev = NULL, Node *next = NULL) {
        this->key = key;
        this->val = val;
        this->prev = prev;
        this->next = next;
    }
};

class LRUCache{
private:
    int capacity;
    int size;
    Node *head;
    Node *tail;
    unordered_map<int, Node*> key_to_node;
    
    void moveNodeToTail(Node *node) {
        if (!node || node == tail)
            return;
            
        Node *prev = node->prev;
        // detach node
        prev->next = node->next;
        if (node->next)
            node->next->prev = prev;
        
        // move to tail
        node->next = NULL;
        node->prev = tail;
        tail->next = node;
        tail = node;
    }
    
    void appendNode(int key, int value) {
        Node *node = new Node(key, value);
        node->prev = tail;
        tail->next = node;
        tail = node;
        key_to_node[key] = node;
        ++size;    
    }
    
    void deleteHead() {
        // delete when there's at least two nodes
        
        Node *victim = head->next;
        head->next = victim->next;
        if (victim->next)
            victim->next->prev = head;
            
        key_to_node.erase(victim->key);
        delete victim;
        --size;
    }
    
    Node *getNodeByKey(int key) {
        Node *node = NULL;
        if (key_to_node.find(key) != key_to_node.end())
            node = key_to_node[key];
            
        return node;
    }
    
public:
    LRUCache(int capacity) {
        this->capacity = capacity;
        size = 0;
        head = new Node(0, 0);
        tail = head;
    }
    
    int get(int key) {
        Node *node = getNodeByKey(key);
        
        int val = -1;
        if (node) {
            moveNodeToTail(node);
            val = node->val;
        }
        return val;
    }

    void set(int key, int value) {
        Node *node = getNodeByKey(key);
        
        if (node) {
            node->val = value;
            moveNodeToTail(node);
        } else {
            // insert the new node first
            appendNode(key, value);
            
            // remove the first node if necessary
            if (size > capacity)
                deleteHead();
        }
    }
};

lru_cache2.cpp

class LRUCache{
private:
    unordered_map<int, int> values;
    unordered_map<int, long long> last_used_time;
    long long time;
    int capacity;
    
public:
    // @param capacity, an integer
    LRUCache(int capacity) {
        this->time = 0;
        this->capacity = capacity;
    }
    
    // @return an integer
    int get(int key) {
        if (values.find(key) != values.end()) {
            ++time;
            last_used_time[key] = time;
            return values[key];
        }
        
        return -1;
    }

    // @param key, an integer
    // @param value, an integer
    // @return nothing
    void set(int key, int value) {
        ++time;
        if (capacity == values.size() && values.find(key) == values.end()) {
            int victim_key = -1;
            long long min_time = LONG_LONG_MAX;
            
            for (const auto &it: last_used_time) {
                if (it.second < min_time) {
                    victim_key = it.first;
                    min_time = it.second;
                }    
            }
            
            values.erase(victim_key);
            last_used_time.erase(victim_key);
        }
        
        values[key] = value;
        last_used_time[key] = time;
    }
};