Linked Lists in JavaScript

Similar to my studying of sorting algorithms, I find the best way to learn something is to know it well enough to be able to teach it. So here goes…

Linked Lists in JavaScript covering:

• what is it?
• why use it?
• how to use it

What is a Linked List?

Well, just like it’s name indicates, this is a list that is linked together. Each item is linked to the next item. Imagine a chain and each link in the chain is connected to the next link.

A simple chain

In the picture above, we have a starting link in the chain, a bunch of links in the middle, and an ending link in the chain. A couple things to note here:

• the start is referred to as the “head”
• the end is referred to as the “tail”
• all links are nodes

EASY! So, head node, a bunch of middle nodes (9 middle nodes in the image) and a tail node (11 nodes total.) Also notice how each node has a “next” node, or node that comes after the current node, EXCEPT the tail node. In this example, this linked list is more specifically a “singly linked list” and this refers to how many pointers each node has: one, to the next node.

But wait! What does that mean?! Is there a doubly linked list?!

Oh yes! Yes there is… in fact, there’s a “doubly linked list” and a “circularly linked list.” With a doubly linked list, each node has a “next” and “previous.” For a circularly linked list, the head node has a previous which points to the tail node, and the tail node has a next which points to the head node, thereby completing the circle.

Back to the singly linked list!

My crude penmanship

So to finalize our conceptualization of a singly linked list, each node has data (could be anything like an object of data about a person, house, etc…) and points to the next node (like an address of the next node.)

You might be asking yourself, “this sounds a lot like an array but more complicated! Why bother?!” That’s a great question!

Why use a Linked List?

Arrays are great, but they’re also terrible. Arrays are great because they’re already built into just about every programming language, they already have an index, so finding something by the index is pretty easy, and they’re easy enough to work with. As an example, if you wanted to add something to the beginning of an array, the computer is going to take the memory for each object in the array, move it over one and then add the new object. This is going to be running O(n) time, which isn’t as fast as it could be. Sure, with a couple objects, this isn’t too bad, but with millions of large objects and millions of users, this could pose a big problem on the server and present a costly situation to explain to the CFO. With a linked list, we can add this new object (node) to the beginning of the list without having to shuffle everything because we’re just giving the new object (node) a pointer to what WAS the head node. This should allow for O(1) time, resulting a much faster computation.

Fortunately, we’re not throwing out arrays today! Arrays still have lots of value, especially when finding a random object in the list. With a linked list, we have to traverse over each node to find what we’re looking for until we find that particular node. With an array, we can just jump right to it because we have an address. It’d be like going to your friends house with the exact address (index from an array) compared to starting at the beginning of the street, knocking on each door to see if your friend lives there (traversing each node in a linked list.)

How to create and use it

So here’s what I think of as the “bummer” part of linked lists: we have to create them because they don’t exist the same way strings (“some string”) and arrays ( [some, array, items] ) do.

First thing to is create a new class called “Node” with data and nextNode values (or null if nothing is passed in. This will simplify things in a bit.)

Awesome! So now that we can create a Node, we need our linked list.

Alright! So this part isn’t too bad, right?! So our head node is defaulting to null and the size is defaulting to 0 because, without anything in our linked list, we don’t really have much of a list, right? We’re also keeping track of the size of the linked list, and this will help out later.

Now, we need to add some functionality to our linked list. Lets start by adding the first node!

With our addFirstNode method, we’ll pass in our data. Here we’re setting this.headNode to a new Node containing the data, and the this.headNode allows for additional nodes to be added to the front instead of erasing everything, and only having a new headNode. We also utilize and increment the size value to keep track of the linked list size.

Let’s also build out a quick function to show our linked list:

And we’ll also initialize a LinkedList and pass it the addFirstNode method.

This will result in creating a LinkedList called “linkedListExample” and then adding a first node with three times, each time with a different value.

First pass

Second pass

Third pass

Ok, so a quick summary of those first passes from above.

1. addFirstNode(300) sets the headNode with a value of 300
2. addFirstNode(200) sets the headNode with a value of 200, and the nextNode points to the node with a value of 300
3. addFirstNode(100) sets the headNode with a value of 100, and the nextNode points to the node with a value of 200

Next, we’re going to add a node at the end of our list.

This is a little more involved, so let’s walk through it.

1. create a variable “node” that is a new Node with the data we’re passing into it.
2. declare another variable “currentNode”
3. if there is not a headNode, then set this.headNode to the node we just created.
4. else, set “currentNode” to the headNode
5. while the currentNode has a nextNode value (meaning it isn’t null like the tail should be) set the currentNode to the nextNode. Just traversing along the list until this while loop returns false. This is what could be a long linear time ( O(n) ) with a massive list.
6. once that while loop returns false, set the nextNode of the currentNode (that has a null nextNode value) to the node we just made.
7. and of course, +1 to the size.

Remember earlier when we set the this.nextNode = nextNode || null ??? Well, that’s coming back to help us out because if we didn’t set it to null there or as a second argument in our addLastNode method, we’d get a tail with a nextNode value of undefined. Oh joy…