LinkedList Class in MooTools

posted by Jonah Dempcy

A commonly used data structure in Java and other programming languages is the linked list (Wikipedia). It is similar to an array in that it is a way to store a collection of objects in sequence, however unlike an array you cannot access items in the collection by index. Instead, you access them through links from other items in the collection, or from the initial head or tail link (which can typically accessed with getFirst() and getLast() methods, respectively).

Each item in the collection has a getNext() method which returns the next item in the collection. If it's a doubly-linked list then each item (save for the head and tail) will have both getNext() and getPrevious() methods.

In JavaScript, no such construct exists, so we'll create one. This is mostly for academic purposes but there's nothing to stop you from using it in real code if you're so inclined. For the sake of this practice, we'll just make a singly-linked list as it is a bit simpler.

This also provides an introduction to defining classes in MooTools. We aren't using much MooTools-specific functionality here so it could easily be ported to another library, or even written without the use of a library. But, since I use MooTools for most of my projects, I decided to use it here. I think you'll find defining classes in MooTools to be quite easy.

The LinkedListItem Class

Here is the code to define the LinkedListItem class. The LinkedListItem takes a value of any type (string, object, etc) and returns an object of type LinkedListItem, which has the original value stored as the value property on the object. It also defines accessor methods for getting/setting the next item in the list. There is also an accessor method for getting the original value.

// This class defines an individual item in the linked list.
// The value it is instantiated with is stored in the value property,
// and is accessible via getter/setter methods.

var LinkedListItem = new Class({
   initialize: function(item) {
       this.value = item;
   },
  
   getNext: function() {
       return this.next;
   },
  
   setNext: function(item) {
       this.next = item;
   },
  
   getValue: function() {
       return this.value;
   }
});

Read on to see how the LinkedListItem class is used by the LinkedList.

Defining the LinkedList Class

The LinkedList class will take an array of objects of any type and create a linked list from those objects. The linking occurs in the order of the array. So, if you call it with ['a', 'b', 'c'] you'll get back a linked list with a as the head, and c as the tail. The list will be linked like so: a -> b -> c.

The LinkedList class has three methods: setFirst(), getFirst() and getAll(). The former two are accessor methods for changing the first element, i.e. the head. The latter is a method which returns an array of all the items in the linked list, in the order they are linked.

There are quite a few other methods you could implement for the LinkedList but for now, these will suffice. If you're particularly brave and inclined to add to the class, go ahead and check out the Java LinkedList docs to see what other methods are available.

Here's the LinkedList class I came up with:

var LinkedList = new Class({
  
   // Input: Array collection
   // An array of items to turn into a singly linked list
  
   initialize: function(collection) {

       this.collection = new Array();
                 
       // Construct the linked list
       collection.each(function(item, i) {
           var item = new LinkedListItem(item);
           this.collection.push(item);
          
           if (i > 0) {
               this.collection[i - 1].setNext(item);
           }
       }.bind(this));
      
       this.setFirst(this.collection[0]);
   },
  
   // Input: LinkedListItem item
   // Sets the head to be the given item
      
   setFirst: function(item) {
       this.head = item;
   },
      
   // Returns: LinkedListItem head
  
   getFirst: function() {
       return this.head;
   },
  
   // Returns: Array result
   // An array with all items' values, in the order they are linked
  
   getAll: function() {
      var result = new Array();
     
      result.push(this.getFirst().getValue());
     
      var item = this.getFirst().getNext();
      while (item) {
          result.push(item.getValue());
          item = item.getNext();
      }
     
      return result;
   }
});

There are only two areas of the code that need explaining: constructing the list in the initialize() method, and constructing an array from the list in the getAll() method. I'll touch on each to make sure it is clear what exactly is going on.

The initialize() method is called on each instance of the class, with the arguments given to the constructor of the class. Calling new LinkedList(['foo', 'bar']) will call the initialize() method with the argument ['foo', 'bar'] as well. This is an automatic function call handled by MooTools and should not be done manually, unlike Prototype where the developer must manually call the initialize() method after instantiating the class.

The first thing our LinkedList initialize() method does is create the collection property. This is so it can store the data internally, and this property is not meant to be publicly accessible to other code. The collection array will be used to store the LinkedListItem objects created from the input array.

I use MooTools each() method to iterate over the items in the input array (collection). For each item, I create a new LinkedListItem and add it to the collection property where it will be stored. I then set the previous item's link (if it exists) to the current item, using the setNext() method.

Finally, once the each() loop has finished iterating over all the items in the collection, I set the head link to be the first item in the array, using the setFirst() method.

The other interesting area is the getAll() method, which does basically the opposite of the initialize() method. Instead of constructing a LinkedList from an array, the getAll() method returns an array in the order of the LinkedList. So you could instantiate a LinkedList in a certain order, change the order around by various setNext() calls, and then call getAll() and get back an array in the new order. This might not seem very useful at the moment, but bear with me and I'll demonstrate its utility through a challenge or two.

The getAll() method uses a while() loop instead of an each() loop, because we don't know the length of the list. Even if the length of the collection array is 10, for instance, we have no guarantee the list will be 10 items. The coder may have called setNext(null) on the head, in which case the list would only have a length of 1. Therefore, we must use a while() loop that continues as long as their are next items, in other words, as long as getNext() on the current item is not null.

Inside the while() loop, we simply add the current item to the result array and then redefine the item variable to point to the next item. After the loop finishes, we return the result, which is an array in the order that the list is linked.

You can test that this works by instantiating a LinkedList and calling getAll() on it.

window.addEvent('domready', function() {

   var list = new LinkedList(['a', 'b', 'c', 'd',
                              'e', 'f', 'g', '1',
                              '2', '3', '4', '5']);

   console.log(list.getAll());
  
   // RESULT:
   // a,b,c,d,e,f,g,1,2,3,4,5
});

LinkedList Challenge

Next up, a LinkedList challenge! Can you write code that reverses a linked list in place, without creating a new array?

My next post will provide an answer, but in the meantime, give it a try. To make it clear, the challenge is to reverse a singly-linked list, using either the LinkedList class defined here or your own implementation, in place. That is, without creating another array, hash or other data structure to store the data in the list temporarily before writing it again.

This is the expected outcome:

   var list = new LinkedList(['a', 'b', 'c', 'd',
                              'e', 'f', 'g', '1',
                              '2', '3', '4', '5']);

   console.log('Forward: ' + list.getAll());
   console.log('Backward: ' + reverseLinkedList(list));
  
   // RESULT:
   //
   // Forward: a,b,c,d,e,f,g,1,2,3,4,5
   // Backward: 5,4,3,2,1,g,f,e,d,c,b,a   

I should also mention that you can't access the collection array inside the linked list directly. Otherwise, you could just do something like this:

function reverseLinkedList(list) {
   return list.collection.reverse();
}

That would be a cheap, and is not an acceptable solution. This challenge is to reverse the list in place, so your only choice for starting is to call getFirst() on the list:

function reverseLinkedList(list) {
   var head = list.getFirst();
}

This challenge was given to me in Java by my mentor at Amazon, Chris. It took me a good 45 minutes to solve the first time (though Chris made me solve it on a whiteboard, which is always more difficult for me than typing it up). Good luck and stay tuned for the next post which will offer a solution to this challenge.