代码

class Node {
public:
    int key, val;
    Node *prev, *next;

    Node(int _key, int _val) : key(_key), val(_val), prev(NULL), next(NULL) {};
};



class LRUCache {
public:
    unordered_map<int, Node*> hash;
    Node *L, *R;
    int n;

    // 删除双链表中的节点
    void remove(Node* node) {
        node->next->prev = node->prev;
        node->prev->next = node->next;
    }

    // 插入节点到双链表中
    void insert(Node* node) {
        node->next = L->next;
        node->prev = L;
        L->next = node;
        node->next->prev = node;
    }

    // 初始化 LRU
    LRUCache(int capacity) {
        n = capacity;
        L = new Node(-1, -1);
        R = new Node(-1, -1);
        L->next = R;
        R->prev = L;
    }

    int get(int key) {
        if (!hash.count(key)) return -1;
        auto node = hash[key];
        remove(node);
        insert(node);
        return node->val;
    }

    void put(int key, int value) {
        if (hash.count(key)) {
            auto node = hash[key];
            node->val = value;
            remove(node);
            insert(node);
        } else {
            // 删除双链表最右端较长时间没有使用的节点
            if (hash.size() == n) {
                auto node = R->prev;
                remove(node);
                hash.erase(node->key);
                delete node;
            }
            auto node = new Node(key, value);
            hash[key] = node;
            insert(node);
        }
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */