How To Implement A Linked List In JavaScript.

After going through the title you might think, why are we even using JavaScript to implement a Linked List, why can’t we just use C++ or Java which support prebuilt DS functions? To be honest, you are not wrong, JavaScript does not support Object-Oriented Programming (OOP) and it does not have any built-in functions for any Data Structures (except Arrays), however with ES-2015, a new class keyword was introduced and we will be taking advantage of that. But again, is implementing Data Structures really hard & is it even worth our efforts?
You will get an answer to this once you go through this article.

Through this article we will try to understand and implement the following:

  • What is a Linked List?
  • How to implement Push and Pop functionality in a Linked List?
  • How to implement Shift and Unshift functionality in a Linked List?
  • How to Insert and Delete a node at any given position in a Linked List?
  • How to Reverse a Linked List?
  • What are the advantages of using a Linked List and where might we use it?

What is a Linked List?

To answer that we will first see what actually do we mean by a Data Structure. Data structures are a collection of values, the relationship among them, which enables efficient access and modification to our data.

So Linked List is a data structure that consists of nodes, and each node has a value and pointer to another node or null.
Head is what we refer to as the starting node of Linked List and Tail is what we call the last node.

As we now know that Linked List is just a collection of nodes, let’s start with creating a node class. A node class will have the property of its value and the next node.

LinkedList Class.

Our Class will have three main parameters, head, tail,& length. By default, the value of head & tail will be null and the value of length will be 0.

Push & Pop

Push & pop is used to add or delete a node at the end of the list.

Push:

With Push, we add a node at the end of our list.

Algorithm:

  • Check for the length, if the length is 0, then, the head & the tail will point to the newly created node.
  • If length is greater than 0, the next property on the tail will then be assigned to the new node, and the tail will then be assigned to our newly created node.
  • Increment the length by 1.
let list = new SinglyLinkedList();
list.push(30);
list.push(31);
list.push(32);

POP

With pop, we can delete the last node in the linked list.

Algorithm:

  • Check for the length of the list, if the length is 0, return undefined.
  • Loop through the list until you reach the tail.
  • Set the next property of second to the last node as null.
  • Set the tail to be the second to the last node.
  • Decrement the length by 1.
list.pop();

Shift & Unshift

Push & Pop is used for adding and removing a node from the end of the list. Contrary to this, shift & unshift is used to remove and add a node from the start of the list.

Shift:

With Shift, we can remove the starting node.

Algorithm:

  • Check for the length of the list, if the length is 0, return undefined.
  • Store the current head property in a variable.
  • Assign the head value to the current head’s next node.
  • Decrement the value by one.
list.shift();

Unshift:

With unshift, we add a node at the beginning of the list.

Algorithm:

  • Create a new node using the value passed to the unshift function.
  • If length is 0, then assign the head & the tail property to the newly created node.
  • Else, set the newly created node’s next property to the current head.
  • Assign the head value to the newly created node.
  • Increment the length by 1.
list.unshift(10);
list.unshift(20);

Insert a node at a given position in a linked list.

Here is when the Linked list becomes a bit difficult. With insertion, we will pass two values, the position/index where we want to add a node & the value of the particular node.

A side note: A linked list with only one element will have a length of 1 & index/position of 0.

Algorithm:

  • If the index is less than 0 or greater than the length, return undefined.
  • If the index is equal to the length, PUSH the new node.
  • If the index is equal to 0, UNSHIFT the new node.
  • Else, Loop through the list until you reach the index -1 Node.
  • Set the next property on that node to our newly created node.
  • Set the next property of the new node to be the previous node’s (index -1 ) next.
  • Increment the length by 1.
list.push(10);
list.push(20);
list.insert(1 , 15)
// O/p => 10 -> 15 -> 20

Remove a node from the given position.

When removing a node from a given position, we need to pass an index/position value to our remove function.

Algorithm:

  • If the index is less than zero or greater and equal to the length, return undefined.
  • If the index is equal to length-1, perform the POP operation.
  • If the index is equal to zero, perform SHIFT operation.
  • Else, Loop through the list until you reach the index -1 Node.
  • Set the next property of that Node to be the next of the next node.
  • Decrement the length by 1.
list.push(20); 
list.push(30);
list.push(40);
list.removeNode(1);
O/P -> "30 removed from index 1"

Reverse a Linked List.

Here we have to reverse a linked list in place, we can’t make a copy or a duplicate and simply return that. So we Reverse as we Traverse.

www.secureservercdn.net

Algorithm:

  • Create two variables called, previous & next, and keep their values as null.
  • Create another variable called current and initialize it to the head property.
  • Now Loop through the list, loop until you have a value for current.
  • Now we set the next property to current's next.
  • The current’s next property should now point to the previous. (This is how we reverse the first element, i.e now our current’s next property will point to null)
  • Now assign previous to current & current to next.
  • Finally, swap the head & tail value and then return the list.

This is one way on how we can reverse a Linked List, we can also use recursion to reverse the linked list. We are not covering the recursion part here, but do let me know if you need an article on the same & I’ll be more than happy to explain it using recursion.

Why use a Linked List?

Linked List is a primary building block of a data structure, to implement a stack or a queue we can use a Linked List. But what other advantages does it provide?

  • Dynamic Data Structure:
    A linked list is a dynamic data structure so it can grow and shrink at runtime by allocating and deallocating memory. So there is no need to give the initial size of a linked list.
  • Insertion and Deletion:
    Unlike in an array, we can easily Insert & Delete a node in Linked List. With adding or removing an element in an array, we need to re-index all the elements present, no such operation needs to be performed when using a Linked List.
  • No memory Wastage:
    As the size of the linked list can increase or decrease at run time so there is no memory wastage. In the case of an array, there is a lot of memory wastage, like if we declare an array of size 10 and store only 6 elements in it then space of 4 elements is wasted.

With some advantages, there are some disadvantages as well, when using a linked list. Here are a few of the disadvantages.

  • Memory Usage:
    More memory is required to store elements in a linked list as compared to an array. Because in the linked list each node contains a pointer and it requires extra memory for itself.
  • No Random Access:
    Unlike in an array, we can’t have random access in a Linked List. By random access, we mean that we can directly find out the fifth element in an array using arr[4]. To retrieve an element in a liked list, we have to traverse the entire list.

Big-O for Linked List Operations:

  • Insertion: O(1)
  • Removal: It depends, Best Time Complexity: O(1), else O(N)
  • Searching: O(N)
  • Access: O(N)

Applications of linked list in the real world:

  1. Image viewer — Previous and next images are linked, hence can be accessed by next and previous button.
  2. Previous and next page in a web browser — We can access the previous and next URL searched in the web browser by pressing back and next button since, they are linked as a linked list.

Conclusion:

We have now learned how to implement a Linked List using JavaScript. Though these operations are not so difficult, you will still want to use programing languages that does support prebuilt DS functions. However, knowing how these operations work will give a deep insight into the Data Structures, also more importantly it will help you a lot in your interview process.

JavaScript Developer

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store