Search for a command to run...
O(1) get and put by evicting the least recently used
Initialization
Empty cache with capacity 2. The list runs head → tail as most-recently-used → least-recently-used, and dummy HEAD/TAIL nodes mean insertion and deletion never need null checks.
Hash Map + Doubly Linked List
1class Node {2 constructor(key = -1, val = -1) {3 this.key = key; this.val = val;4 this.next = null; this.prev = null;5 }6}//capacity: 2size: 07 8class LRUCache {9 constructor(capacity) {10 this.mpp = new Map();11 this.cap = capacity;12 this.head = new Node();13 this.tail = new Node();14 this.head.next = this.tail;15 this.tail.prev = this.head;16 }17 18 deleteNode(node) {19 node.prev.next = node.next;20 node.next.prev = node.prev;21 }22 23 insertAfterHead(node) {24 node.next = this.head.next;25 this.head.next.prev = node;26 this.head.next = node;27 node.prev = this.head;28 }29 30 get(key) {31 if (!this.mpp.has(key)) return -1;32 const node = this.mpp.get(key);33 this.deleteNode(node);34 this.insertAfterHead(node);35 return node.val;36 }37 38 put(key, value) {39 if (this.mpp.has(key)) {40 const node = this.mpp.get(key);41 node.val = value;42 this.deleteNode(node);43 this.insertAfterHead(node);44 return;45 }46 if (this.mpp.size === this.cap) {47 const lru = this.tail.prev;48 this.mpp.delete(lru.key);49 this.deleteNode(lru);50 }51 const newNode = new Node(key, value);52 this.mpp.set(key, newNode);53 this.insertAfterHead(newNode);54 }55}