super simple JavaScript Implementation of LRUCache

LRUCache.js

// 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