-
Notifications
You must be signed in to change notification settings - Fork 0
/
LRU Cache Implementation (**IMP)
68 lines (57 loc) · 1.67 KB
/
LRU Cache Implementation (**IMP)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
// problem url: https://www.codingninjas.com/codestudio/problems/799354?topList=striver-sde-sheet-problems&utm_source=striver&utm_medium=website&leftPanelTab=0
// mode: Medium
// **IMP TOPIC: LRU (Least Recently Used)
// Doubly LinkedList
#include <bits/stdc++.h>
struct Node {
int key=0, val=0;
Node *prev = nullptr, *next = nullptr;
Node(int key, int val): key(key), val(val){}
};
class LRUCache{
Node *head, *tail;
unordered_map<int,Node*> cache;
int size = 0, currSize = 0;
void createAndAddNode(int key, int val){
Node *node = new Node(key, val);
node->next = head->next;
node->prev = head;
head->next->prev = node;
head->next = node;
cache[key] = node;
}
void deleteNode(Node* node){
Node *prevNode = node->prev;
Node *nextNode = node->next;
prevNode->next = nextNode;
nextNode->prev = prevNode;
cache[node->key] = nullptr;
node = nullptr;
}
public:
LRUCache(int capacity){
size = capacity;
head = new Node(0,0);
tail = new Node(0,0);
head->next = tail;
tail->prev = head;
}
int get(int key){
if(cache[key] == nullptr)
return -1;
Node *node = cache.at(key);
int val = node->val;
deleteNode(node);
createAndAddNode(key, val);
return val;
}
void put(int key, int value){
if(cache[key] != nullptr)
deleteNode(cache.at(key));
else if(currSize == size)
deleteNode(tail->prev);
else
++currSize;
createAndAddNode(key, value);
}
};