146. LRU Cache

146. LRU Cache

class LRUCache {
public:
    LRUCache(int capacity): capacity(capacity), head(new Node()), tail(new Node()) {
        head->post = tail;
        head->prev = nullptr;
        tail->prev = head;
        tail->post = nullptr;
    }
    
    int get(int key) {
        if(cache.find(key) != cache.end())
        {
            moveNodeToHead(cache[key]);
            return cache[key]->val;
        }
        else
            return -1;
    }
    
    void put(int key, int value) {
        if(cache.find(key) == cache.end())
        {
            if(cache.size() > capacity - 1)
                cache.erase(removeTailNode());
            Node* node = new Node(key, value);
            addNodeToHead(node);
            cache[key] = node;
        }else
        {
            auto node = cache[key];
            if(node->val != value)
                node->val = value;
            moveNodeToHead(node);
        }
    }
private:
    struct Node {
        int key;
        int val;
        Node* prev;
        Node* post;
        Node() = default;
        Node(int key, int val): key(key), val(val) {}
    };
    void removeNode(Node* node)
    {
        node->prev->post = node->post;
        node->post->prev = node->prev;
    }
    void addNodeToHead(Node* node)
    {
        node->prev = head;
        node->post = head->post;
        head->post = node;
        node->post->prev = node;
    }
    void moveNodeToHead(Node* node)
    {
        removeNode(node);
        addNodeToHead(node);
    }
    int removeTailNode()
    {
        auto node = tail->prev;
        tail->prev = node->prev;
        tail->prev->post = tail;
        auto key = node->key;
        delete node;
        return key;
    }
    Node* head;
    Node* tail;
    int capacity;
    unordered_map<int, Node*> cache;
};

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

使用doubleLinkedList是因为在删除时候需要操作前面的元素，因此DoublelinkedList可以实现O(1)的删除操作，而SingleLinkedList就需要O(n)
总体思路是访问过的移动到第一位，而最少访问的放在最后，如果新进来的时候缓存满了，那么就释放掉最后一位。