题解 | #设计LRU缓存结构#手写双向链表

struct List_Node {
   int key, value;
    List_Node *pre;
    List_Node *next;
    List_Node(int a = 0, int b = 0) : key(a), value(b), pre(nullptr), next(nullptr) {}
};

class Solution {
private:
    int n, capacity_;
    List_Node *head;
    List_Node *tail;
    unordered_map <int, List_Node *> ss;

public:
    vector <int> ans;

    List_Node *DelTail() {
        List_Node *p = tail->pre;
        DelNode(p);
        return p;
    }

    void DelNode(List_Node *p) {
        p->pre->next = p->next;
        p->next->pre = p->pre;
        return ;
    }

    void AddToHead(List_Node *p) {
        p->next = head->next;
        p->next->pre = p;
        head->next = p;
        p->pre = head;
        return ;
    }

    void MoveToHead(List_Node *p) {
        DelNode(p);
        AddToHead(p);
        return ;
    }

    void get(int key) {
        if(!ss.count(key)) ans.push_back(-1);
        else {
            MoveToHead(ss[key]);
            ans.push_back(ss[key]->value);
        }
        return ;
    }

    void set(int key, int value) {
        if(!ss.count(key)) {
            List_Node *p = new List_Node(key, value);
            ss[key] = p;
            AddToHead(p);
            n++;
            if(n > capacity_) {
                List_Node *q = DelTail();
                ss.erase(q->key);
                n--;
            }
        } else {
            MoveToHead(ss[key]);
            ss[key]->value = value;
        }
        return ;
    }

    vector<int> LRU(vector<vector<int> >& operators, int k) {
        n = 0, capacity_ = k;
        head = new List_Node();
        tail = new List_Node();
        head->next = tail;
        tail->pre =  head;
        for(auto &c : operators) {
            if(c[0] == 1) set(c[1], c[2]);
            else get(c[1]);
        }
        return ans;
    }
};