Simple linked hash map in JS (Node/browser) I needed a simple data structure to cache the most recent few directory contents for this project I was working on. I thought a linked hash map would be the right approach since we will cache only one item per path (the key) and keep only X recent items. We will store the timestamp and directory contents as the "payload" for each node.

/**
 * A linked-list with key-based map. Use case: recent items cache, storing the
 * last X items with linear-time lookup and removal (constant average cost per
 * operation)
 *
 * - Adding an item to head will remove any existing items with that key
 * - Adding to head will remove an item from tail if needed to prevent
 *   exceeding max length
 */

function LinkedHashMap(maxLength) {
  this.map = {};
  this.head = null;
  this.tail = null;
  this.length = 0;
  this.maxLength = maxLength;
}

LinkedHashMap.prototype = {
  get: function(key) {
    var item = this.map[key] || {};
    return item.payload;
  },

  addHead: function(key, payload) {
    this.remove(key);
    if (this.length === this.maxLength) {
      this.removeTail();
    }
    var item = {
      key: key,
      prev: null,
      next: this.head,
      payload: payload
    };
    if (this.head) {
      this.head.prev = item;
    }
    this.head = item;
    if (!this.tail) {
      this.tail = item;
    }
    this.map[key] = item;
    this.length += 1;
  },

  removeTail: function() {
    if (this.tail) {
      this.removeItem(this.tail);
    }
  },

  // remove item by key
  remove: function(key) {
    var item = this.map[key];
    if (!item) return;
    this.removeItem(item);
  },

  // this removes an item from the link chain and updates length/map
  removeItem: function(item) {
    if (this.head === item) {
      this.head = item.next;
    }
    if (this.tail === item) {
      this.tail = item.prev;
    }
    if (item.prev) {
      item.prev.next = item.next;
    }
    if (item.next) {
      item.next.prev = item.prev;
    }
    delete this.map[item.key];
    this.length -= 1;
  }
};
This is good code! I don't have many suggestions, and those that I do have are mostly minor.



First of all, just consider the general naming. I don't mind the names as they are, but you could consider other names as well. Here are two sets of alternate names for addHead and removeTail:


add / remove — The simple approach. I sort of prefer something a little more explicit.
push / pop — I like this more. It conveys the stack-like nature of the data structure but is more concise.




Now for some more substantive suggestions. None of these functions (except, of course, get) return anything! This is okay, but not ideal. JavaScript lends itself quite well to chaining, and it would be nice to be able to do something like this:

map.push('foo', 'bar')
   .push('baz', 'qux')
   .push('one', 'two')
   .push('red', 'blue');


Make addHead/push return the map!

Next, also add return values for remove and pop/removeTail. These should each return the value removed from the map. This also makes it easy to determine if a removal actually removed something or not.

Also, should maxLength really be required? What if I want an unbounded map? Under your current implementation, I could just pass in null or undefined or -1, but it might be nice to make this functionality more explicit.



Now for some suggestions for additions.

First of all, add some kind of length or size method. Using Object.defineProperty, you could even implement length as a "magic" property a-la array.length.

Second, having access to the actual underlying list seems a little important if you're using this to display anything. The obvious answer would be to add some sort of iterator support, but JavaScript doesn't really have native support for iterators (pre-ES6). For simplicity's sake, a simple keys function that returned the list of keys in list order would be convenient.

Also, you might want to add peekHead and peekTail to complement the existing set of functions, since even with keys, shorthand access is convenient.



Consider adding some error checking. While this is called LinkedHashMap, JavaScript objects only support string keys. This isn't really a problem, and building a more general solution in pure JS would be nontrivial (another thing coming in ES6!). Unfortunately, it wouldn't be unreasonable for someone to accidentally try to use an object as a key. I'd recommend throwing an exception on insertion for non-string keys. Force explicit calls to toString to avoid confusing errors down the line.



Other odds and ends:


Why is removeItem part of the public API? Make it internal. Don't expose it.
Add some inline comments! Most of this code is fairly self-explanatory, so you don't need to write any essays. Just adding something like // insert item at head of list would break up the code and make it easier to follow by dividing it into chunks.
Add tests! Something like this is a textbook candidate for extensive unit testing. Something like a data structure should not go untested.