https://leetcode.com/problems/lru-cache/
An LRU cache can be implemented with an hashmap and a doubly linked list. The hashmap is used to insert/delete a key-value pair in average \(O(1)\). The doubly linked list is used to maintain the order of recent accesses of the keys.
class LRUCache {
struct Node {
int key;
Node* prev;
Node* next;
Node(int _key): key(_key), prev(NULL), next(NULL) {}
};
unordered_map<int, pair<int, Node*>> hashmap;
int m_capacity;
Node* head;
Node* tail;
void moveNodeToHead(Node *node) {
if (node == NULL || node == head) return;
if (node == tail) {
tail = node->prev;
node->prev->next = NULL;
node->prev = NULL;
head->prev = node;
node->next = head;
head = node;
} else {
node->prev->next = node->next;
node->next->prev = node->prev;
head->prev = node;
node->next = head;
head = node;
}
}
int removeTail() {
if (tail == NULL) return -1;
if (head == tail) {
int ret = tail->key;
delete(tail);
head = tail = NULL;
return ret;
}
int ret = tail->key;
Node* temp = tail->prev;
temp->next = NULL;
delete(tail);
tail = temp;
return ret;
}
void addToHead(int key) {
if (!head) {
head = new Node(key);
tail = head;
} else {
Node* temp = head;
head = new Node(key);
head->next = temp;
temp->prev = head;
}
}
public:
LRUCache(int capacity) {
m_capacity = capacity;
head = NULL;
tail = NULL;
}
int get(int key) {
if (hashmap.find(key) != hashmap.end()) {
Node* node = hashmap[key].second;
moveNodeToHead(node);
return hashmap[key].first;
}
return -1;
}
void put(int key, int value) {
if (hashmap.find(key) != hashmap.end()) {
hashmap[key].first = value;
moveNodeToHead(hashmap[key].second);
return;
}
if (hashmap.size() == m_capacity) {
int evicted = removeTail();
hashmap.erase(evicted);
}
addToHead(key);
hashmap[key] = pair<int, Node*>(value, head);
}
};
Comments