LinkedList- A JavaScript Implementation

In this series which I called JS-DS (JavaScript Data Structure), I will implement various Data Structures in Javascript. The first Data Structure that I am implementing is LinkedList.

One of the widely used data structure is Array in JavaScript. In contrast to Arrays which are inbuilt in JavaScript, LinkedLists is not inbuilt. Let's briefly know what is LinkedList and then deeply dive into the implementation.

LinkedList

@vaidehijoshi in her awesome medium blog post says:

LinkedList is linear data structure, which means that there is a sequence and an order to how it is constructed and traversed.

One of the famous analogy which is given for LinkedList is chain link. You can think of LinkedList as chain link. Each link in the chain is connected to another link to form the whole chain.

Basic building block

As you can see in the picture above, the basic building block of a chain is link, in similar fashion the basic building block of a LinkedList is node.

Node

A node has two parts

• Data
• Pointer or reference to next node

One of the important thing about node is, it only cares about the data it holds and the pointer to next node. Apart from this it does not know anything about other nodes in LinkedList.

Head

First node of the LinkedList is referred as head. When there is no element in LinkedList, the head is null. Head is the starting point of LinkedList.

Tail

The last node of the LinkedList is referred as tail. The tail of the LinkedList points to null as it is the last element in the list.

In Summery there is three main parts of LinkedList

• Head
• Node
• Tail

Difference between LinkedList and Array

In her blog @vaidehijoshi says:

The biggest differentiator between arrays and linked lists is the way that they use memory in our machine.

• Array requires allocation of contiguous memory while in LinkedList the memory allocation is dynamic which means the elements of LinkedList can be anywhere in memory.

• When we add or remove element at start of the Array, it needs to shift all the elements (reindex all the items)

• When we add or remove items from between the elements, array need to be reindexed again.

• When we add more items in the array and it does not have enough memory for items, it will recreate a new array with enough memory (point to note here that it need to find enough contiguous memory again) and copy all the items from the previous array to new array then add our new items.

Adding and deleting items in Arrays is costly operation due to the reindexing, whereas LinkedList do not suffer the same issue.

Implementation of LinkedList

So now when basics are clear. Let's start implementing the LinkedList.

Node

As discussed above, Node has 2 properties:

• data : Contains value of element added
• next : Pointer to next element

To create a Node we need some element or data that we need to add to LinkedList. In ES 6 we have class so let's use it to implement Node.

// src/linkedlist/model.js

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

Equality of node

Equality of nodes is one thing that we need later in our LinkedList implementation.

Anatomy of equals method:

• Take two nodes as params
• Perform some operation to decide whether nodes are equal or not
• Return a boolean

For a default I am going to write a defaultEquals method which simply compares two nodes with === operator.

// src/linkedlist/utils.js

const defaultEquals = (nodeA, nodeB) => {
  return nodeA === nodeB;
};

LinkedList

Now it's time to write our LinkedList class.

// src/linkedlist/linkedlist.js

class LinkedList {
  constructor(equals = defaultEquals) {
    this.equals = equals;
    this.head = null;
    this.count = 0;
  }
}

As you can see LinkedList constructor will take an equals methods which is equal to defaultEquals. If user of the LinkedList want to override the equals, he/she can provide his/her own implementation of the equals method.

We initialise 3 internal properties of LinkedList :

• equals : Which is initialised as passed defaultEquals methods
• head: Pointer to the start of LinkedList. Initialised as null
• count : Keep count of number of elements in LinkedList. Initialised as 0

Methods of LinkedList

• add(element): Takes an element and add it to the list

• insertAt(element, index): Adds the element at the specified index

• addFirst(element): Takes an element and add it to start of the list

• getAt(index): Return the element at the specified index

• indexOf(element): Returns index of the passed the element. If the element do not exist in list it returns -1

• removeAt(index): Removes the element at the specified index and return the removed element

• remove(element): Removes the element if it exist in list and returned the removed element

• size: A getter method which return size of the list

• isEmpty(): Return true if list is empty otherwise return false

• clear(): Clears the list

• toString(): Return the string representation of the list

add(element)

Steps:

• Create the new Node for the passed element.
• Check if the list is empty i.e. size === 0. If yes then it is easy we just assign the node to the head

• If list is not empty we need to go through the whole list to reach to the end of the list. As we know that the last element always points to null so that will be our breaking condition.
• After we find last node, we simply assign the newly created node to the next of last node

• Last but not the least we need to increase the count of the list.

// src/linkedlist/linkedlist.js

add(element) {
    const node = new Node(element);
    if (this.size === 0) {
      this.head = node;
    } else {
      let currentNode = this.head;
      while (currentNode.next !== null) {
        currentNode = currentNode.next;
      }
      currentNode.next = node;
    }

    this.count++;
  }

insertAt(element, index)

Steps:

• First thing we check that the passed index is within the bounds i.e. between 0 and size. For this I have written an utility method _isIndexWithinBound

 _isIndexWithinBound(index) {
    return index >= 0 && index <= this.count;
  }

• If it is not in bounds then we simply throw a Error that the provided index is out of bound

• If the index is within the bounds of list then

• Create the new Node for the passed element.

• If we want to add the element to start of the list i.e. index === 0 then we simply need to point the head to our newly created node and then point the next of new node to the old head

const currentNode = this.head;
node.next = currentNode;
this.head = node;

• If the index is not 0 then we need to find the previous node of the provide index. We need to find it because we need to break the link between previous node and the node at the provided index. To find previous node, I have implemented a utility method _getNodeAt(index), which return node at the provided index.

• In _getNodeAt(index) we start from head and loop until we reach the specified index. Once we reach that index we return the node. If the head is null then we return undefined.

 _getNodeAt(index) {
    if (this._isIndexWithinBound(index)) {
      let currentNode = this.head;
      for (let i = 0; i < index && currentNode !== null; i++)
      {
        currentNode = currentNode.next;
      }
      return currentNode;
    }
    return undefined;
  }

• After we find the previous node using _getNodeAt(previousIndex) then we point the next of previous node to our newly created node and next of our newly created node to the existing node at that index.

const previousNode = this._getNodeAt(index - 1);
node.next = previousNode.next;
previousNode.next = node;

• At last we increase the count and return true to specify that the operation is success.

In summery whole insertAt will be like this

// src/linkedlist/linkedlist.js

insertAt(element, index) {
    if (this._isIndexWithinBound(index)) {
      const node = new Node(element);

      if (index === 0) {
        const currentNode = this.head;
        node.next = currentNode;
        this.head = node;
      } else {
        const previousNode = this._getNodeAt(index - 1);
        node.next = previousNode.next;
        previousNode.next = node;
      }
      this.count++;
      return true;
    }
    throw new Error(
      `IndexOutOfBoundError: Provided index ${index} is not
        within bounds[${0} - ${this.size}] of LinkedList`
    );
  }

addFirst(element):

After implementing insertAt(element, index) it is very easy to implement addFirst. We just need to pass element and index = 0 for adding at the start.

  addFirst(element) {
    return this.insertAt(element, 0);
  }

getAt(index)

To implement getAt(index) we simply use _getNodeAt(index) to get the node at that index and if the node exist then we return data of the node.

  getAt(index) {
    const node = this._getNodeAt(index);
    return node && node.data;
  }

indexOf(element)

Steps

• To find index of provided element we start from head.

• For every node and use our equals method to check that provided node is equal to our current node or not.

• If it is equal to our current node then we return the index.

• If head is null or we have visited all the nodes and we do not find any of the elements to be equal to provided node then we return -1.

indexOf(element) {
    let currentNode = this.head;
    for (let i = 0; i < this.count && currentNode != null;
    i++) {
      if (this.equals(element, currentNode.data)) {
        return i;
      }
      currentNode = currentNode.next;
    }

    return -1;
  }

removeAt(index)

Steps

• First we check that the passed index is within bounds of list.
• Then we check if the index === 0 means we want to delete first node of list. Then we assign second node (this.head.next) to head.

• If index !== 0 then we need to find previous node to provided index. We can find that by using _getNodeAt(index - 1).
• Then we point next of previous node to next node of current node (we can find current node by previousNode.next).
• Lastly we decrease the count and return data of deleted node.

removeAt(index) {
    if (this._isIndexWithinBound(index)) {
      let currentNode = this.head;
      if (index === 0) {
        this.head = currentNode.next;
      } else {
        const previousNode = this._getNodeAt(index - 1);
        currentNode = previousNode.next;
        previousNode.next = currentNode.next;
      }
      this.count--;
      return currentNode.data;
    }
    return undefined;
  }

remove(element)

Now that we know that how to find index of a given element and we also know how to remove a element at a given index.

Combining these two methods, we can implement remove(element) as follows:

  remove(element) {
    const elementIndex = this.indexOf(element);
    return this.removeAt(elementIndex);
  }

get size()

I have implemented size as getter to make it similar to length property in Array. Implementation is very easy, we just return count of the list

  get size() {
    return this.count;
  }

isEmpty()

If the size of the list is 0 then list is empty.

isEmpty() {
    return this.size === 0;
  }

clear()

To clear a list we simply set head to null and reset the count to 0.

 clear() {
    this.head = null;
    this.count = 0;
  }

toString()

I wanted the string implementation of LinkedList to be similar to Java implementation of toString of LinkedList which is something like this:

If we have added 1, 2 and 3 in LinkedList then toString will return [1,2,3]

To make it simpler, I first made this LinkedList iterable by implementing [Symbol.iterator] generator. If you do not know how to make any object in JavaScript iterable. I highly recommend this Convert any object to Iterable blog. Implementation is as follows :

 *[Symbol.iterator]() {
    let currentNode = this.head;
    while (currentNode) {
      yield currentNode.data;
      currentNode = currentNode.next;
    }
  }

Once our LinkedList is iterable we simply take advantage of ... (spread operator) and convert our linkedlist to array and call toString on it.

 toString() {
    return `[${[...this].toString()}]`;
  }

Whole implementation

import { Node } from "./model";
import { defaultEquals } from "./utils";

export class LinkedList {
  constructor(equals = defaultEquals) {
    this.equals = equals;
    this.head = null;
    this.count = 0;
  }

  add(element) {
    const node = new Node(element);
    if (this.size === 0) {
      this.head = node;
    } else {
      let currentNode = this.head;
      while (currentNode.next !== null) {
        currentNode = currentNode.next;
      }
      currentNode.next = node;
    }

    this.count++;
  }

  _isIndexWithinBound(index) {
    return index >= 0 && index <= this.count;
  }

  _getNodeAt(index) {
    if (this._isIndexWithinBound(index)) {
      let currentNode = this.head;
      for (let i = 0; i < index && currentNode !== null; i++) {
        currentNode = currentNode.next;
      }
      return currentNode;
    }
    return undefined;
  }

  getAt(index) {
    const node = this._getNodeAt(index);
    return node && node.data;
  }

  insertAt(element, index) {
    if (this._isIndexWithinBound(index)) {
      const node = new Node(element);

      if (index === 0) {
        const currentNode = this.head;
        node.next = currentNode;
        this.head = node;
      } else {
        const previousNode = this._getNodeAt(index - 1);
        node.next = previousNode.next;
        previousNode.next = node;
      }

      this.count++;

      return true;
    }
    throw new Error(
      `IndexOutOfBoundError: Provided index ${index} is not 
        within bounds[${0} - ${this.size}] of LinkedList`
    );
  }

  addFirst(element) {
    return this.insertAt(element, 0);
  }

  addLast(element) {
    return this.insertAt(element, this.count);
  }

  removeAt(index) {
    if (this._isIndexWithinBound(index)) {
      let currentNode = this.head;
      if (index === 0) {
        this.head = currentNode.next;
      } else {
        const previousNode = this._getNodeAt(index - 1);
        currentNode = previousNode.next;
        previousNode.next = currentNode.next;
      }
      this.count--;
      return currentNode.data;
    }
    return undefined;
  }

  indexOf(element) {
    let currentNode = this.head;
    for (let i = 0; i < this.count && currentNode != null; i++) {
      if (this.equals(element, currentNode.data)) {
        return i;
      }
      currentNode = currentNode.next;
    }

    return -1;
  }

  remove(element) {
    const elementIndex = this.indexOf(element);
    return this.removeAt(elementIndex);
  }

  isEmpty() {
    return this.size === 0;
  }

  get size() {
    return this.count;
  }

  getHead() {
    return this.head;
  }

  getTail() {
    return this.getAt(this.size - 1);
  }

  clear() {
    this.head = null;
    this.count = 0;
  }

  *[Symbol.iterator]() {
    let currentNode = this.head;
    while (currentNode) {
      yield currentNode.data;
      currentNode = currentNode.next;
    }
  }

  toString() {
    return `[${[...this].toString()}]`;
  }
}

Thank you for reading.

You can play around the code on Codesandbox

Access the repository on Github

References

• Vaidehi Joshi's blog on LinkedList part-1
• Vaidehi Joshi's blog on LinkedList part-2
• Vaidehi Joshi's video Lecture series on LinkedList
• Learning Javascript DataStructure book