class LRUCache {
public:
    struct Node {
        int key, val;
        Node *prior, *next;
        Node(int _key, int _val): key(_key), val(_val), prior(NULL), next(NULL) {}
    }*L, *R;
    unordered_map<int, Node*> mp;
    int n;

    void del(Node* p) 
    {
        p->prior->next = p->next;
        p->next->prior = p->prior;
    }

    void ins(Node* p)
    {
        p->next = L->next;
        p->prior = L;
        L->next->prior = p;
        L->next = p;
    }

    LRUCache(int capacity) 
    {
        n = capacity;
        L = new Node(-1, -1), R = new Node(-1, -1);
        L->next = R, R->prior = L;
    }

    int get(int key) 
    {
        if (!mp.count(key)) return -1;
        auto p = mp[key];
        // 已访问过节点p
        del(p);     // 在链表中删除该节点
        ins(p);     // 将该节点插入到表头
        return p->val;
    }

    void put(int key, int value) 
    {
        if (mp.count(key)) 
        {
            auto p = mp[key];
            p->val = value;     // 修改其数据
            // 已访问过节点p
            del(p);
            ins(p);
        } 
        else 
        {
            if (mp.size() == n)     // 缓存容量已满
            {
                auto p = R->prior;  // 链表末尾的那个节点就是 最近最少使用的节点 
                // 删除该 最近最少使用的节点 
                del(p);
                // 同时在哈希表中删除该节点
                mp.erase(p->key);
                delete p;       // 释放该节点内存  写不写都无所谓
            }
            auto p = new Node(key, value);
            mp[key] = p;
            // 将新节点插入到链表中
            ins(p);
        }
    }
};