使用双链表+哈希表实现，之所以不用单链表，是因为在实现删除节点的操作时双链表只需要$O(1)$的时间复杂度。

class LRUCache {
public:
    struct Node     //构造双链表结构体
    {
        int key, val;
        Node *left, *right;
        Node(int _key, int _val):key(_key), val(_val), left(nullptr), right(nullptr){}
    }*L, *R;

    unordered_map<int, Node*> hash;     //哈希表的键是val，值是结构体Node，即（key, val）键值对
    int n;                              //n表示哈希表的容量大小

    LRUCache(int capacity) {
        n = capacity;
        L = new Node(-1, -1), R = new Node(-1, -1);     //初始化双链表的两个哨兵节点
        L->right = R, R->left = L;                      //哨兵节点最初互相指向
    }

    void remove(Node* p)                //删除一个节点
    {
        p->left->right = p->right;
        p->right->left = p->left;   
        //注意这里不能delete p，因为p节点并不是真的删除掉不用了
        //可能仅仅只是从当前的位置中抽离出来，会再放到双链表头部
    }

    void insert(Node* p)                //在双链表头部插入一个节点
    {
        p->left = L;
        p->right = L->right;
        L->right->left = p;
        L->right = p;
    }

    int get(int key) {
        if (!hash.count(key)) return -1;

        Node* p = hash[key];
        remove(p);                      //删除又插入等于更新该节点到链表头部
        insert(p);
        return p->val;
    }

    void put(int key, int value) {
        if (hash.count(key))            //若待插入值已存在
        {
            Node* p = hash[key];
            p->val = value;             //则更新其值
            remove(p);
            insert(p);
        }
        else                            //若待插入值不存在，分两种情况
        {
            if (hash.size() == n)       //1.若哈希表已满，则删除链表尾元素再插入
            {
                Node* p = R->left;
                remove(p);
                hash.erase(p->key);
                delete p;
            }                           //2.若哈希表未满，构造新节点直接插入
            Node* p = new Node(key, value);
            hash[key] = p;
            insert(p);
        }
    }
};