How to Create a Linked List in JavaScript

Published in

The Startup

12 min readDec 4, 2020

One of the first things you are told to learn as you wish to progress your career in the world of programming are data structures. My goal is to provide a detailed explanation of how to create a Linked List and explain the logic of each line of code and each step taken in order to implement a fully functioning Linked List.

What exactly is a Linked List? A Linked List is a “complex” data structure that is made up of a group of nodes, or objects, that use pointers to indicate the next node in the list. First open up your text editor, I use VS code, and create a JavaScript file. For the sake of this article let’s call it LinkedList.js

Now for our first lines of code we will declare our variable and assign it the function of creating our Nodes:

const Node = function(value, next = null) {
  this.value = value,
  this.next = next
}

Our nodes are going to have two values, a number and a pointer which is going to point to the next node into the list. We are going to assign two parameters. The first will be that node’s value and the second parameter will be the next node in our linked list. If we omit our second argument when declaring a new instance of Node then the next pointer will point at a value equating null indicating that we have reached the end of our linked list. Our LinkedList function is going to look similar to our Node function. Let’s take a look:

const LinkedList = function() {
  this.head = null;
  this.size = 0;
}
const linked_list = new LinkedList();

The “new” keyword is what makes this function very different from a normal function. Instead of having a return statement inside our LinkedList function we use the new keyword to create a new object with values that are constructed inside our function. In this case we create a linked_list object with the values head which equates to null and size which equates to 0 and store that inside our variable linked_list. So if you log our variable linked_list into the console it looks like this:

console.log(linked_list);
// output:
// linked_list: {
//   head: null, 
//   size: 0
// }

We now have a function that creates linked lists and one that creates nodes…now what? Well our two functions don’t interact with each other at all so we are going to take advantage the fact that both functions are in a global memory space. We are going to go into our LinkedList function and create some new methods. For our first method let’s create some functionality that adds a new node to the beginning of the linked list:

const Node = function(value, next = null) {
  this.value = value,
  this.next = next
}const LinkedList = function() {
  this.head = null;
  this.size = 0;
}LinkedList.prototype.addNodeAtHead = function(value) {
  this.head = new Node(value, this.head);
  this.size++;
  return;
}const linked_list = new LinkedList();
linked_list.addNodeAtHead(1);
linked_list.addNodeAtHead(5);

Prototype is a property that can be used to add methods to existing constructors. In this case our constructor is our linked_list object. When we pass our value of 0 into our addNodeAtHead method we are creating a new node at the beginning of the list and setting the value to 0 and the current head as the next node in the list. The next line takes our size value in our linked_list object will be incremented by one and then we hit our return statement to explicitly exit the method. In this next block I will provide a breakdown as to what is happening inside the object while we call our methods:

const linked_list = new LinkedList();
linked_list.addNodeAtHead(1);
console.log(linked_list);
// output:
// linked_list: {
//   head: Node: {
//   value: 1,
//   next: null
//   },
//   size: 1
// }
linked_list.addNodeAtHead(5);
// output:
// linked_list: {
//   head: Node: {
//   value: 5,
//   next: Node: {
//     value: 1,
//     next: null
//   }},
//   size: 2
// }

So we see that when there is no head node the first node added will take the value of null as the next pointer indicating the end of the list. When there is a head node we take that node and set it to the value of next and reassign the new node to be the head of our linked list. That’s great but now let’s add a node to the end of our linked list:

const LinkedList = function() {
  this.head = null;
  this.size = 0;
}LinkedList.prototype.addNodeAtHead = function(value) {
  this.head = new Node(value, this.head);
  this.size++;
  return;
}LinkedList.prototype.addNodeAtTail = function(value){
  let node = new Node(value); 
  if(!this.head) return this.addNodeAtHead(value);
  let current = this.head;
  while(current.next) {
    current = current.next;
  }
  current.next = node;
  this.size++;
  return;
}

const linked_list = new LinkedList();
linked_list.addNodeAtHead(1);
linked_list.addNodeAtTail(5);

So in order to add a node at the end of the linked list we first need to get to the end of the list to put our new node there. First we assign the value of our new Node with the argument that our method gets passed to a variable called node. If there is no head in our linked_list then we run our method that adds our new node at the head. If we do have a head node then we assign the head of linked_list to a variable called current. While the next value points to an existing node we are going to set current to the next node in our list. Once we have iterated through our linked_list we store our new node in the next pointer of the last node in our linked_list and then we increment the size of our list by 1.

const linked_list = new LinkedList();
linked_list.addNodeAtHead(1);
console.log(linked_list);
// output:
// linked_list: {
//   head: Node: {
//     value: 1,
//     next: null
//   },
//  size: 1
// }
linked_list.addNodeAtTail(5);
// output:
// linked_list: {
//   head: Node: {
//     value: 1,
//     next: Node: {
//       value: 5,
//       next: null
//   }},
//   size: 2
// }

Here we can see that the next pointer of our first node is reassigned to the tail node that we add in our second method. Now what if we want to add a node in the middle of our list. We would simply just create another method to add a value into our linked list at a specific point.

const LinkedList = function() {
  this.head = null;
  this.size = 0;
}LinkedList.prototype.addNodeAtHead = function(value) {
  this.head = new Node(value, this.head);
  this.size++;
  return;
}LinkedList.prototype.addNodeAtTail = function(value){
  let node = new Node(value); 
  if(!this.head) return this.addNodeAtHead(value);
  let current = this.head;
  while(current.next) {
    current = current.next;
  }
  current.next = node;
  this.size++;
  return;
} LinkedList.prototype.addNodeAt = function(value, index) {
   if(index > 0 && index > this.size) return console.log(‘Index does not exist’);
   if(index === 0) return this.addNodeAtHead(value);
   const node = new Node(value);
   let current = this.head;
   let count = 0;
   let previous;
   while(count < index) {
    count++;
    previous = current;
    current = current.next
   }
   previous.next = node;
   node.next = current;
   this.size++;
   return;
}const linked_list = new LinkedList();
linked_list.addNodeAtHead(1);
linked_list.addNodeAtTail(5);
linked_list.addNodeAt(10, 1);

Now this method is a little different from the other two. Adding a node to the head of our linked list required only a value and would push the rest of the nodes down. Similarly adding a node to the end of our linked list we would take our value and iterate through our list until we have reached the last node and then append our new node to the end of our list. With this method we take an index parameter to keep track of how many nodes we have traversed to accurately insert the new node where desired.

In the first line we check index and see if the number is larger than the size of the linked list, if it is we log into the console that the index does not exist and exit the method. If the index exists inside our linked list we can traverse through our list until we get to the position we wish to insert our new Node. If we want our node to be appended at the 0th index or the beginning of our linked list then we simply run our addNodeAtHead method. Next we store our newly created Node with our value to the variable node. We also set the head of our list to current, initialize a count variable starting at 0 and declare previous to be used later. We then compare the values of count and index and while they are not equal we have not yet reached the position we wish to insert our new node so we must traverse the list until count equates to index. We set the previous node’s next value to our new node and then we make the new node’s next value the current node to push the rest of the list down. Don’t forget to increment the size by 1 and again we are done with our method.

const linked_list = new LinkedList();
linked_list.addNodeAtHead(1);
linked_list.addNodeAtTail(5);
console.log(linked_list)
// output:
// linked_list: {
//   head: Node: {
//     value: 1,
//     next: Node: {
//       value: 5,
//       next: null
//   }},
//   size: 2
// }
linked_list.addNodeAt(10, 1);
console.log(linked_list);
// output:
// linked_list: {
//   head: Node: {
//     value: 1,
//     next: Node: {
//       value: 10, 
//       next: Node: {
//         value: 5, 
//         next: null
//   }}},
//   size: 3
// }

Now we have gone over three different ways to add nodes to our linked list. Now let’s test your understanding of what we have learned so far. On your own try to create a method that returns the value of a node at a given index. When you are done continue with this article to view how it should look like.

Now if you have tried to create your own get method it should look something like this:

const LinkedList = function() {
  this.head = null;
  this.size = 0;
}LinkedList.prototype.getNodeAtIndex = function(index) {
  if(index > 0 && index >= this.size || !this.head) return console.log('Index does not exist');
  let current = this.head;
  let count = 0;
  while(current) {
    if(count === index) return console.log(current.value);
    count++;
    current = current.next;
  }
  return null;
}

If you look closely this method slightly resembles our addNodeAt method. First we check if it is possible to reach our inputted index or if we have any nodes in our list. If we do not we return a console log. We assign the value of the head node to a variable labeled current and initialize count to equate 0. while there is a current node we will continuously check if the count is equal to the index we are looking for. Until we reach our desired node we will continue to traverse through our linked list. Once we reach our index we return the value of the current node. If for some reason we do not get a case where count equates to index we return null at the end of the method.

Now let’s tackle removing nodes from our linked list. Removing nodes from our linked list will look similar to adding them just with slightly different logic. Here is the the method for removing the head of our linked list:

const LinkedList = function() {
  this.head = null;
  this.size = 0;
}LinkedList.prototype.removeHeadNode = function() {
  if(!this.head) return console.log('There is no head');
  this.head = this.head.next;
  this.size--;
  return;
}

Firstly we check to see if we have a head node and if we do not then we return a string ‘There is no head.’ If we do have a linked list then we make the next node the new head of the list, decrement the size by one and return out of the method. Here is what our linked list looks like after we remove a head node:

const linked_list = new LinkedList();
linked_list.addNodeAtHead(1);
linked_list.addNodeAtTail(5);
console.log(linked_list)
// output:
// linked_list: {
//   head: Node: {
//     value: 1,
//     next: Node: {
//       value: 5,
//       next: null
//   }},
//   size: 2
// }
linked_list.removeHeadNode();
console.log(linked_list);
// output:
// linked_list: {
//   head: Node: {
//     value: 5,
//     next: null
//   },
//  size: 1
// }

We remove our head node and shift over the next node in our list. Next we will remove the tail node of our linked list. Again feel free to try it yourself before moving on.

Just like our addNodeAtTail method, we are going to traverse the whole linked list and then remove the tail from the list. Here is what it should look like:

const LinkedList = function() {
  this.head = null;
  this.size = 0;
}LinkedList.prototype.removeHeadNode = function() {
  if(!this.head) return console.log('There is no head');
  this.head = this.head.next;
  this.size--;
  return;
}LinkedList.prototype.removeTailNode = function() {
  if(!this.head) return console.log('There is no head');
  if(!this.head.next) return this.removeHeadNode();
  let current = this.head;
  let previous;
  while(current.next){
    previous = current;
    current = current.next;
  }
  previous.next = null;
  this.size--;
  return;
}

In the first line we check to see if there is a linked list. Next if there is a linked list but only a head node then we run our removeHeadNode method. If the list is longer than 1 node then we will start to traverse through until we arrive at the final node. Once the node is taken off the list we decrement by one and return.

Now we have one removal algorithm left. Removing a node at a given index. Try to code out your solution on your own and then continue with this article.

Now we will go over the final removal method.

const LinkedList = function() {
  this.head = null;
  this.size = 0;  LinkedList.prototype.removeHeadNode = function() {
    if(!this.head) return console.log('There is no head');
    this.head = this.head.next;
    this.size--;
    return;
    }  LinkedList.prototype.removeTailNode = function() {
    if(!this.head) return console.log('There is no head');
    if(!this.head.next) return this.removeHeadNode();
    let current = this.head;
    let previous;
    while(current.next){
      previous = current;
      current = current.next;
    }
    previous.next = null;
    this.size--;
    return;
  }
  LinkedList.prototype.removeNodeAt = function(index) {
    if(index > 0 && index >= this.size || !this.head) return console.log('Index not found');
    if(index === 0) return this.removeHeadNode();
    let current = this.head;
    let count = 0;
    let previous;
    while(count < index) {
      count++;
      previous = current;
      current = current.next;
    }
    previous.next = current.next;
    this.size--;
    return;
  }
}

In the first line of this solution we are making sure that index is not greater than the amount of nodes we have to traverse. If we wish to remove the first index then we will run the removeHeadNode method. Once we have established that we have a linked list and we want to remove a node other than the first one we will begin to traverse through our linked list until we have reached the node we wish to remove. We take the next pointer of the previous node and set it to the next node of the current node, cutting out the current node from the linked list. Finally we decrement the size by one and return.

Wow! That is a lot of logic and functionality for our linked list. But there are two more methods I wish to show you. the first will print each nodes values to the console and the second will clear the whole linked list. Here they are:

const LinkedList = function() {
  this.head = null;
  this.size = 0;
}LinkedList.prototype.clearList = function() {
  this.head = null;
  this.size = 0;
  return;
}LinkedList.prototype.printValue = function() {
  let current = this.head;
  while(current) {
    console.log(current.value};
    current = current.next;
}

Our clearList method resets the head to null and the size to 0 totally severing the tie between the linked list and its nodes. As for our printValue method we will start at the head and log the value of each node as we traverse through the list until we get to the end.

Now we have created a fully functional linked list. By the end of this article your LinkedList.js file should look similar to this:

const Node = function(value, next = null) {
  this.value = value,
  this.next = next
}const LinkedList = function() {
  this.head = null;
  this.size = 0;
}LinkedList.prototype.addNodeAtHead = function(value) {
  this.head = new Node(value, this.head);
  this.size++;
  return;
}LinkedList.prototype.addNodeAtTail = function(value){
  let node = new Node(value); 
  if(!this.head) return this.addNodeAtHead(value);
  let current = this.head;
  while(current.next) {
    current = current.next;
  }
  current.next = node;
  this.size++;
  return;
}LinkedList.prototype.addNodeAt = function(value, index) {
  if(index > 0 && index > this.size) return console.log(‘Index does not exist’);
  if(index === 0) return this.addNodeAtHead(value);
  const node = new Node(value);
  let current = this.head;
  let count = 0;
  let previous;
  while(count < index) {
    count++;
    previous = current;
    current = current.next
  }
  previous.next = node;
  node.next = current;
  this.size++;
  return;
}
 
LinkedList.prototype.getNodeAtIndex = function(index) {
  if(index > 0 && index >= this.size || !this.head) return console.log('Index does not exist');
  let current = this.head;
  let count = 0;
  while(current) {
    if(count === index) return console.log(current.value);
    count++;
    current = current.next;
  }
  return null;
}LinkedList.prototype.removeHeadNode = function() {
  if(!this.head) return console.log('There is no head');
  this.head = this.head.next;
  this.size--;
  return;
}LinkedList.prototype.removeTailNode = function() {
  if(!this.head) return console.log('There is no head');
  if(!this.head.next) return this.removeHeadNode();
  let current = this.head;
  let previous;
  while(current.next){
    previous = current;
    current = current.next;
  }
  previous.next = null;
  this.size--;
  return;
}LinkedList.prototype.removeNodeAt = function(index) {
  if(index > 0 && index >= this.size || !this.head) return console.log('Index not found');
  if(index === 0) return this.removeHeadNode();
  let current = this.head;
  let count = 0;
  let previous;
  while(count < index) {
    count++;
    previous = current;
    current = current.next;
  }
  previous.next = current.next;
  this.size--;
  return;
}LinkedList.prototype.clearList = function() {
  this.head = null;
  this.size = 0;
  return;
}LinkedList.prototype.printValue = function() {
  let current = this.head;
  while(current) {
    console.log(current.value);
    current = current.next;
}

Once you have this file saved try testing out each method and make sure it works in the way you expect it to. Thank you for reading and happy hacking!

How to Create a Linked List in JavaScript

Written by Samuel Robles