The linked list data structure is one of the fundamental data structures for computer programming.
Implementing a linked list using JavaScript is one of the most popular interview questions for software development related jobs.
This tutorial will help you to understand how the linked list data structure works and how you can implement the data structure using JavaScript in five easy steps.
The finished linked list implementation code can be found in the following GitHub Gist file.
You can download the file and run it using NodeJS on your local computer with the following command:
$ node linked-list
3
10
9
8
Let’s start with a quick introduction to the linked list first.
How linked list data structure works
A linked list is a representation of a list of values like an array, but each item in the list consists of a single object that has two properties:
- The
valueproperty stored inside the object - The
nextproperty that points to the next object
The linked list data structure value can be of any valid JavaScript data types (string, number, boolean, object, etc)
A linked list usually also has two special pointers that refer to the first and last node in the list. They are called head and tail respectively.
Here’s an illustration of a typical linked list:
When implemented, a linked list looks like a list of object that’s linked together through the next property value.
Take a look at the following basic linked list example that has three items:
{
head: {
value: 7, // first value
next: {
value: false, // second value
next: {
value: "A string", // third value
next: null
}
}
}
}
While a linked list looks similar to an array, a linked list is slower because it doesn’t store the index of its values, making random access at a specific index unavailable without traversing the entire linked list from the head to the tail.
Linked list types
There are three known types of linked list data structure:
- Singly linked list where each node only has the
nextpointer - Doubly linked list where each node as both
nextandpreviouspointer - Circular linked list where the
tailnode points to theheadnode, creating a circle.
A circular linked list can be a singly or doubly linked list.
Now that you’ve learned how the data structure works, let’s learn how to implement a linked list using JavaScript next.
This tutorial will focus on implementing a singly, non-circular linked list.
Implementing a linked list using JavaScript
The linked list that you’re going to implement in this tutorial will have the ability to insert and remove nodes both from the head and the tail pointer.
It will also store the current length of the linked list so that you can easily check the size of the list like an array.
To implement a linked list using JavaScript, you can follow these 5 easy steps:
- Create a function for creating a new Node object
- Create the
LinkedListclass with the proper constructor - Create the
insert()andprint()methods - Create the
remove()method to remove nodes - Create the methods to remove and insert from the head
Alright, let’s start with the first step and create a function for creating a new node object.
Creating the list node with a function
A linked list node can be implemented in JavaScript by using a function that returns an object as follows:
function createNode(value) {
return {
value: value,
next: null,
};
}
Now each time you need to create a node object, you just call the createNode() function above and pass the desired value as its argument:
let newNode = createNode("Hello");
console.log(newNode);
// { value: 'Hello', next: null }
You can also implement the node as a JavaScript class as follows:
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
let newNode = new Node("World");
console.log(newNode);
// Node { value: 'World', next: null }
But I personally prefer to use a function over a class, so I’ll use the function implementation for the rest of this tutorial. You are free to use class if you want to though.
Writing the LinkedList class
Next, let’s start writing the LinkedList class implementation with the following constructor:
class LinkedList {
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
}
A new instance of the LinkedList object will have the head and tail pointers refer to the null value, while the length property will start at 0.
These values will be updated as you insert and remove nodes from the instance.
Creating the insert() and print() methods
With the LinkedList class ready, let’s add a method to insert a new node into the class.
First, create an insert() method that accepts a single parameter:
- The
valueof the new node
The syntax of the function is as shown below:
insert(value) {}
First, you need to increment the length property by one. Then, you need to create a new node that will be inserted into the list.
insert(value) {
this.length++;
let newNode = createNode(value); // or use new Node(value);
}
After that, check on the value of the tail property. If the value is not null, then you need to do the following:
- Point the
tail.nextproperty to thenewNodeobject - Point the
tailproperty to thenewNodeobject - Return the
newNodeobject to the caller
When the value of tail is null, it means that the linked list is still empty, so you need to assign the newNode object to the head and tail pointers.
The full code for the insert() method is as follows:
insert(value) {
this.length++;
let newNode = createNode(value);
if (this.tail) {
this.tail.next = newNode;
this.tail = newNode;
return newNode;
}
this.head = this.tail = newNode;
return newNode;
}
Now that you can insert new values into the class instance, let’s add a print() method to see what’s inside the instance.
To print the linked list, you need to create a loop using a while statement from the head node.
If the current node is not null, then print the value property and assign the current.next property to current:
print() {
let current = this.head;
while (current) {
console.log(current.value);
current = current.next;
}
}
Now you can try inserting and printing your linked list:
const linkedList = new LinkedList();
linkedList.insert(7);
linkedList.insert(true);
linkedList.insert(20);
linkedList.print(); // 7 true 20
You have both the insert() and print() methods work. Great job!
Removing nodes from the linked list
Now it’s time to add the remove() method to the LinkedList class.
First, the remove() methods needs to check if the tail pointer is not null.
When the tail pointer is null, you can simply return undefined to the methods caller:
remove() {
if (this.tail) {
// code omitted ...
}
return undefined;
}
When the tail pointer refers to a valid node, then it’s time to execute the code that will remove the node.
The steps to remove the last node is as follows:
- Decrement the
lengthproperty - Search for the node that has the
nextproperty points to thetailnode - Set the
tailto point to the previous node - Set the
tail.nextvalue tonull
Here’s the complete code for the remove() methods:
remove() {
if (this.tail) {
this.length--;
const tailNode = this.tail;
// search for the node before tail
let currentNode = this.head;
// The while loop stops when the node next to tail node is found
while (currentNode.next != tailNode) {
currentNode = currentNode.next;
}
const beforeTail = currentNode;
this.tail = beforeTail;
this.tail.next = null;
return tailNode;
}
return undefined;
}
Now you should be able to remove nodes from a linked list object.
You can stop for a break here, and let’s learn how to insert and remove nodes from the head next when you’re ready.
Creating methodss to insert and remove from the head
To make your linked list implementation more sophisticated, you can add methodss that will insert and remove nodes from the head instead of the tail.
Let’s write a new methods named insertHead() to insert a new node from the head.
The insertHead() methods works just like the insert() methods, but instead of changing the tail and tail.next pointer, you change the newNode.next property to point to the current this.head node and point this.head to the newNode
The code will be as follows:
insertHead(value) {
this.length++;
let newNode = createNode(value);
if (this.head) {
newNode.next = this.head;
this.head = newNode;
return newNode;
}
this.head = this.tail = newNode;
return newNode;
}
Next, you need to create the removeHead() methods that removes a node from the head pointer.
To remove a node from the head, you just need to point this.head pointer to the head.next node:
removeHead() {
if (this.head) {
this.length--;
const removedNode = this.head;
this.head = this.head.next;
return removedNode;
}
return undefined;
}
And with that, you can remove nodes from the head index. Nice work!
Bonus: Add methods to insert and remove a node at a specific index
While there’s nothing wrong with the linked list implementation we’ve created so far, you can still extend the functionalities of your linked list implementation by adding two more methods.
These methods are called insertIndex() and removeIndex() methods, and they allow you to insert and remove a node at a specific index inside your linked list data structure.
Let’s start with the insertIndex() function. This method needs to have two parameters:
- The
valueparameter for the new node’s value - The
indexparameter for the index where the node will be inserted
Write the method syntax as follows:
insertIndex(value, index) {}
First, you need to make sure that the value of the index parameter is smaller than the length value of the linked list.
This is required because the method won’t be able to work properly when the value of index is equal to or higher than the length.
You need to throw an error and stop the method execution inside the if block as shown below:
if (index >= this.length) {
throw new Error("Insert index out of bounds");
}
If you need to learn more about JavaScript throw statement, then you can check out another tutorial I’ve written here:
JavaScript throw statement guide
Next, if the index value is actually zero, then you can call the insertHead() method instead:
if (index === 0) {
return this.insertHead(value);
}
Finally, when the index is not 0, it’s time to start writing the actual code to change your linked list instance.
To insert a new node at a specific index, JavaScript needs to scan the list from the first index and find two nodes:
- The current node at the specified index
- The node located the previous index
The code to find the currentNode and the previousNode looks as follows:
let previousNode = null;
let currentNode = this.head;
for (let i = 0; i < index; i++) {
previousNode = currentNode;
currentNode = currentNode.next;
}
A for statement is used in the code above to quickly traverse the list and grab the desired nodes. This is made possible because we have checked the index value at the beginning of the method.
Without checking if the index value is smaller than the length value, the for loop will cause both previousNode and currentNode value to be null.
This makes you unable to add the new node in the right place.
Next, you need to call the createNode() method to create a newNode out of the value argument passed into the method.
const newNode = createNode(value);
Point the newNode.next property to the currentNode and previousNode.next to the newNode:
newNode.next = currentNode;
previousNode.next = newNode;
Finally, increment the length property and return the newNode to the method caller as follows:
this.length++;
return newNode;
Now your insertIndex() method is finished. Try add a new node on a specific index and print the list.
You’ll see the new node added to the right index:
const linkedList = new LinkedList();
linkedList.insert(6);
linkedList.insert(7);
linkedList.insert(8);
linkedList.insertIndex(20, 1);
console.log(linkedList.length); // 4
linkedList.print(); // 6 20 7 8
From the output above, you can see that the node with value 20 is added right at index 1. Great!
Remove a node at a specific index
Now that you’ve learned how to add a new node at a specific index, removing a node at a specific index will be easy.
First, you need to write the removeIndex() method that accepts one parameter:
- The
indexvalue to remove the node
The method syntax will be like this:
removeIndex(index) {}
Just like with insertIndex(), you need to start with making sure the value of the index parameter is smaller than the length value:
if (index >= this.length) {
throw new Error("Remove index out of bounds");
}
Next, check if the index is equal to zero, and call the removeHead() method if it is:
if (index === 0) {
return this.removeHead();
}
Then, find the previousNode and the currentNode values using a for statement as follows:
let previousNode = null;
let currentNode = this.head;
for (let i = 0; i < index; i++) {
previousNode = currentNode;
currentNode = currentNode.next;
}
Once you find the values, assign the currentNode.next property as the value of the previousNode.next property, decrement the length value, and return the removed node to the method caller:
previousNode.next = currentNode.next;
this.length--;
return currentNode;
And now the removeIndex() method is finished.
You can test the method using the following snippets:
const linkedList = new LinkedList();
linkedList.insert(7);
linkedList.insert(8);
linkedList.insert(9);
linkedList.insert(10);
linkedList.removeIndex(2); // remove 9
console.log(linkedList.length); // 3
linkedList.print(); // 7 8 10
The node at index 2 above is removed, reducing the length and re-arranging the stored data.
You have just added two advanced methods to your linked list implementation. Well done! 👍
Here’s the GitHub Gist link again in case you need to compare it with your code.
Conclusion
With this tutorial, you’ve learned how the linked list data structure works and how to implement one using JavaScript.
You’ve also learned how to create a node object using both JavaScript class and function keywords.
The traditional way to create a node is by creating a new instance of the Node class, but I’d recommend you use the createNode() methods instead because methods are cleaner and simpler.
Next, you can learn about implementing doubly linked list using Javascript.
You can also see how a linked list is implemented in PHP.
Thank you for reading, I hope you’ve learned something new from this tutorial 😉