JS101: Linked Lists

My day to day responsibilities are somewhat far-removed from the concepts I learned in my introductory Computer Science classes. I'm under the impression that engineers don't need to know how to write their own BSTs, much less web developers. However, I firmly believe that the value in a college degree stems from learning how to think, not necessarily what you learn.

When I was interviewing for a technical role in the Bay Area, I picked up a book called Cracking the Coding Interview by Gayle Laakmann McDowell. After flipping through a few pages, I realized that it was unavoidable: I'd have to brush up on algorithms and data structures. In an attempt to explore the possibilities of object-oriented programming with JavaScript, I decided to see what it would look like to implement those academic topics in a new language. My first stop was the veritable linked list.

Source Code: https://github.com/tuanderful/js-101/tree/master/01_LinkedList

A linked list is a chain of nodes, where each node holds a value as well as a reference to the next node. I began by defining a Node constructor:

function Node(value) {
  return {
    val: value,
    next: null
  }
}

I designed my LinkedList constructor so that it could take in a value and set it as the value of the first item on the list, known as the head. The LinkedList usually has just one reference, and that is to head. Accessing the second item on the list requires looking at what head.next points to; the third item on the list is accessed through the second item's next property, and so on.

I planned on using new Node() to create a new Node when constructing a LinkedList, then assigning it to head, but I decided that it'd be easier to leave all that logic involving null checks up to the insert method. So the LinkedList constructor is rather simple:

function LinkedList(val) {
  this.head = null;
  this.length = 0;

if (typeof val !== 'undefined') {
    this.insert(val);
  }
}

LinkedList.prototype.isEmpty = function() {
  return this.head === null;
}

I also included a method that we'll be using soon, isEmpty(). I decided that it will reside on the prototype chain so as to not take up memory each time a linked list is created. Note that we could have also implemented isEmpty by comparing length to 0.

Insertion

The first thing it does is check if the linked list is empty. In this special case, we can set the head of the linked list to the Node we just created. Otherwise, we iterate through the linked list until we are at the last element, at which point, we set it's next property equal to the node we just created.

LinkedList.prototype.insert = function(val) {
  var newNode = new Node(val),
      pointer = this.head;

if (this.isEmpty()) {
    this.head = newNode;
  } else {
    while (pointer.next !== null) {
      pointer = pointer.next;
    }
    pointer.next = newNode;
  }

this.length++;
  return this;                         // for chaining
}

I also figured it was about a good a time as any to increment the length property as we proceeded.