class Node {
public:
int key;
int value;
Node* next;
Node* pre;
Node(int k, int v): key(k), value(v) {}
};
class LRUCache {
public:
LRUCache(int capacity) {
cap = capacity;
head = NULL;
tail = NULL;
}
int get(int key) {
Node* node = map[key];
if (node == NULL) return -1;
if (node != tail) {
if (node == head) {
head = head -> next;
}
else {
node -> pre -> next = node -> next;
node -> next -> pre = node -> pre;
}
tail -> next = node;
node -> pre = tail;
node -> next = NULL;
tail = node;
}
return node -> value;
}
void put(int key, int value) {
Node* node = map[key];
if (node != NULL) {
node -> value = value;
if (node != tail) {
if (node == head) {
head = head -> next;
}
else {
node -> pre -> next = node -> next;
node -> next -> pre = node -> pre;
}
tail -> next = node;
node -> pre = tail;
node -> next = NULL;
tail = node;
}
}
else {
Node* newNode = new Node(key, value);
if (cap == 0) {
Node* tmp = head;
head = head -> next;
map.erase(tmp -> key);
cap++;
}
if (head == NULL && tail == NULL) {
head = newNode;
}
else {
tail -> next = newNode;
newNode -> pre = tail;
newNode -> next = NULL;
}
tail = newNode;
map[key] = newNode;
cap--;
}
}
private:
unordered_map<int, Node*> map;
int cap;
Node* head;
Node* tail;
};
/**
* 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);
*/