Before I get into the details of this, what exactly is a linked list? Well, it’s a type of data storage structure that has some similarities to the array data type. The key difference is that, rather than storing values using numeric indexes, it stores them by creating links between successive elements so that they form a chain. You can only traverse such a list by following the links between elements, rather than by specifying an index. The advantage of linked lists is that they make removing and re-ordering elements really easy and efficient.

For example, for Sylvester’s next release, I’m implementing an algorithm that splits a polygon into a collection of its constituent triangles. It does this by recursively removing vertices from the polygon, chopping off one triangle each time. Managing the list of vertices using an array in this instance would quickly cause headaches, as you have to shuffle each element down a notch after removing an element from the list using a bunch of slice() and push() operations. As well as being inelegant, this is also really inefficient. Linked lists allow you to cleanly remove items from them, and all this operation has to do is change the links on the elements either side of the removed one.

JavaScript does not have a built-in linked list data type, so we need to implement our own. I’m going to show how to write a doubly-circularly-linked list, which sounds like the most complicated but is also the most versatile. It contains the functionality of linear and singly linked lists, and adds more features on top. If you want a more restricted type of list, this code should give you a good starting point.

I’ll start by specifying a base class that holds properties (and methods, later) shared between all types of linked list.

function LinkedList() {}
LinkedList.prototype = {
  length: 0,
  first: null,
  last: null
};

I’ve given it a length property that will work the same way as that for arrays. The properties first and last will be pointers to the first and last nodes in the list – we need somewhere to start traversing the list from! Throughout this, it’s important to remember that objects in JavaScript are pass-by-reference: setting myList.first = someObject means that myList.first is a reference to the object represented by someObject, not a copy of its value. In fact, the two variables are both references to the same data in memory – change one and you’ve automatically changed the other. This pass-by-reference feature is what makes linked lists possible.

Next, I’m going to subclass this to write the specifics of my doubly circular list.

LinkedList.Circular = function() {};
LinkedList.Circular.prototype = new LinkedList();

We need a way of adding nodes to the list. I should point out that a linked list is only good for storing lists of objects, not primitive values like strings or numbers. We need to set properties on the list nodes themselves, and we can only do that with objects.

Our first method, append, takes an object and sticks on the end of the list. If the list is empty, the node’s prev and next pointers will point to itself – the list is circular. Otherwise, we just link it up to the previous node and the first node in the list by setting properties:

LinkedList.Circular.prototype.append = function(node) {
  if (this.first === null) {
    node.prev = node;
    node.next = node;
    this.first = node;
    this.last = node;
  } else {
    node.prev = this.last;
    node.next = this.first;
    this.first.prev = node;
    this.last.next = node;
    this.last = node;
  }
  this.length++;
};

Note how we set the last property last of all – if we did it sooner then it would point to the wrong node for the links we want to create.

The second useful method we need is insertAfter, which allows us to insert a node anywhere in the list. The logic for this follows the same pattern – everything is done by just setting some properties, rather than shuffling array elements around. This highlights another important distinction between arrays and linked lists – a linked list does not ‘contain’ its nodes in the same way that arrays contain their values. Linked lists emerge out of links between objects, and a LinkedList object is just a plain object with three properties – first, last and length.

For insertAfter, we don’t need to deal with the special case of the list being empty, as we need some pre-existing node to insert the new one after. We do have to deal with the case where the new node becomes the last node in the list:

LinkedList.Circular.prototype.insertAfter = function(node, newNode) {
  newNode.prev = node;
  newNode.next = node.next;
  node.next.prev = newNode;
  node.next = newNode;
  if (newNode.prev == this.last) { this.last = newNode; }
  this.length++;
};

Pay attention to the order in which properties are set – anything that needs to be retrieved in order to set a link cannot be modified until nothing else depends on it. We set the links on the incoming node first by retrieving properties from the list, then skip forward to link the node in front, then finally change the node we’re inserting after, after we’ve got all the information we need from it.

The remove method is a little more involved, as we need to handle what happens when there’s only one node remaining. Again, pay attention to the order of operations and how it avoids broken links.

LinkedList.Circular.prototype.remove = function(node) {
  if (this.length > 1) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
    if (node == this.first) { this.first = node.next; }
    if (node == this.last) { this.last = node.prev; }
  } else {
    this.first = null;
    this.last = null;
  }
  node.prev = null;
  node.next = null;
  this.length--;
};

That’s all you need to get a basic linked list going. I add some methods for iteration, searching etc. but the core is what’s written above. I’ve leave prepend and insertBefore as exercises for the reader they’re really not tricky.

One other useful class you might need is an explicit node class. Sometimes, you’ll need to allow objects to belong to several linked lists, but each object can only have one prev and one next pointer. The cleanest way to solve this is to create a class specifically for use as a linked list node, that can point to objects you want to list.

LinkedList.Node = function(data) {
  this.prev = null; this.next = null;
  this.data = data;
};

So then you’d write

myList.append(new LinkedList.Node(someObject));

which appends a new object with a pointer to the object to actually want to list as its data property.

It’s a little tricky to see how this is so different from an array at first, but one you start using it where it’s appropriate you’ll find it so much more useful. Later this week I’ll post some additional useful methods and a source file for you to download.