Linked List in JavaScript

Photo by JJ Ying on Unsplash.

What is linked list?

A linked list is a data structure that is very similar to an array. However in a linked list, we do not store all the elements in a particular memory location. Instead, each element is it’s own separated object that contains a pointer (memory address) to the next element. At the end of a linked list is just a pointer to null (no data/pointer).

Image from GeeksforGeeks

Advantage of Linked List

• Elements can easily be removed or added to a linked list without the modifying the entire data structures.
• To reorganizing the linked list you just need to change the pointers instead of changing the values around.

Disadvantage of Linked List

• Unable to access the middle of the linked list from any point you want.
• Unsuited for operations which requires accessing the elements by index. (Sorting)

Implementing a Linked List in JavaScript

Each node in a linked list only needs two variables. First is the data we are storing, and a pointer to the next node.

Here is an example on how it works.

Next we want to create a class for Linked List. In the constructor all we need is a head pointing to the first node. Initialize it as null, in case if the user didn’t add any node into it.

With this we have created a simple version of Linked List. However we can still improve it and give it more features.

Improvements for Linked List

Let’s go a step and beyond, and start by adding in a size to the linked list. If a linked list is create with a node, the size becomes 1, otherwise it remains 0.

Let’s implement a function called “add”. The purpose of this function is to add an element to the end of the linked list. First, we need to create a few Node with the data. Then we need to check if the head of the linked list is empty or not. If it’s empty, we add the new node straight to the end. Otherwise, we’ll keep going down the list to the last node, and add in the new node.

Make sure we remember to increment the size as well, so we have that data stored and available at any time.

This is only one possible function we can add into the class ourselves. There are other possible functions we can add like:

• insertAt(element, location)
• removeFrom(location)
• removeElement(element)
• printList()
• isEmpty()
• etc…

We can add anything we want to modify the linked list such as it can be similar to an array while maintaining the use of linked list.