in this code, we use an hashMap to store the node address for fast accessing

the LRU order is stored in a double linked list, the access, move, and delete operation are all O(1).

The operation on linked list pointers are good example for beginner who just started to learn data structure.

```
class LRUCache{
public:
struct Node
{
int val;
int key;
Node * prev;
Node * next;
Node( int k, int v):key(k), val(v), prev(NULL), next(NULL){};
};
unordered_map<int,Node*>mp;
Node* head;
Node* end;
int cap;
//for debug
void print()
{
Node * temp = head;
cout << "from head to end: ";
while(temp)
{
cout << temp -> key << " ";
temp = temp -> next;
}
cout << endl << "from end to head: ";
temp = end;
while(temp)
{
cout << temp -> key << " ";
temp = temp -> prev;
}
cout << endl;
}
LRUCache(int capacity)
{
cap = capacity;
head = new Node(0,0);
end = new Node(0,0);
head -> next = end;
end -> prev = head;
}
int get(int key)
{
if(mp.find(key)==mp.end()) return -1;
Node * temp = mp[key];
//remove temp from original position
temp -> prev -> next = temp -> next;
temp -> next -> prev = temp -> prev;
//move temp to the end
end -> prev -> next = temp;
temp -> prev = end -> prev;
temp -> next = end;
end -> prev = temp;
return temp -> val;
}
void set(int key, int value)
{
if(mp.find(key)==mp.end())
{
//create new node
Node * temp = new Node(key,value);
//insert to map
mp [key] = temp;
//insert to list
temp -> prev = end -> prev;
temp -> prev -> next = temp;
temp -> next = end;
end -> prev = temp;
//check size
while(mp.size()>cap)
{
temp = head -> next;
head -> next = temp -> next;
temp -> next -> prev = head;
mp.erase(temp->key);
delete temp;
}
}
else
{
mp[key]->val = value;
get(key);
}
}
};
```