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

双向链表

class Solution {
private:
    struct LinkNode{
        int key;
        int val;
        LinkNode* pre;
        LinkNode* next;
        LinkNode(int _key, int _val){
            key = _key;
            val = _val;
            pre = next = NULL;
        }
    };
    int CAPACITY = 0;
    int size = 0;
    LinkNode* head = new LinkNode(-1, -1);
    LinkNode* tail = new LinkNode(-1, -1);
    unordered_map<int, LinkNode*> keyToNode;
    
    void moveToHead(LinkNode* node){
        node -> next -> pre = node -> pre;
        node -> pre -> next = node -> next;
        
        node -> next = head -> next;
        head -> next -> pre = node;
        head -> next = node;
        node -> pre = head;
    }
public:
    Solution(int capacity){
         // write code here
        CAPACITY = capacity;
        size = 0;
        head -> next = tail;
        tail -> pre = head;
    }
    
    int get(int key) {
         // write code here
        if(keyToNode.count(key)){
            moveToHead(keyToNode[key]);
            return keyToNode[key] -> val;
        }else{
            return -1;
        }
    }
    
    void set(int key, int value){
         // write code here
        if(keyToNode.count(key)){
            keyToNode[key] -> val = value;
            moveToHead(keyToNode[key]);
        }else{
            if(size == CAPACITY){
                LinkNode* node = tail -> pre;
                keyToNode.erase(node -> key);
                keyToNode[key] = node;
                node -> key = key;
                node -> val = value;
                moveToHead(node);
            }else{
                LinkNode* node = new LinkNode(key, value);
                keyToNode[key] = node;
                
                node -> next = head -> next;
                head -> next -> pre = node;
                head -> next = node;
                node -> pre = head;
                
                size ++;
                
            }
        }
    }
};

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