Link lists in javascript

JavaScript linked list data structure in five easy steps (code example included)

The linked list data structure is one of the fundamental data structures for computer programming.

Implementing a linked list using JavaScript is one of the most popular interview questions for software development related jobs.

This tutorial will help you to understand how the linked list data structure works and how you can implement the data structure using JavaScript in five easy steps.

The finished linked list implementation code can be found in the following GitHub Gist file.

You can download the file and run it using NodeJS on your local computer with the following command:

 Let’s start with a quick introduction to the linked list first.

How linked list data structure works

• The value property stored inside the object
• The next property that points to the next object

The linked list data structure value can be of any valid JavaScript data types (string, number, boolean, object, etc)

A linked list usually also has two special pointers that refer to the first and last node in the list. They are called head and tail respectively.

Here’s an illustration of a typical linked list:

When implemented, a linked list looks like a list of object that’s linked together through the next property value.

Take a look at the following basic linked list example that has three items:

   While a linked list looks similar to an array, a linked list is slower because it doesn’t store the index of its values, making random access at a specific index unavailable without traversing the entire linked list from the head to the tail.

Linked list types

• Singly linked list where each node only has the next pointer
• Doubly linked list where each node as both next and previous pointer
• Circular linked list where the tail node points to the head node, creating a circle.

A circular linked list can be a singly or doubly linked list.

Now that you’ve learned how the data structure works, let’s learn how to implement a linked list using JavaScript next.

This tutorial will focus on implementing a singly, non-circular linked list.

Implementing a linked list using JavaScript

The linked list that you’re going to implement in this tutorial will have the ability to insert and remove nodes both from the head and the tail pointer.

It will also store the current length of the linked list so that you can easily check the size of the list like an array.

• Create a function for creating a new Node object
• Create the LinkedList class with the proper constructor
• Create the insert() and print() methods
• Create the remove() method to remove nodes
• Create the methods to remove and insert from the head

Alright, let’s start with the first step and create a function for creating a new node object.

Creating the list node with a function

A linked list node can be implemented in JavaScript by using a function that returns an object as follows:

Now each time you need to create a node object, you just call the createNode() function above and pass the desired value as its argument:

You can also implement the node as a JavaScript class as follows:

But I personally prefer to use a function over a class, so I’ll use the function implementation for the rest of this tutorial. You are free to use class if you want to though.

Writing the LinkedList class

Next, let’s start writing the LinkedList class implementation with the following constructor:

A new instance of the LinkedList object will have the head and tail pointers refer to the null value, while the length property will start at 0 .

These values will be updated as you insert and remove nodes from the instance.

Creating the insert() and print() methods

With the LinkedList class ready, let’s add a method to insert a new node into the class.

The syntax of the function is as shown below:

First, you need to increment the length property by one. Then, you need to create a new node that will be inserted into the list.

• Point the tail.next property to the newNode object
• Point the tail property to the newNode object
• Return the newNode object to the caller

When the value of tail is null , it means that the linked list is still empty, so you need to assign the newNode object to the head and tail pointers.

The full code for the insert() method is as follows:

Now that you can insert new values into the class instance, let’s add a print() method to see what’s inside the instance.

To print the linked list, you need to create a loop using a while statement from the head node.

If the current node is not null , then print the value property and assign the current.next property to current :

Now you can try inserting and printing your linked list:

You have both the insert() and print() methods work. Great job!

Removing nodes from the linked list

Now it’s time to add the remove() method to the LinkedList class.

First, the remove() methods needs to check if the tail pointer is not null .

When the tail pointer is null , you can simply return undefined to the methods caller:

 When the tail pointer refers to a valid node, then it’s time to execute the code that will remove the node.

• Decrement the length property
• Search for the node that has the next property points to the tail node
• Set the tail to point to the previous node
• Set the tail.next value to null

Here’s the complete code for the remove() methods:

  Now you should be able to remove nodes from a linked list object.

You can stop for a break here, and let’s learn how to insert and remove nodes from the head next when you’re ready.

Creating methodss to insert and remove from the head

To make your linked list implementation more sophisticated, you can add methodss that will insert and remove nodes from the head instead of the tail.

Let’s write a new methods named insertHead() to insert a new node from the head.

The insertHead() methods works just like the insert() methods, but instead of changing the tail and tail.next pointer, you change the newNode.next property to point to the current this.head node and point this.head to the newNode

The code will be as follows:

Next, you need to create the removeHead() methods that removes a node from the head pointer.

To remove a node from the head, you just need to point this.head pointer to the head.next node:

And with that, you can remove nodes from the head index. Nice work!

Bonus: Add methods to insert and remove a node at a specific index

While there’s nothing wrong with the linked list implementation we’ve created so far, you can still extend the functionalities of your linked list implementation by adding two more methods.

These methods are called insertIndex() and removeIndex() methods, and they allow you to insert and remove a node at a specific index inside your linked list data structure.

• The value parameter for the new node’s value
• The index parameter for the index where the node will be inserted

Write the method syntax as follows:

First, you need to make sure that the value of the index parameter is smaller than the length value of the linked list.

This is required because the method won’t be able to work properly when the value of index is equal to or higher than the length .

You need to throw an error and stop the method execution inside the if block as shown below:

If you need to learn more about JavaScript throw statement, then you can check out another tutorial I’ve written here:

Next, if the index value is actually zero, then you can call the insertHead() method instead:

Finally, when the index is not 0 , it’s time to start writing the actual code to change your linked list instance.

The code to find the currentNode and the previousNode looks as follows:

A for statement is used in the code above to quickly traverse the list and grab the desired nodes. This is made possible because we have checked the index value at the beginning of the method.

Without checking if the index value is smaller than the length value, the for loop will cause both previousNode and currentNode value to be null .

This makes you unable to add the new node in the right place.

Next, you need to call the createNode() method to create a newNode out of the value argument passed into the method.

Point the newNode.next property to the currentNode and previousNode.next to the newNode :

Finally, increment the length property and return the newNode to the method caller as follows:

Now your insertIndex() method is finished. Try add a new node on a specific index and print the list.

You’ll see the new node added to the right index:

From the output above, you can see that the node with value 20 is added right at index 1 . Great!

Remove a node at a specific index

Now that you’ve learned how to add a new node at a specific index, removing a node at a specific index will be easy.

The method syntax will be like this:

Just like with insertIndex() , you need to start with making sure the value of the index parameter is smaller than the length value:

Next, check if the index is equal to zero, and call the removeHead() method if it is:

Then, find the previousNode and the currentNode values using a for statement as follows:

Once you find the values, assign the currentNode.next property as the value of the previousNode.next property, decrement the length value, and return the removed node to the method caller:

And now the removeIndex() method is finished.

You can test the method using the following snippets:

The node at index 2 above is removed, reducing the length and re-arranging the stored data.

You have just added two advanced methods to your linked list implementation. Well done! 👍

Here’s the GitHub Gist link again in case you need to compare it with your code.

Conclusion

With this tutorial, you’ve learned how the linked list data structure works and how to implement one using JavaScript.

You’ve also learned how to create a node object using both JavaScript class and function keywords.

The traditional way to create a node is by creating a new instance of the Node class, but I’d recommend you use the createNode() methods instead because methods are cleaner and simpler.

Thank you for reading, I hope you’ve learned something new from this tutorial 😉

Learn JavaScript for Beginners 🔥

Get the JS Basics Handbook, understand how JavaScript works and be a confident software developer.

A practical and fun way to learn JavaScript and build an application using Node.js.

About

Hello! This website is dedicated to help you learn tech and data science skills with its step-by-step, beginner-friendly tutorials.
Learn statistics, JavaScript and other programming languages using clear examples written for people.

Search

Type the keyword below and hit enter

Tags

Click to see all tutorials tagged with:

Источник