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

struct Node {
    int key;
    int val;
    Node* next;
    Node* prev;
    Node(int _key,int _val) :key(_key),val(_val), next(nullptr), prev(nullptr) {}
};

class Solution {
public:
    unordered_map<int, Node*> hash;
    Node* head;
    Node* tail;
    int cap;
    int size;
    Solution(int capacity) {
        // write code here
        size = 0;
        cap = capacity;
        head = nullptr;
        tail = nullptr;
        hash.clear();
    }
    void removetohead(Node* p) {
        if (p == head) {
            return;
        }
        p->prev->next = p->next;
        if (p == tail) {
            tail = p->prev;
        }
        else {
            p->next->prev = p->prev;
        }
        p->prev = nullptr;
        p->next = head;
        head->prev = p;
        head = p;
        return;
    }
    int get(int key) {
        // write code here
        if (hash.find(key) == hash.end()) {
            return -1;
        }
        else {
            removetohead(hash[key]);
            return hash[key]->val;
        }
    }

    void set(int key, int value) {
        // write code here
        if (hash.find(key) != hash.end()) {
            //key已经存在
            hash[key]->val = value;
            removetohead(hash[key]);
        }
        else {
            //key不存在
            if (size < cap) {
                //缓存未满，直接在头部插入
                Node* p = new Node(key,value);
                if (head == nullptr) {
                    head = tail = p;
                }
                else {
                    head->prev = p;
                    p->next = head;
                    head = p;
                }
                hash[key] = head;
                size++;
            }
            else {
                //缓存已满，更新尾，将尾移到头
                int k = tail->key;
                hash.erase(k);
                tail->key = key;
                tail->val = value;
                removetohead(tail);
                hash[key] = head;
            }
        }
    }
};