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

哈希表：管理存在的数据

双向链表：管理数据的优先级。使用双向链表的原因是要进行头插入、尾删除和删除中间某个节点。

class Node {
public:
    int key_, val_;
    Node *pre_, *next_;
    Node(int key, int val, Node *pre = nullptr, Node *next = nullptr)
    : key_(key), val_(val), pre_(pre), next_(next) {}
};

class Solution {
    int size;
    Node *head, *tail;
    unordered_map<int, Node*> umap;
public:
    Solution(int capacity)
    : head(new Node(-1, -1)), tail(new Node(-1, -1)) {
        size = capacity;
        head->next_ = tail;
        tail->pre_ = head;
    }

    void movetohead(Node *node) {
        if(node->pre_ == head) return;
        if(node->pre_) node->pre_->next_ = node->next_;
        if(node->next_) node->next_->pre_ = node->pre_;

        node->pre_ = head;
        node->next_ = head->next_;
        head->next_->pre_ = node;
        head->next_ = node;
    }

    int get(int key) {
        auto it = umap.begin();
        if((it = umap.find(key)) == umap.end()) return -1;
        movetohead(it->second);
        return it->second->val_;
    }

    void set(int key, int value){
        auto it = umap.begin();
        if((it = umap.find(key)) != umap.end()) {
            it->second->val_ = value;
            movetohead(it->second);
        } else {
            Node *newnode = new Node(key, value);
            movetohead(newnode);
            umap[key] = newnode;
            if(size > 0) size--;
            else {
                Node *temp = tail->pre_;
                cout << temp->val_ << endl;
                tail->pre_ = temp->pre_;
                temp->pre_->next_ = tail;
                umap.erase(temp->key_);
                delete temp;
            }
        }
    }
};