structLinkedNode{intkey,value;LinkedNode*prev;LinkedNode*next;LinkedNode():key(0),value(0),prev(nullptr),next(nullptr){}LinkedNode(int_key,int_value):key(_key),value(_value),prev(nullptr),next(nullptr){}};classLRUCache{private:unordered_map<int,LinkedNode*>cache;LinkedNode*head;LinkedNode*tail;intsize;intcapacity;voidaddToHead(LinkedNode*node){node->prev=head;node->next=head->next;head->next->prev=node;head->next=node;}voidremoveNode(LinkedNode*node){node->prev->next=node->next;node->next->prev=node->prev;}voidmoveToHead(LinkedNode*node){removeNode(node);addToHead(node);}LinkedNode*removeTail(){LinkedNode*node=tail->prev;removeNode(node);returnnode;}public:LRUCache(int_capacity):capacity(_capacity),size(0){head=newLinkedNode();tail=newLinkedNode();head->next=tail;tail->prev=head;}intget(intkey){// if key does not exist, return -1if(!cache.count(key))return-1;// if key exists, use hash map to locate, and move to headLinkedNode*node=cache[key];moveToHead(node);returnnode->value;}voidput(intkey,intvalue){if(!cache.count(key)){// if key does not exist, create a new nodeLinkedNode*node=newLinkedNode(key,value);// add to hash mapcache[key]=node;// add to head of double linked listaddToHead(node);size++;if(size>capacity){// delete tail node if size is larger than capacityLinkedNode*removed=removeTail();cache.erase(removed->key);deleteremoved;size--;}}else{// if key exists, locate through hash map and move the modified node to headLinkedNode*node=cache[key];node->value=value;moveToHead(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); */