Seeing as I’d implemented the linked list in Java (an OO language) and Python (an OO/procedural mix), I thought it would be fun to implement the linked list in Javascript. This was certainly a fulfilling experience. At the onset, JavaScript had always been very procedural – you write some code to do some DOM-like things like getting field values from HTML form elements. But I have some interesting findings. Javascript turns out to be a little more than procedural. Javascript is prototype-based. Classes simply don’t exist in Javascript (as they would in an OO language). In Javascript, there is no distinction between the Class (which is the blueprint for instances and contains behaviour and structure) and the Object (which is an instance of the Class). No – in Javascript, it’s all the same. A function is a higher-order element, which means that a function can be made into an object by instantiating the function. In this way, the function acts as a constructor, and the resulting object is an instance. The function can contain attributes and it can contain other functions. When an object has been instantiated, it is possible to modify the prototype of the object (and all subsequent instance of the object for a particular run). This means you can change the “Class” definition as you go.

Javascript also has a notation for expressing objects as literals (which is quite nifty and very easy to read).

For my implementation of the linked list in Javascript, I created a function called LinkedListNode, which contained node data (data and next) and a function called LinkedList, which contained the first and last node and size, as well as functions to add, remove, check position, check size and get a string representation.

I’ve only implemented this for strings, and I’ve only tested it in Mozilla Firefox for Mac OS X. If you have a different setup, and it doesn’t work for you, I’d love to hear from you!

The code and unit tests are available in my GitHub repository. I also created my own Unit Testing framework for this one (it’s called UnitTestFramework.js).

Part 1: The LinkedListNode object
The list node is simply the data and a reference to the next node. The values for these properties are set to null when the object is instantiated.

function LinkedListNode() {
  this.data = null;
  this.next = null;
}

Part 2: The LinkedList object
The linked list class has a first and last node reference and a size.

function LinkedList() {
  this.firstNode = null;
  this.lastNode = null;
  this.size = 0;
}

Part 3: The add() function
The add method replaces the lastNode reference with the node being added and makes the old last node reference the new node as the next node in the list.

this.add = function(data) {

    var newNode = new LinkedListNode();
    newNode.data = data;

    if (this.firstNode == null) {
      this.firstNode = newNode;
      this.lastNode = newNode;
    }
    else {
      this.lastNode.next = newNode;
      this.lastNode = newNode;
    }

    this.size++;
  }

Part 4: The remove() function
The remove method iterates the list looking for the node to delete. We actually look ahead in the list because we need to loop around the deleted node by having the previous node point to the following node as its next node.

this.remove = function(data) {
    var currentNode = this.firstNode;

        if (this.size == 0) {
          return;
        }

        var wasDeleted = false;

        /* Are we deleting the first node? */
        if (data == currentNode.data) {

          /* Only one node in list, be careful! */
            if (currentNode.next == null) {
              this.firstNode.data = null;
              this.firstNode = null;
              this.lastNode = null;
              this.size--;
              return;
            }

          currentNode.data = null;
          currentNode = currentNode.next;
          this.firstNode = currentNode;
          this.size--;
          return;
        }

        while (true) {
            /* If end of list, stop */
            if (currentNode == null) {
              wasDeleted = false;
                break;
            }

            /* Check if the data of the next is what we're looking for */
            var nextNode = currentNode.next;
            if (nextNode != null) {
                if (data == nextNode.data) {

                    /* Found the right one, loop around the node */
                    var nextNextNode = nextNode.next;
                    currentNode.next = nextNextNode;

                    nextNode = null;
                    wasDeleted = true;
                    break;
                }
            }

            currentNode = currentNode.next;
        }

        if (wasDeleted) {
          this.size--;
        }
    }

Part 5: The helper function(s)
The getSize(), indexOf() and toString() functions are provided to make things more useful.

this.getSize = function() {
    return this.size;
  }

  this.indexOf = function(data) {
    var currentNode = this.firstNode;
    var position = 0;
    var found = false;

        for (; ; position++) {
            if (currentNode == null) {
                break;
            }

            if (data == currentNode.data) {
              found = true;
                break;
            }

            currentNode = currentNode.next;
        }

        if (!found) {
          position = -1;
        }

        return position;
  }

  this.toString = function() {
      var currentNode = this.firstNode;

      result = '{';

      for (i = 0; currentNode != null; i++) {
        if (i > 0) {
          result += ',';
        }
        var dataObject = currentNode.data;

        result += (dataObject == null ? '' : dataObject);
          currentNode = currentNode.next;
      }
      result += '}';

      return result;
  }