题解 | 设计LRU缓存结构

struct doublelist {    //构建双指针结构，其中有一个哈希表的键，用于删除时，找到哈希表中的元素
    doublelist* back = nullptr;         //用ListNode会与默认的已经设置好的LIstNode重定义；
    doublelist* next = nullptr;  
    int val, key_back;
    doublelist(int value, int key): val(value), key_back(key){}  //列表初始化，使用（）
};

class Solution {
  private:
    int cap;
    int size = 0;    //记录目前大小，判断容量是否已满，则删
    unordered_map<int, doublelist*> store1;
    doublelist *head = new doublelist(0, -1);  //链表的前后顺序表示最近使用，使用一次放在表头；
    doublelist *tail = new doublelist(0, -1);  //因为要在链头添加，链尾删除，则需要头尾节点方便操作

  public:
    Solution(int capacity) {
        cap = capacity;
        head->next = tail;
        tail->back = head;   //类的成员变量初始化只能在构造函数中做，不能直接在类体中写“逻辑代码”。
    }

    int get(int key) {
        if (store1.find(key) != store1.end()) {  //找到了，则移动：缝补，添加
            doublelist* node = (*store1.find(key)).second;
            int val = node->val;

            node->back->next = node->next;
            node->next->back = node->back;

            node->next = head->next;
            node->back = head;
            node->next->back = node;
            head->next = node; 
            return val;
        } else {
            return -1;
        }
    }

    void set(int key, int value) {
        if(store1.find(key) != store1.end()){
            (*store1.find(key)).second->val = value;  //哈希表找到链表，修改值
        }else{
            if(size == cap){
                store1.erase(tail->back->key_back);  //先删除哈希表中的记录，链表找到哈希表

                tail->back = tail->back->back;
                tail->back->next = tail;
                --size;
            }
            store1[key] = new doublelist(value, key); //添加元素，哈希表到链表

            auto newnode = store1[key];  //头添加
            newnode->next = head->next;
            newnode->back = head;
            newnode->next->back = newnode;
            head->next = newnode;
            ++size;  //大小+1；
        }
    }
};

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