Linked List (JavaScript)

A linked list is a common programming structure used to store and manage data. Some advantages of linked lists:

  • Fast insertion and removal of data at constant time-complexity O(1).
  • Versatile insofar as they are dynamically resizable.
  • Linked lists are also used as a complementary data structure for hash table buckets.
Let’s explore linked lists under three headings:
  1. The nature of linked lists
  2. The implementation of linked lists
  3. The JavaScript we learn from linked lists

First, the nature of linked lists:

At a high level, what is the structure of a linked list?

This diagram is helpful for illustrating the concept of a linked list; but it is unhelpful in writing code for it. What’s head? What’s tail? What are all these boxes and arrows? Looks dangerous or accusatory.

The first thing to note is that a linked list is comprised of plain old objects we call “nodes.” An example of objects in action:

let basicList = { 
name: "myName",
phoneNumber: "212-555-1234",
age: 25,
anotherObject: { inception: "deep" }
};

So if you know how to insert into, remove from, and update properties/values in objects, then you know how to navigate a linked list.

Second, the implementation of linked list:

Make a Class:

We must build a linked list class. Let’s do so using the pseudoclassical style of class instantiation, which will create a relationship between LinkedList.prototype and any objects we create with the LinkedList function. This way we can give the head and tail properties to LinkedList class, instantiate LinkedList objects, and store methods that we will be able to share across linked lists.

var LinkedList = function() {
this.head = null;
this.tail = null;
};

The head and tail properties are objects initially set to null. When we add data to the linked list, the head and tail will point to the objects (nodes) we insert. Head will point to a node at the start of the chain of nodes and tail will point to the node at the end.

Make Nodes:

Now that we know linked list is simply an object that contains two properties (head, tail) that contains other objects (nodes), what do the nodes look like? If we want nodes, we have to make them.

LinkedList.prototype.makeNode = function(value) {
var node = {};
node.value = value;
node.next = null;
return node;
};

LinkedList.prototype.makeNode is now a method attached to the LinkedList object. We can use it whenever we want to create nodes to insert into the list.

Notice that makeNode is an object with two properties: value and next. Value is simply the data we pass into it (string, number). Next is where we put the next node in the linked list. Next is the link that allows us to travel through the list. The list is essentially objects nested within objects. So head and tail contain nodes; and nodes contain other nodes. Nodes are connected by their “next” properties.

Make Methods:

In order to handle linked lists, let’s build out three more methods: addToTail, removeHead, and contains (which finds the node we want).

LinkedList.prototype.addToTail = function(value) {
var newNode = makeNode(value);
if (!this.head.value) {
this.head = newNode;
}
this.tail.next = newNode;
this.tail = newNode;
};

The addToTail method simply checks the head for a matching value. If there is no value at head, then assign the newly created node to head and assign newNode to both tail.next and tail. When it is the first insertion, head gets assigned. Subsequent insertions only update tail and tail.next, not head.

LinkedList.prototype.removeHead = function() {
if (this.head === null) {
return null;
}
var oldHead = this.head;
this.head = this.head.next;
this.tail = this.tail.next;
};

In removeHead, the oldHead is stored. Then the node at head’s next property is assigned to head itself.

LinkedList.prototype.contains = function(value) {
var node = this.head;
while (node) {
if (node.value === value) {
return true;
}
node = node.next;
}
return false;
};

This while loop’s termination condition updates when node.next is assigned to node within the loop. The loop checks every node starting from the head until it finds a match or there are no more nodes left in the list.

Third, the JavaScript we learn from linked lists:

  • Pseudoclassical instantiation pattern: This pattern works in the same way as prototypal instantiation without the fuss of using Object.create() and returning the object.
  • Subclassing & inheritance: Classes are prototypes of objects that share the same properties and methods. Classes constructed through pseudoclassical instantiation are simply functions instantiated by the keyword new.
  • JavaScript objects: When you realize that the fundamental character of most data structures are mere objects and arrays, sleep comes easy. Objects are versatile, they have special methods, and the rules of insertion, inspection, deletion, and revision of objects are consistent. That makes data structures simple but powerful programming tools.