Enhancing your linked list

Having given you the basics of linked lists in my last couple of posts, I’ll now give you some useful extensions to the class that you can use to make it even friendlier.

What would be really useful is a little function that lets you pretend the list is an array and grab a node by its index:

LinkedList.prototype.at = function(i) {
  if (!(i >= 0 && i < this.length)) { return null; }
  var node = this.first;
  while (i--) { node = node.next; }
  return node;
};

Note this is part of the generic list class, which the circular class inherits from. This method will get less and lass efficient the longer your list is – it is only possible to access linked list nodes sequentially and this makes access slower than for arrays.

Second, we might like a way of finding a node containing some piece of data, if we’re using LinkedList.Node:

LinkedList.prototype.withData = function(data) {
  var node = this.first, n = this.length;
  while (n--) {
    if (node.data == data) { return node; }
    node = node.next;
  }
  return null;
};

An iterator might be nice as well – this takes advantage of the fact that JavaScript lets you pass functions as arguments to other functions:

LinkedList.prototype.each = function(fn) {
  var node = this.first, n = this.length;
  for (var i = 0; i < n; i++) {
    fn(node, i);
    node = node.next;
  }
};

This lets you iterate over the nodes and gives you the index of each one, so you can write:

myList.each(function(node, i) {
  // Do something with the node
});

Note that you cannot remove nodes while inside an each loop as this will break the link needed to get to the next node. Even doing something like nextNode = node.next before the call to fn(node, i) doesn’t help.

And finally, it helps to have a couple of methods to convert to and from arrays:

LinkedList.prototype.toArray = function() {
  var arr = [], node = this.first, n = this.length;
  while (n--) {
    arr.push(node.data || node);
    node = node.next;
  }
  return arr;
};

Note that this is part of the generic class as its form will not differ for different types of linked list. Also, note that it will give you back the node data if you’re using LinkedList.Node. The members of the array you get back will be the same objects as are contained in the list, not copies of them. To convert an array to a circular list:

LinkedList.Circular.fromArray = function(list, useNodes) {
  var linked = new LinkedList.Circular();
  var n = list.length;
  while (n--) { linked.prepend(useNodes ?
      new LinkedList.Node(list[n]) : list[n]); }
  return linked;
};

And that just about wraps it up. You can download the complete source for the linked list class I’m using (with various modifications) in some of my projects. It’s MIT-licensed, so do what you like with it.

If you’ve enjoyed this article, you might enjoy my recently published book JavaScript Testing Recipes. It’s full of simple techniques for writing modular, maintainable JavaScript apps in the browser and on the server.