Skip to content

Instantly share code, notes, and snippets.

@shsunmoonlee
Created February 4, 2020 13:39
Show Gist options
  • Save shsunmoonlee/1a3e78d0c4efa5dce4c1272d7067818d to your computer and use it in GitHub Desktop.
Save shsunmoonlee/1a3e78d0c4efa5dce4c1272d7067818d to your computer and use it in GitHub Desktop.
Classic LRU Cache in JavaScript. Goal: Real World Implementation
function ListNode(key, value) {
this.value = value
this.key = key
this.next = this.prev = null
}
/**
* @param {number} capacity
*/
var LRUCache = function(capacity) {
this.capacity = capacity
this.size = 0
this.head = new ListNode()
this.tail = new ListNode()
this.cache = new Map()
this.head.next = this.tail
this.tail.prev = this.head
}
/**
* @param {number} key
* @return {number}
*/
LRUCache.prototype.get = function(key) {
let node = this.cache.get(key)
// console.log("===GET", key, this.cache, node)
if(node) {
this.moveToHead(node)
return node.value
} else {
return -1
}
};
LRUCache.prototype.moveToHead = function(node) {
this.removeNode(node)
this.addNode(node)
}
LRUCache.prototype.removeNode = function(node) {
let prev = node.prev
let next = node.next
prev.next = next
next.prev = prev
this.cache.delete(node.key)
this.size --
}
LRUCache.prototype.addNode = function(node) {
let next = this.head.next
node.prev = this.head
this.head.next = node
node.next = next
next.prev = node
this.cache.set(node.key, node)
this.size ++
}
LRUCache.prototype.popTail = function() {
let node = this.tail.prev
this.removeNode(node)
}
/**
* @param {number} key
* @param {number} value
* @return {void}
*/
LRUCache.prototype.put = function(key, value) {
let node = this.cache.get(key)
if(node) {
node.value = value
this.moveToHead(node)
} else {
this.addNode(new ListNode(key, value))
if(this.size > this.capacity) {
this.popTail()
}
}
};
/**
* Your LRUCache object will be instantiated and called as such:
* var obj = new LRUCache(capacity)
* var param_1 = obj.get(key)
* obj.put(key,value)
*/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment