JS-DS: LinkedList- A JavaScript Implementation
Tags: javascript, webdev, programming, jsds
Published: 2021-10-18 01:49:59

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 `Array`s which are inbuilt in JavaScript, `LinkedList`s is not inbuilt. Let's briefly know what is LinkedList and then deeply dive into the implementation.


## LinkedList

@vaidehijoshi in her awesome medium [blog](https://medium.com/basecs/whats-a-linked-list-anyway-part-1-d8b7e6508b9d) 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](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/g8vzotniepw1dgpn4rul.jpeg)


## 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](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/l4p20dbq1hy2d7enq5fk.jpeg)

### Node 

A node has two parts

* Data
* Pointer or reference to next node

![Node](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/50sntv6ve4h5vp7wopmy.jpeg)


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](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/xzcebdg4feq5p7e33a9a.jpeg)


## 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](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/7jq56gih7yfp1b702xkf.jpeg)


In Summery there is three main parts of LinkedList


* Head
* Node
* Tail 

![Linkedlist](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/hzmkaq1xxjjkj5a232bz.jpeg)

## Difference between LinkedList and Array

In her [blog](https://medium.com/basecs/whats-a-linked-list-anyway-part-1-d8b7e6508b9d) @vaidehijoshi says: 

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


![Memory Management](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/e42mk58yk367fk7esf56.jpeg)

* 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 `Array`s 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`.  


```js
// 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. 


```js 
// src/linkedlist/utils.js

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

### LinkedList

Now it's time to write our `LinkedList` class. 

```js 
// 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`

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/edaidsmejjfrr6r0tucj.jpeg)

* 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](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/nyd4kzv62ostkzyrklpi.jpeg)

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



```js 
// 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`

```js
 _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`

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/3y0auu07do1740c2vi01.jpeg)

```js
        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.    

```js 
 _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.


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/nhi1t0oesvq7l8plczsl.jpeg)

```js
        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


```js
// 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. 

```js 
  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. 


```js 
  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`.

```js
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. 

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/8fqumcgh2u2yeigdn6cr.jpeg)

* 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](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/zorvuxkyivlhwcmiwsmg.jpeg)

```js
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: 

```js
  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 

```js
  get size() {
    return this.count;
  }
```

### isEmpty() 

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

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

### clear() 

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

```js 
 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](https://dev.to/xenoxdev/javascript-jungle-convert-any-object-to-iterable-40l6). Implementation is as follows : 

```js 

 *[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. 

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

### Whole implementation

```js 
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**


{% codesandbox youthful-goldberg-uqw4k %}


Access the repository on **Github**

{% github https://github.com/thejsdeveloper/JS-DS-LinkedList %}


 
###Read my other articles 

{% link https://dev.to/xenoxdev/special-kind-of-array-tuple-4l1h %}

{% link https://dev.to/xenoxdev/curious-case-of-sparse-array-in-js-38h7 %}

Follow me on [twitter](https://twitter.com/VikasYadav_Dev)

##References

* @vaidehijoshi's [blog] on LinkedList part-1 (https://medium.com/basecs/whats-a-linked-list-anyway-part-1-d8b7e6508b9d)
* @vaidehijoshi's [blog] on LinkedList part-2 (https://medium.com/basecs/whats-a-linked-list-anyway-part-2-131d96f71996)
* @vaidehijoshi's [video Lecture series on LinkedList](https://dev.to/vaidehijoshi/linked-lists--basecs-video-series--2le8)
* Learning Javascript DataStructure [book](https://www.packtpub.com/product/learning-javascript-data-structures-and-algorithms-third-edition/9781788623872)