Introduction

A linked list is a linear collection of data elements, and it's one of the various data structures in computer programming. Its most basic form is a collection of nodes containing data and a link (a pointer to the next node in the list). A linked list allows for easy insertion and deletion of elements (nodes) from any position without reorganizing the whole list compared to the array data structure, which does otherwise.

This article will help us understand how to implement the linked list data structure using the JavaScript programming language.

Prerequisites

To follow along with this article, a basic understanding ofObject-Oriented Programming in JavaScript is required.

Repository

The complete code used throughout this article can be found on GitHub:

https://github.com/folucode/linked-list-javascript

Basic overview of Linked Lists

As stated in the introduction, linked lists contain a sequence of nodes, and each node has a data property and a link to the next node. See the image below:

The node at the beginning of the list is called the head node. The last node in the list is the tail node because its link is null and therefore connects to no other node. The list is terminated at the tail node.

To understand this better, let's consider a one-way road trip passing through different cities (nodes) connected by the road (links). With this example, we'll see that the initial city we started the journey from is the head node, and the final city, our destination, is the tail node.

Throughout this article, we'll be exploring four different operations on linked lists. These operations are:

• Adding nodes
• Removing nodes
• Finding a node
• Iterating through the linked list

Creating a node

Before we can start working with the linked list, we have to create a node which is what makes up a linked list. Each node in a linked list contains two properties, data and a link.

We start by creating a project folder called Linked-List and open it in our text editor. We create a new file -Node.js - in the project folder and add the following code snippet.

class Node {  constructor(data) {    this.data = data;    this.next = null;  }}module.exports = Node;

In the code block above, we created aNode class that would represent eachNode in the linked list. We then initialized theNode class in the constructor function with thedata property before setting thenext property to null. Thenext property was set to null initially because aNode on creation is an orphan node, i.e., a node with no links.

When the Node is first created, the next Node is initially set to null, and there is no way to change it. Let’s create a method in the node class to create the nextNode. To achieve this, we add the following code snippet to our node class:

class Node {  ...  setNextNode(node) {    if (!(node instanceof Node)) {      throw new Error('data must be an instance of Node');    }    this.next = node;  }}module.exports = Node;

Above, we created a new method calledsetNextNode, which takesNode as an argument. We then ensure that the node argument is an instance of theNode class and not any other data type. Afterward, we set thenext property to theNode passed into the function.

Now that we can create a new node and set its next Node, we also want a way to get a node's next Node. i.e., To get the Node linked to a particular node and to do this, add the following code to theNode class:

class Node { ...  getNextNode() {   return this.next;  }}module.exports = Node;

All we're simply doing in the code above is returning thenext property in this function. Now, the final Node class will look like this:

class Node {  constructor(data) {    this.data = data;    this.next = null;  }  setNextNode(node) {    if (!(node instanceof Node)) {      throw new Error('data must be an instance of Node');    }    this.next = node;  }  getNextNode() {    return this.next;  }}module.exports = Node;

Adding to Head of the Linked List

The first operation we will be working on is adding a node to the head of the linked list.

To begin, we’ll create a new file calledLinkedList.js in our current working directory and add the code below:

const Node = require('./Node');class LinkedList {  constructor() {    this.head = null;  }  addToHead(data) {    const newHead = new Node(data);    const currentHead = this.head;    this.head = newHead;    if (currentHead) {      this.head.setNextNode(currentHead);    }  }}module.exports = LinkedList;

In the code above, theNode class is first imported and then aLinkedList class is created. The class is instantiated with its head node being null. This is because we want to be able to add nodes by ourselves.

Next, we create a method calledaddToHead, which has an argument ofdata, which can be of any data type. Then, we create a new node with the data passed into the function and set it to a variable of newHead. We also tracked the current head, which is null initially, in a variable calledcurrentHead, and then set the newly created Node as the head node of the linked list.

Next, we check to see that the former head node (currentHead) wasn't null and set it as the next node of the newly createdNode if it wasn't null. i.e., It would be the Node thatnewHead links to.

This is a pictorial representation of the final result of theaddToHead function. The only thing is thatcurrentHead is null at the first instance, so the linked list will only containnewHead.

Adding to Tail of the Linked List

In ourLinkedList.js file, we’ll define a method calledaddToTail that has one parameter calleddata.

const Node = require('./Node');class LinkedList {  ...  addToTail(data) {    const tail = this.head;    const tailNode = new Node(data);    if (!tail) {      this.head = tailNode;    } else {      while (tail.getNextNode() !== null) {        tail = tail.getNextNode();      }      tail.setNextNode(tailNode);    }  }}module.exports = LinkedList;

A lot is happening in this function so let's break it down:

1. First, we assign the current head node to a variable calledtail.
2. Next, we instantiate a new node and add it to a new variable calledtailNode.
3. Next, check if the head node isn't null. If it is, we just settailNode as the head node. This means there is just one node in the linked list. If not, we'll iterate through the linked list by getting the next Node of each Node in the linked list and check if it is null.
4. If the next node is not null, we assign it to the tail variable and then check again with the newtail value. Note that we have moved to the next element (node) in the linked list.
5. If the next node of the current ‘head’ node we're checking with is null, it means we've gotten to the end of the list and then we set the next node equal totailNode.

Removing the Head of the Linked List

So far, we've learned how to:

• create a new LinkedList with its constructor function
• add a head node to the linked list using.addToHead()
• add a tail node to the linked list using.addToTail()

Now we're going to learn how to remove the head node in the linked list. We will first check if the list has a head node. If it doesn't, it means the linked list is empty. However, If there is a head node, we’ll get it’s next node and set the next node as the new head node of the linked list. Lastly, we’ll return that original head. See the implementation below:

const Node = require('./Node');class LinkedList {  ...  removeHead() {    const removedHead = this.head;    if (!removedHead) return;    this.head = removedHead.getNextNode();    return removedHead.data;  }}module.exports = LinkedList;

Printing the elements in the linked list

Now that we have a handful of helpful methods in ourLinkedList class to help us manipulate data, we will be defining one last method calledprintList to print out the elements in our linked list.

This method uses a while loop to iterate through our linked list, appends each node'sdata property into a string, and then logs it to the console. We keep track of the head node and ensure it isn't null. If it is null, we've reached the end of the linked list, and then the iteration stops. See the implementation below:

const Node = require('./Node');class LinkedList {  ...  printList() {    let currentNode = this.head;    let output = '<head> ';    while (currentNode !== null) {      output += currentNode.data + ' '      currentNode = currentNode.getNextNode();    }    output += '<tail>';    console.log(output);  }}module.exports = LinkedList;

Using the Linked List

To test all we've been working on, we would create a new file in our project folder calledindex.js and then paste the following code into it:

const LinkedList = require('./LinkedList');const dogBreeds = new LinkedList();dogBreeds.addToHead('Bulldog');dogBreeds.addToHead('German Shepard');dogBreeds.addToTail('Poodle');dogBreeds.addToTail('Boxer');dogBreeds.removeHead();dogBreeds.printList();

In this file, we import theLinkedList class and then instantiate it with a variable calleddogBreeds. We then add two elements to the head of the node, two elements to the tail of the node and then remove the head node. Lastly, we print out the result.

To see the result, we would run the command below in our terminal, and we should see the result like so:

$ node index.js<head> Bulldog Poodle Boxer <tail>

Note: Make sure to be in the project directory in the terminal. If not, navigate to the project directory.

Conclusion

In this article we learned how to create and work with linked lists using the JavaScript language.

Resources

You may find these resources helpful.

• Wikipedia
• Tutorials Point