Implementing Linked Lists

Learn how to implement Linked Lists with JavaScript

Mar 14, 20185 min read

Overview:

In this article, I am going to help you learn how to implement Linked Lists using JavaScript.

The bad thing about using JavaScript to implement linked lists is that we cannot use pointers to store addresses of the nodes, which effectuates dynamic memory.

The good thing about using JavaScript to implement linked lists is that we do not have to use pointers to store addresses of the nodes. Also, JavaScript implements dynamic memory out of the box.

The main purpose of this article is to help you learn the basics of linked lists and implement it with any language you prefer.

Setup

To get started, you will need to have node installed in your system. If you are new to need, take the following steps to run your program:

Create a new file with .js extension in your destination folder
Name the file linkedList.js
Open the file in your editor and write a simple hello world program
In your terminal, from the directory your file is in, run:

node linkedList.js

This should execute your hello world program. Now, every time you need to run the program, just the run the above code in your terminal.

What are Linked Lists?

A linked list is a sequence of nodes, where each node stores some data and also keeps track of the next node in the list.

We need to create the node and the list as user defined data types. For JavaScript, we can use it’s class keyword but I am going to stick the the traditional function declaration to build user defined data types. For simplicity, and irony, let’s call them class throughout this article.

Next, we will write a Node class and a LinkedList class.

Node( )

Fundamentally, a node should have two variables, one for storing the data and the other one for storing the next node in the list. We can write it in code as follows:

function Node(data) {   
  this.data = data  
  this.next = null   
}

Every initialization of a Node class now requires a data and the next will always be initialized to null until we add it to a linked list.

LinkedList( )

We are going to write a singly linked list, which is the simplest form of a linked list. The nodes that the list stores should only be the Node class we defined earlier.

It should also keep track of the head of the list, which is also the starting point for all traversals of the list.

Each node in the list should store the next node in the list.

The last node in the list should have null as its next value, which will later help us find the last node in the list.

We can define the LinkedList class as follows:

function LinkedList() {  
  this.head = null  
}

Notice that the linked list does not require a data to initialize. This means that we can initialize an empty linked list when we first declare it. We can declare a new linked list using the new keyword as follows:

let list = new LinkedList()

Push( )

Next thing we need to write is a method for the LinkedList class that will help us insert a node into our linked list.

We are going to write a method that will take a value to use as the data for a new node.

Let’s name the method push( ). It should work like this:

list.push(1)

Now, for this to actually work, we need to create a prototype function for the LinkedList class. We can declare the function as follows:

LinkedList.prototype.push = function(val) {}

Now, we need to use the value to create a new node inside the function, which we can do as follows:

LinkedList.prototype.push = function(val) {  
  let node = new Node(val)  
}

Now, when we use the push method, LinkedList will create a new Node with the push value as it’s data.

The next part of the problem is to store the node in our list. We can do this by finding the last node in the list and changing it’s next value to the new value we are trying to push.

If the list is empty, we can store the node as the head of the list because this node is the first node in the list.

Else if the list already has nodes, we will have to traverse through the list starting from the head until we find the last node in the list. Then, we will have to set the next value of the last node in the list to the node we are trying to push to the list.

We can write this in code as follows:

LinkedList.prototype.push = function(val) {  
  let node = new Node(val)  
  if(!this.head) {  
    this.head = node  
  } else {  
    let currentNode = this.head  
    while(currentNode.next) {  
    currentNode = currentNode.next  
  }  
  currentNode.next = node  
  }  
}

Search( )

Adding a search method to the LinkedList class could be very complex depending on what kind of search you want to perform. For simplicity, we are going to write a method that takes a value as an argument and returns the first Node in the list the the value.

For this to work, we will have to traverse through the list, starting from the head, until we find the node that has the current value and return the node. We can write it in code as follows:

LinkedList.prototype.search = function(val) {  
  let currentNode = this.head  
  while(currentNode.data !== val && currentNode.next) {  
    currentNode = currentNode.next  
  }  
  return currentNode.data === val ? currentNode : null  
}

Delete( )

Writing the delete method is similar to the search method because we need to first find the node with the data we are trying to delete.

The difference is that we also need to keep track off the previous node while we are traversing to search the specified node. We can start by initializing the previous node to null.

Why do we need previous node?

We know that each node contains the next node in the list. So, once we find the node we want to delete, we can remove the node from the list by setting the next value of the previous node to the next value of the node we want to delete.

We can write this in code as follows:

LinkedList.prototype.delete = function(val) {  
  let currentNode = this.head  
  let prevNode = null  
  while(currentNode.data !== val && currentNode.next) {  
    prevNode = currentNode  
    currentNode = currentNode.next  
  }  
   
  if(currentNode.data === val) {  
    prevNode.next = currentNode.next  
  } else {  
    console.log(’Node does not exist’)  
  }  
}

In a nutshell:

Linked list is a very basic linear data structure that prioritizes dynamic memory allocation over runtime of it’s methods. Linked lists are best used in more primitive languages like C and C++. However, we can implement it using any language we prefer it we know the fundamentals of it.

Implementing a linked list requires two user defined data types, one for the node in the list and one as the list itself. We can add any CRUD functionality to it as we like because we are in control writing the data type.

Go ahead and try to implement it in your preferred language.

Happy Coding!