int key, value;

DLinkedNode* prev;

DLinkedNode* next;

DLinkedNode(): key(0), value(0), prev(nullptr), next(nullptr) {}

DLinkedNode(int _key, int _value): key(_key), value(_value), prev(nullptr), next(nullptr) {}

unordered_map<int, DLinkedNode*> cache;

DLinkedNode* head;

DLinkedNode* tail;

int size;

int capacity;

LRUCache(int capacity): capacity(capacity), size(0) {

head = new DLinkedNode();

tail = new DLinkedNode();

head->next = tail;

tail->prev = head;

}

int get(int key) {

if (!cache.count(key)) {

return -1;

}

DLinkedNode* node = cache[key];

moveToHead(node);

return node->value;

}

void put(int key, int value) {

if (!cache.count(key)) {

// 不存在创建一个

DLinkedNode* node = new DLinkedNode(key, value);

cache[key] = node;

addToHead(node);

size++;

if (size > capacity) {

DLinkedNode* tail = removeTail();

cache.erase(tail->key);

delete tail;

size--;

}

} else {

// 存在更新值并且移动到 head

DLinkedNode* node = cache[key];

node->value = value;

moveToHead(node);

}

}

void moveToHead(DLinkedNode* node) {

removeNode(node);

addToHead(node);

}

void removeNode(DLinkedNode* node) {

node->prev->next = node->next;

node->next->prev = node->prev;

}

void addToHead(DLinkedNode* node) {

node->prev = head;

node->next = head->next;

head->next->prev = node;

head->next = node;

}

DLinkedNode* removeTail() {

DLinkedNode* node = tail->prev;

removeNode(node);

return node;

}