Simple JS LRU Cache

gistfile1.js

var Node = function(Data)
{
  //Reference to the next element (closer to the head)
  this.next = null;
  //Reference to the prev element (closer to the tail)
  this.prev = null;
  
  //The payload of the node (UserName in our example)
  this.data = Data;
}

var Cache = function(size){
  //How many elements to hold without eviction.
  this.size = size;

  //Associative Array
  this.cache = {};

  //Double Linked List
  this.req_head = null;
  this.req_tail = null;
  this.req_length = 0;

  //Only Public API Point.
  this.lookup = function(uid, callback)
  {
    var node = cache[uid];
    
    //If the node is already in cache.
    if(node !== undefined)
    {
      //Splice the node out of the linked list.
      node.next.prev = node.prev;
      node.prev.next = node.next;
      
      //Make the node the head.
      node.prev = this.req_head;
      node.next = null;
      this.req_head.next = node;
      this.req_head = node;
      
      //Return the data to our caller.
      callback(node.data);
      return;
    }
    else
    {
      //Node isn't in cache.
      
      var self = this; //Advanced.
      
      //This is the provided async fetcher
      fetch(function(uid, username)
      {
        //Make the new node.
        node = new Node({uid: uid, name: username});
        
        //Make the new node the head.
        node.prev = self.req_head;
        self.req_head.next = node;
        self.req_head = node;
        
        //Record the increase in size of the cache.
        self.req_length++;
        
        if(self.req_length > self.size)
        {
          //Eviction Time.
          
          //Remove the tail from the DLL.
          var old_tail = self.req_tail;
          old_tail.next.prev = null;
          self.req_tail = old_tail.next;
          old_tail.next = null;
          
          //Remove the references to the data.
          delete self.cache[uid];
          delete old_tail;
          
          //Record the decrease in size.
          self.req_length -= 1;
        }
        
        //Pass the data along to the callback.
        callback(node.data);
        return;
      });
    }
  }
}