DEV Community

Cover image for JS-DS: LinkedList- A JavaScript Implementation
XenoX profile image Vikas yadav
Vikas yadav for XenoX

Posted on • Edited on

JS-DS: LinkedList- A JavaScript Implementation

#javascript #webdev #programming #jsds

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.

Chain links

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.

LinkedList-chain

Node

A node has two parts

  • Data
  • Pointer or reference to next node

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.

head

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.

Linkedlist tail

In Summery there is three main parts of LinkedList

  • Head
  • Node
  • Tail

Linkedlist

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.

Memory Management

  • 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;
  }
}
Enter fullscreen mode Exit fullscreen mode

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;
};
Enter fullscreen mode Exit fullscreen mode

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;
  }
}
Enter fullscreen mode Exit fullscreen mode

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

Image description

  • 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

Image description

  • 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++;
  }
Enter fullscreen mode Exit fullscreen mode

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;
  }
Enter fullscreen mode Exit fullscreen mode

  • 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

Image description

        const currentNode = this.head;
        node.next = currentNode;
        this.head = node;
Enter fullscreen mode Exit fullscreen mode

  • 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;
  }
Enter fullscreen mode Exit fullscreen mode
  • 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.

Image description

        const previousNode = this._getNodeAt(index - 1);
        node.next = previousNode.next;
        previousNode.next = node;
Enter fullscreen mode Exit fullscreen mode
  • 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`
    );
  }
Enter fullscreen mode Exit fullscreen mode

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);
  }
Enter fullscreen mode Exit fullscreen mode

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;
  }
Enter fullscreen mode Exit fullscreen mode

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;
  }
Enter fullscreen mode Exit fullscreen mode

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.

Image description

  • 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.

Image description

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;
  }
Enter fullscreen mode Exit fullscreen mode

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);
  }
Enter fullscreen mode Exit fullscreen mode

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;
  }
Enter fullscreen mode Exit fullscreen mode

isEmpty()

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

isEmpty() {
    return this.size === 0;
  }
Enter fullscreen mode Exit fullscreen mode

clear()

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

 clear() {
    this.head = null;
    this.count = 0;
  }
Enter fullscreen mode Exit fullscreen mode

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;
    }
  }
Enter fullscreen mode Exit fullscreen mode

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()}]`;
  }
Enter fullscreen mode Exit fullscreen mode

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()}]`;
  }
}
Enter fullscreen mode Exit fullscreen mode

Thank you for reading.

You can play around the code on Codesandbox

Access the repository on Github

GitHub logo thejsdeveloper / JS-DS-LinkedList

Created with CodeSandbox

JS-DS: LinkedList- JavaScript Implementation

linkedlist-js-ds

This repository contains implementation of LinkedList in JavaScript.

To know in detail please refer to my blog in JS-DS series.

Setup

  • Clone the repository
git clone https://github.com/thejsdeveloper/JS-DS-LinkedList.git
Enter fullscreen mode Exit fullscreen mode
  • Enter into JS-DS-LinkedList directory
cd JS-DS-LinkedList
Enter fullscreen mode Exit fullscreen mode
  • To Run
yarn start
Enter fullscreen mode Exit fullscreen mode
  • To run Test Cases
yarn test
Enter fullscreen mode Exit fullscreen mode

Instructions

After running yarn start look into the console of your browser for result

View on GitHub

Read my other articles

XenoX

Special kind of array in Typescript - Tuple

Vikas yadav for XenoX ・ Sep 26 ・ 4 min read

#javascript #webdev #typescript #react
XenoX

JavaScript Jungle: Curious case of sparse array in JS

Vikas yadav for XenoX ・ Sep 19 ・ 3 min read

#javascript #webdev #beginners #development

Follow me on twitter

References

Top comments (0)

Read next

04anilr profile image

What is new feature of React version19

Anil -

andrew_mclean_09 profile image

anyone wanna join me building my first app?(I'm a beginner bare with me)

Andrew Mclean -

dev_girl profile image

Best Memes of Anime Girls Holding Programming Books

Dev Girl -

blamsa0mine profile image

Build a Simple Chatbot with Svelte and ElizaBot

A0mineTV -