题解 | #设计LRU缓存结构#

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

class Solution {
//双向链表 + 哈希表
private:
    unordered_map<int, DoubleLinkedNode*> cache;
    DoubleLinkedNode* head;
    DoubleLinkedNode* tail;
    int size;
    int capacity;
public:
    Solution(int _capacity) : capacity(_capacity), size(0) { //初始化列表
         // write code here       
        head = new DoubleLinkedNode();
        tail = new DoubleLinkedNode();
        head->next = tail;
        tail->prev = head;
    }
    
    int get(int key) {
         // write code here
        if(!cache.count(key)){
            return -1;
        }
        //找到其在哈希表中位置，移到头部
        DoubleLinkedNode* node = cache[key];
        removeToHead(node);
        return node->value;
    }
    
    void set(int key, int value){
         // write code here
        if(/*cache.find(key) == cache.end()*/!cache.count(key)){
            //不存在，新建
            DoubleLinkedNode* node = new DoubleLinkedNode(key, value);
            //存入哈希表
            cache[key] = node;
            //添加到头部
            addToHead(node);
            //更新size
            ++size;
            if(size > capacity){
                //如果超出容量 删除双向链表的最后一个节点
                DoubleLinkedNode* removed = removeTail();
                //删除哈希表中对应的项
                cache.erase(removed->key);
                //防止内存泄漏
                delete removed;
                --size;
            }
        }
        else{
            //存在 找到其在哈希表中位置，更新值，移到头部
            DoubleLinkedNode* node = cache[key];
            node->value = value;
            removeToHead(node);
        }
    }
    
    void addToHead(DoubleLinkedNode* Node){
        Node->prev = head;
        Node->next = head->next;
        head->next->prev = Node;
        head->next = Node;
    }
    
    void removeNode(DoubleLinkedNode* Node){
        Node->prev->next = Node->next;
        Node->next->prev = Node->prev;      
    }
    
    void removeToHead(DoubleLinkedNode* Node){
        removeNode(Node);
        addToHead(Node);
    }
    
    DoubleLinkedNode* removeTail(){
        DoubleLinkedNode* node = tail->prev;
        removeNode(node);
        return node;
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* solution = new Solution(capacity);
 * int output = solution->get(key);
 * solution->set(key,value);
 */