loading...

Understanding and Implementing Linked Lists in JavaScript with ES6 - Implementation

blarzhernandez profile image Roberto Hernandez ・4 min read

This is a continuation of the previous article where we digested all surrounding concepts, pros, and cons, Big O time complexity, real use cases, linked-list mainly operations, and all that kind of theory. If you have not read it yet, I recommend you read it first.

This is a data structure post series with implementation in JavaScript using the ES6 specification.

The aim of this post is to walk through the implementation of a linked list. Actually, this two-posts enclose a linked list itself, since the prior post is pointing to this one.

The Node Class

In the next code, we are going to define our Node class with its constructor. Remember the node is the basic building block to store the data and the next pointer. 

This class will have to handle the node creation. Every time the class is instantiated, the constructor has the responsibility to initialize the two properties: data and next.

alt

Now, the challenge is to create the next four nodes, just nodes creation not how to connect them.

alt

Basically, we have to instantiate four times the Node class in order to create the four nodes.
alt
At this point, we don't care about the second parameter. Why? Because at this moment we are just learning how to create the node without to worry about how they will be connecting together.

How can we connect the nodes?

In the prior code we just created nodes independently, now is time to learn how to connect them to form the linked list.

alt
So, now we have defined the Node class the follow next is to define a new class that will have to handle the next pointer property and the main operations in the linked list. Let's create the LinkedList class.
alt

n the above code, we have just defined a class called LinkedList with its constructor. This has the work to initializing the head property to store the first node and size, to keep track of the size of the linked list.

The follow next, is to offer the ability to insert to the head, to the tail, or at any random position in the list.

Inserting into the Head

alt

We have just created a simple method to add nodes to the head of the Linked list. We are passing down to it the data parameter and setting a value for the this.head property creating a new instance of the Node class.
Let´s do some tests of its implementation so far and see the results.
alt

The output will be next.
alt

Inserting at the Tail

We just learned how to add nodes to the head. So, it's time to know how to add nodes to the tail.
alt

In the aboveinsertToTail function, we are passing down the data parameter and then we created a new instance of the Node class. After that, we are checking if the head is empty if so, the head itself will be set to the new node we have just after created otherwise, set the tail with the head and then loop through the linked list to find the tail and update the tail's next pointer.

Inserting at Random Position

Finally, we are going to see how to insert a new node in the linked list at a given random position. For this, we have to traverse the list until we find the desired position.
alt

Now we are going to test this function using the next tests

alt

The output will be this one. As you can see, at the given index, the node( 600)was added at the second index of the list.

alt

Complete code

Gist Link

I hope you have gained more knowledge about data structure and especially with Linked list. That's all for now. 

Thanks for reading! If this story turned out to be interesting, I’d really appreciate it if you like and share it with your friends. I hope to add a little bit more knowledge to you.
Supporting and follow me on my blog and Medium

Posted on by:

blarzhernandez profile

Roberto Hernandez

@blarzhernandez

React & JavaScript Enthusiast, coding and decoding life => One is More than Zero, Just a Human being and Developer | Blogger@ www.mullinstack.com

Discussion

markdown guide