| 52 | } |
| 53 | |
| 54 | void put(int key, int val) { |
| 55 | // If a node with this key already exists, remove it from the |
| 56 | // linked list. |
| 57 | if (hashmap.find(key) != hashmap.end()) { |
| 58 | DoublyLinkedListNode* existingNode = hashmap[key]; |
| 59 | removeNode(existingNode); |
| 60 | delete existingNode; |
| 61 | hashmap.erase(key); |
| 62 | } |
| 63 | DoublyLinkedListNode* node = new DoublyLinkedListNode(key, val); |
| 64 | hashmap[key] = node; |
| 65 | // Remove the least recently used node from the cache if adding |
| 66 | // this new node will result in an overflow. |
| 67 | if (hashmap.size() > capacity) { |
| 68 | DoublyLinkedListNode* lruNode = head->next; |
| 69 | hashmap.erase(lruNode->key); |
| 70 | removeNode(lruNode); |
| 71 | delete lruNode; |
| 72 | } |
| 73 | addToTail(node); |
| 74 | } |
| 75 | |
| 76 | void addToTail(DoublyLinkedListNode* node) { |
| 77 | DoublyLinkedListNode* prevNode = tail->prev; |