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

struct DNode{
  
    int key;
    int val ;
    DNode* next;
    DNode* pre;
    DNode():key(0),val(0),next(nullptr),pre(nullptr){}
    DNode(int k,int v) : key(k), val(v),next(nullptr),pre(nullptr){}
};

class Solution {
public:
    
    int default_capacity;
    DNode* head;
    DNode* tail;
    unordered_map<int,DNode*> cache;
    
    Solution(int capacity){
         // write code here
        default_capacity = capacity;
        head = new DNode();
        tail = new DNode();
        head->next = tail;
        tail->next = head;
    }
    
    void update(DNode* node){
        remove(node);
        addToHead(node);
    }
    
    void remove(DNode* node){
        node->pre->next = node->next;
        node->next->pre = node->pre;
    }
    
    void addToHead(DNode* node){
        node->next = head->next;
        head->next->pre = node;
        node->pre = head;
        head->next = node;
    }
    
    int get(int key) {
         
        // if cache contains the key
        if(cache.count(key)){
            DNode* res_node = cache[key];
            update(res_node);
            return res_node->val;
        }
        else{
            return -1;
        }
    }
    
    void set(int key, int value){
         
        // if cache contains the key
        if(cache.count(key)){
            DNode* exist_node = cache[key];
            exist_node->val = value;
            update(exist_node);
        }
        else{
            DNode* new_node = new DNode(key,value);
            addToHead(new_node);
            cache[key] = new_node;
            // overflow occurs after addToHead
            if(cache.size()>default_capacity){
                DNode* del_node = tail->pre;
                remove(del_node);
                cache.erase(del_node->key);
            }
        }
    }
};

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