Understanding linked lists using JavaScript

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 of Object-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 a Node class that would represent each Node in the linked list. We then initialized the Node class in the constructor function with the data property before setting the next property to null. The next property was set to null initially because a Node 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 next Node. 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 called setNextNode, which takes Node as an argument. We then ensure that the node argument is an instance of the Node class and not any other data type. Afterward, we set the next property to the Node 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 the Node class:

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

module.exports = Node;

All we're simply doing in the code above is returning the next 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 called LinkedList.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, the Node class is first imported and then a LinkedList 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 called addToHead, which has an argument of data, 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 called currentHead, 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 created Node if it wasn't null. i.e., It would be the Node that newHead links to.

This is a pictorial representation of the final result of the addToHead function. The only thing is that currentHead is null at the first instance, so the linked list will only contain newHead.

Adding to Tail of the Linked List

In our LinkedList.js file, we’ll define a method called addToTail that has one parameter called data.

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 called tail.
2. Next, we instantiate a new node and add it to a new variable called tailNode.
3. Next, check if the head node isn't null. If it is, we just set tailNode 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 new tail 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 to tailNode.

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 our LinkedList class to help us manipulate data, we will be defining one last method called printList to print out the elements in our linked list.

This method uses a while loop to iterate through our linked list, appends each node's data 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 called index.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 the LinkedList class and then instantiate it with a variable called dogBreeds. 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