Skip to content

Instantly share code, notes, and snippets.

@tpae
Created November 21, 2016 08:16
  • Star 3 You must be signed in to star a gist
  • Fork 2 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save tpae/8f997cd7ab06a1b89c38267f0b588816 to your computer and use it in GitHub Desktop.
super simple JavaScript Implementation of LRUCache
// LRUCache.js - super simple JavaScript Implementation
// LRU stands for "Least Recently Used"
// https://en.wikipedia.org/wiki/Cache_replacement_policies#LRU
// -----------------------------------------
function LRUNode(key) {
this.key = key;
this.next = this.prev = null;
}
// -----------------------------------------
// doubly-linked list based LRUCache
// set(key, value)
// get(key)
// bubbleUp(key)
function LRUCache(capacity) {
this.capacity = capacity;
this.head = this.tail = null;
this.length = 0;
this.data = {};
this.nodeRefs = {};
}
// set the value, if it already exists, bubble up the key.
// if it doesn't exist, set the key to the head.
// if it reaches capacity, remove the tail to make room.
// time complexity: O(1)
LRUCache.prototype.set = function(key, value) {
// check to see if data exists.
if (this.data[key]) {
// bubble up the key
this.bubbleUp(key);
// update existing value
this.data[key] = value;
} else {
// data doesn't exist, update new head
var head = new LRUNode(key);
// build key linked list
if (this.head === null && this.tail === null) {
this.head = head;
this.tail = head;
this.head.next = this.tail;
this.tail.prev = this.head;
} else {
this.head.prev = head;
head.next = this.head;
this.head = head;
}
// save a reference to the node for faster bubbleUp
this.nodeRefs[head.key] = head;
// increment size
this.length += 1;
// check capacity
if (this.length > this.capacity) {
// remove tail
var tail = this.tail;
this.tail = tail.prev;
this.length -= 1;
// delete data and refs
delete this.data[tail.key];
delete this.nodeRefs[tail.key];
}
// set new data
this.data[key] = value;
}
};
// get the value. since the value is used,
// we bubble up the key to the head.
// time complexity: O(1)
LRUCache.prototype.get = function(key) {
// check to see if data exists.
if (this.data[key]) {
// bubble up the key
this.bubbleUp(key);
// return data
return this.data[key];
}
return null;
};
// bubble up the key to the front.
// time complexity: O(1)
LRUCache.prototype.bubbleUp = function(key) {
// make sure the ref exists, and is not the head node
if (this.nodeRefs[key] && this.nodeRefs[key] !== this.head) {
var prefRef = this.nodeRefs[key].prev;
var nextRef = this.nodeRefs[key].next;
prefRef.next = nextRef;
nextRef.prev = prefRef;
this.head.prev = this.nodeRefs[key];
this.nodeRefs[key].next = this.head;
this.head = this.nodeRefs[key];
}
};
// -----------------------------------------
// instantiate our cache with max capacity of 5
var cache = new LRUCache(5);
// set some dummy values
cache.set("key1", "some value1");
cache.set("key2", "some value2");
cache.set("key3", "some value3");
cache.set("key4", "some value4");
cache.set("key5", "some value5");
cache.set("key4", "some value4");
console.log(cache.get("key1")); // some value1
console.log(cache.length); // 5
cache.set("key6", "some value6");
console.log(cache.get("key1")); // null, since it's least recently used.
console.log(cache.length); // 5
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment