commit bf939056b88bd7e6403b9ed8b5a731b21a136aa5 parent 96dad389705864255df9bb6cf63af5c3e9a32e0e Author: Andrew Laack <andrew@laack.co> Date: Thu, 5 Nov 2026 20:34:01 -0600 lru cache lc Diffstat:
| A | leetcode/lru-cache/lru-cache.cpp | | | 90 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
1 file changed, 90 insertions(+), 0 deletions(-)
diff --git a/leetcode/lru-cache/lru-cache.cpp b/leetcode/lru-cache/lru-cache.cpp @@ -0,0 +1,90 @@ +class Node { + public: + Node* next; + Node* prior; + int value; + int key; +}; + +class LRUCache { +private: + Node* head = nullptr; + Node* tail = nullptr; + int cap = 0; + unordered_map<int, Node*> lookup {}; + +public: + + LRUCache(int capacity) { + this->cap = capacity; + } + + int get(int key) { + if(lookup.contains(key)) { + Node* current = lookup[key]; + + if(current != tail) { + Node* pr = current->prior; + if(pr != nullptr) { + pr->next = current->next; + } else { + head = current->next; + } + current->next->prior = pr; + + current->prior = tail; + tail->next = current; + tail = current; + current->next = nullptr; + } + return current->value; + } + return -1; + } + + void put(int key, int value) { + if(lookup.contains(key)) { + Node* cr = lookup[key]; + cr->value = value; + + if(cr != tail) { + if(cr->prior != nullptr) { + cr->prior->next = cr->next; + } else { + head = cr->next; + } + cr->next->prior = cr->prior; + + cr->prior = tail; + tail->next = cr; + tail = cr; + cr->next = nullptr; + } + + } else { + if(lookup.size() >= cap) { + lookup.erase(head->key); + Node* nHead = head->next; + delete head; + head = nHead; + + if(head != nullptr) head->prior = nullptr; + else tail = nullptr; + } + + Node* nextNodePtr = new Node(); + nextNodePtr->value = value; + nextNodePtr->key = key; + lookup[key] = nextNodePtr; + + if(tail != nullptr) { + nextNodePtr->prior = tail; + tail->next = nextNodePtr; + tail = nextNodePtr; + } else { + tail = nextNodePtr; + head = nextNodePtr; + } + } + } +};