Implement a Singly Linked List in JavaScript

A LinkedList is a sequential collection of data. Linked List are of two types, Singly Linked List and Doubly Linked List.

In this article, I will discuss how you can use es6 (JavaScript) to implement a Singly Linked List. The example below uses object-oriented features of es6, please refer my previous on Object-Oriented Programming in ES6.

Download the course content below.

Download

Steps to run the code

Unzip the downloaded package and navigate inside the folder
Run npm install
Run npm run start
The above step should open http://localhost:3000 in your browser automatically, if it does not please open the same in a browser.
A debug point is already inserted in the test file, please play with the test now by opening browser debug console.

A Linked List is a linear data structure. It is made up of independent nodes that may contain any type of data like objects, functions, character, number, etc.

1. Singly LinkedList Node

A LinkedList node consists of 2 parts, data – which actually holds the value and next – a reference or pointer to the next node. The node that does not point to any node, should have next = null

Copy

2. Singly LinkedList

A singly Linked List is made up of multiple nodes connected with next (next of node1 points to the node2, next of next2 points to next3 and so on). LinkedList has 3 important parts as:

Head: The first node of the list is known as Head, this is null for an empty list.
Tail: The last node of the list is known as Tail, this is null for an empty list.
Size: Number of elements present in a Linked List. This is 0 for an empty list.

Copy

Linked List allows the following operations:

3. Insertion/add data

Data can be added/inserted to LinkedList in two ways i.e on top – prepending, or at the bottom – appending.

Below is the code which explains how to achieve prepending and appending.

Copy

4. Deletion of a random node containing data

The code below is refactored into 3 methods, deleteHead() – deletes the first node, deleteTail() – deletes the last node and delete(data) – deletes a random node with the given data.

Copy

/**
   * Delete the head - first element.
   *
   * @returns deleted Node
   * @memberof LinkedList
   */
  deleteHead() {
    if (!this._head) {
      return null;
    }

let deletedNode = this._head;

if (this._head.next) {
      this._head = this._head.next;
    } else {
      this._head = null;
      this._tail = null;
    }
    this._size--;

return deletedNode;
  }

/**
   * Delete the Last element.
   *
   * @returns
   * @memberof LinkedList
   */
  deleteTail() {
    //If no elements
    if (!this._tail) {
      return null;
    }
    let deletedNode = this._tail;

//If exactly one elememt present
    if (this._head === this._tail) {
      this._head = null;
      this._tail = null;
      this._size--;

return deletedNode;
    }

return deletedNode;
  }

/**
   * Delete a random node that contains the given data.
   *
   * @param {*} data
   * @returns
   * @memberof LinkedList
   */
  delete(data) {
    // If no Element.
    if (!this._head) {
      return null;
    }

// Check if the data is present in Head node
    if (this._head.data === data) {
      return this.deleteHead();
    }

// Check if data is present in Tail node
    if (this._tail.data === data) {
      return this.deleteTail();
    }

let tempNode = this._head;

while (tempNode.next) {
      //If a match found.
      if (tempNode.next.data === data) {
        let deletedNode = tempNode.next;
        tempNode.next = tempNode.next.next;
        return deletedNode;
      }
      tempNode = tempNode.next;
    }

// If no Node with match data found.
    return null;

}

5. Traverse LinkedList or find a node with the data

Below is the code that implements a find(data) method with the LinkedList basic traversal logic.

Copy

6. The complete LinkedList code

Now, let us look into how the LinkedList class look like after assembling all bits and pieces.

Copy

import LinkedListNode from "./LinkedListNode.js";

export default class LinkedList {
  constructor() {
    this._head = null;
    this._tail = null;
    this._size = 0;
  }

/**
   * Adds the new Node at Head.
   *
   * @param {*} data
   * @returns
   * @memberof LinkedList
   */
  prepend(data) {
    let newNode = new LinkedListNode(data, this._head);
    this._head = newNode;

//if no tail yet, make a new tail node
    if (!this._tail) {
      this._tail = newNode;
    }
    this._size++;

return this;
  }

/**
   * Add to the end of the Linked list.
   *
   * @param {*} data
   * @returns
   * @memberof LinkedList
   */
  append(data) {
    let newNode = new LinkedListNode(data);

if (!this._head) {
      this._head = newNode;
      this._tail = newNode;
    } else {
      this._tail.next = newNode;
      this._tail = newNode;
    }
    this._size++;

return this;
  }

/**
   * Finds the Node with the Given value.
   *
   * @param {*} data
   * @returns
   * @memberof LinkedList
   */
  find(data) {
    if (!this._head) {
      return null;
    }

let tempNode = this._head;
    while (tempNode) {
      if (tempNode.data === data) { //TODO - replace with Comparator
        return tempNode;
      }
      tempNode = tempNode.next;
    }

return null;
  }

// Check if the data is present in Head node
    if (this._head.data === data) {
      return this.deleteHead();
    }

// Check if data is present in Tail node
    if (this._tail.data === data) {
      return this.deleteTail();
    }

let tempNode = this._head;

// If no Node with match data found.
    return null;

}

/**
   * Delete the head - first element.
   *
   * @returns deleted Node
   * @memberof LinkedList
   */
  deleteHead() {
    if (!this._head) {
      return null;
    }

let deletedNode = this._head;
    deletedNode.next = null; //Important

if (this._head.next) {
      this._head = this._head.next;
    } else {
      this._head = null;
      this._tail = null;
    }
    this._size--;

return deletedNode;
  }

/**
   * Delete the first/head element.
   *
   * @memberof LinkedList
   */
  deleteFirst() {
    return this.deleteHead();
  }

//If exactly one elememt present
    if (this._head === this._tail) {
      this._head = null;
      this._tail = null;
      this._size--;

return deletedNode;
    }

return deletedNode;
  }

/**
   * Delete the last element.
   *
   * @memberof LinkedList
   */
  deleteLast() {
    return this.deleteTail();
  }

/**
   * Empty the LinkedList.
   *
   * @returns
   * @memberof LinkedList
   */
  deleteAll() {
    if (!this._head) {
      return this;
    }
    this._head = null;
    this._tail = null;
    this._size = 0;

return this;
  }

/**
   * Convert an Array to LinkedList.
   *
   * @param {*[]} array
   * @returns {LinkedList}
   * @memberof LinkedList
   */
  fromArray(values) {
    values.forEach(value => this.append(value));

return this;
  }

/**
   * LinkedList to Array.
   *
   * @returns {*[]} array
   * @memberof LinkedList
   */
  toArray() {
    let nodes = [];
    let tempNode = this._head;
    while (tempNode) {
      nodes.push(tempNode);
      tempNode = tempNode.next;
    }

return nodes;
  }

/**
   * The size of the LinkedList.
   * 
   * @readonly
   * @memberof LinkedList
   */
  get size() {
    return this._size;
  }
}

7. Test Singly Linked List

You can create a LinkedList as below and write a few test cases to verify the functionalities. You can also try out enterprise level testing tools like Jest, Karma, etc.

Copy

I would love to hear your thoughts on the approach I took in implementing a Singly Linked List in JavaScript. There are off-course many more ways to implement the same. I did not like the way many popular blogs implemented this, so decided to write an article on the same. Happy Coding…