An Introduction to the Linked List Data Structure Using Javascript

Photo by Karine Avetisyan on Unsplash

Introduction

In JavaScript, like other coding languages, data structures are used to organize and store data, so the developer can easily access the data inside of them later for use in the application, or file. One of the most common and simple structures is the array, which stores an ordered list of data. There is another data structure that is comparable to an array but has its own unique use-cases and advantages over using a simple array. That data structure is the linked list. Now, to understand the linked list let’s take a quick review of the array, so we can compare and contrast the two.

Basics of an Array

In an array, we can store data in an ordered form. For example, let’s say we want to store a list of numbers.

Now to access those numbers we can use a couple of different methods provided by JavaScript, or the simplest way is accessing the index of the number we want to access.

This can be very powerful because we can access data anywhere in the array without having to traverse through the whole list. However, let’s say we now want to insert a new number into the beginning of the list. Doing this is trivial, we just use a simple array method, and add it to the front of the list.

In the diagram above, did you notice how all the indexes of the previous list had to be shifted up one place? Without going too deep into what JavaScript is doing under the hood, the method will now have to shift the index of each element up one place. This can cause some performance loss with larger arrays because it has to do this to the rest of the array.

Linked List: What is it?

A linked list is a linear data structure just like an array, but instead of the data having an index, the order of the data is maintained by a pointer and pointee relationship. Well… that sounds a bit confusing, so let me explain with some illustrations.

Let’s break this down into its main parts: the node (or the data), which stores the data and the pointer, and the list, which stores the nodes as a list.

The Node

The node’s main job is to store two properties:

  • The Data
  • The Pointer (the reference to the next node)

So to illustrate this, take a look at the following code.

First, we create a class so we can easily instantiate nodes. Each instance of that class has a constructor to store the two properties we mentioned earlier: the data and the pointer. We can now easily create nodes to store data and store the next node in the list. Let’s do that now!

Awesome! Now we have five nodes, which store our data, but we are still missing one thing. We need to connect these nodes somehow to make a list. One solution would be to simply assign each node’s next variable to the node instance we want next in the list.

Great! We now have a linked list of nodes, but once again we are still missing something. This method of linking the nodes works nicely when we only need to link nodes together at the end of the list. Another downside is we need to keep track of the last node in the list. In large data sets, this will quickly become unmanageable, so this is where we introduce the list.

The List

Now, creating a LinkedList class will help us organize our nodes into a specific list instance and allow us to create powerful methods to call on the instance. Let’s first start by creating the LinkedList class.

As you can see, we create a LinkedList class that has the property of head. The head property allows us to define the starting Node of the list, which in this case we assign to node1. So, if we were to console.log(list) now we would get the following in our console:

or as a visual:

This gives us a good start. We created an instance of LinkedList , which stores our list in a central location within our code, but this seems to be lacking some functionality. We need to add methods to our LinkedList instance to get some use out of our linked list instance. Let’s add three different methods to our class to do the following:

  • Add a node to the start
  • Add a node to the end
  • Add a node to a specific index

(These examples will brush over the edge cases, and just focus on the main implementation of the methods. If you like, try and solve the edge cases for practice after reading through the article.)

Class Method 1: Add a Node to the Start

This class method is the simplest of the three, only taking two lines of code to complete. On line 8, we first start by setting the next property of the node we want to set as the head, which in this case is the previous head. We then overwrite this.head with the node we passed into the method as an argument. When we console.log out the result we get is something like this:

or as a visual:

Class Method 2: Add a Node to the End

This one has a bit more going on in it compared to the last one, so let’s break it down step-by-step.

On line 10, we create a local variable in the method called current, which is where we will store the current node the while loop will evaluate before entering the loop. If the current.next is not falsy, so in our scenario the value is not null, the while loop will execute and set current to current.next which gives us the next node in our linked list.

We keep going through this loop until eventually, we get to the end of the linked list because the final current.next will be evaluated to false and the while loop will stop and go to the next line of execution.

Now on line 14, since we are no longer in the while loop we can guarantee we are at the end of our linked list, so we set the current.next to the node we passed in as an argument. When we console.log(node5) (the previous end of our linked list), the result we get is something like this:

For clarification, we are starting from our original list instance, before we did list.unshift(node6)

or as a visual:

Class Method 3: Add a Node to a Specific Index

The last method has a very similar structure to our previous method, but they vary slightly in their use of the while loop.

We once again start by setting a local variable of current to be equal to this.head, so we can start traversing the linked list from the beginning. Now, the additional local variable we add to this method is listIndex , which will keep track of the index we are currently at in the linked list since they do not have indexes by default like an array.

The while loop this time will be checking if we have arrived at the listIndex of the node before the index passed in as an argument to the method. If listIndex and index — 1 do not match, the while loop will update the current.next in the same manner as the push method from earlier.

Once the while loop finishes executing current will be the node at the index before the given index argument, so in this case, it’s node2 which we set earlier in this article.

We then do a similar set of steps as we did in the unshift method by first setting node.next to current.next. This gives our node argument the pointer to node3, which previously belonged to node2. Lastly, we need to set the current.next to the node argument, and when we console.log(node2), the result we get is something like this:

or as a visual:

Conclusion: Why Use a Linked List?

After all those examples you may be asking yourself, “Why even bother using a linked list. Using an array is so much easier.” and in most scenarios, you would be 100% correct. The linked list is a less commonly used data structure in JavaScript because its use-cases are somewhat limited in the language. In front-end applications, we see arrays and regular JavaScript objects as commonplace in the major frameworks (React, Vue, etc.) for storing data.

However, with that said, linked lists still play a role in low-level languages, such as C and C++, where you must specify how long the array is going to be so the application can allocate memory for the it. Without going into too much detail, in these languages, the array will be allocated as one, sequential block in memory. This can cause performance issues later on during the runtime if the array needs additional spots in memory or you allocate too much space for the array from the start.

Since linked lists can be set at run time, and their location in-memory does not have to be in a sequential block (because of the use of pointers), it makes them a prime candidate in scenarios where the cons of arrays outweigh the pros. In comparison, the same can be stated for arrays that excel in their ability to randomly access data using an index, which gives them a speed advantage over linked lists that must traverse the list linearly.

This is a very simplified explanation of what is going on with arrays and linked lists in these languages. To learn more about this topic and overall about the linked list, check out these resources:

Full Stack Web Development Student at Lighthouse Labs