Understanding linked lists using JavaScript
Tags: javascript, datastructures, algorithms, programming
Published: 2022-05-13 08:50:15

---
title: Understanding linked lists using JavaScript
published: true
description: This article helps the reader to understand the linked list data structure using the JavaScript programming language
tags: #JavaScript #dataStructures #algorithms #programming
cover_image: https://paper-attachments.dropbox.com/s_C972A61B1A3FDB282B7C6FF26D2509CE27B51448E7F1B4A6604EF3E444AE63FD_1652177881926_linked-lists.drawio.png
---
## 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](https://en.wikipedia.org/wiki/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:


![linked lists image](https://paper-attachments.dropbox.com/s_C972A61B1A3FDB282B7C6FF26D2509CE27B51448E7F1B4A6604EF3E444AE63FD_1652177881926_linked-lists.drawio.png)


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.


![linked lists image](https://paper-attachments.dropbox.com/s_C972A61B1A3FDB282B7C6FF26D2509CE27B51448E7F1B4A6604EF3E444AE63FD_1652185439687_linked-lists.drawio+1.png)


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](https://en.wikipedia.org/wiki/Linked_list#:~:text=In%20computer%20science%2C%20a%20linked,which%20together%20represent%20a%20sequence.)
- [Tutorials Point](https://www.tutorialspoint.com/data_structures_algorithms/linked_list_algorithms.htm)