JavaScript Data Structures: Doubly Linked List: Insert a new node at a specific index
Tags: beginners, tutorial, javascript, webdev
Published: 2019-12-13 14:55:27

---
title: "JavaScript Data Structures: Doubly Linked List: Insert a new node at a specific index"
description: "JavaScript Data Structures: Doubly Linked List: Insert a new node at a specific index"
published: true
tags: ["Beginners", "Tutorial", "JavaScript", "Webdev"]
series: JavaScript Data Structures
---

## Intro

[Last time](https://dev.to/miku86/javascript-data-structures-doubly-linked-list-set-update-a-specific-node-3kd5), we learned how to update a specific node.

Today, we'll learn how to insert a new node at a specific index.

---

## Starter Code

We start with code that has the `push`, `unshift` and `get` method,
because we can reuse them to add data.

```js
class Node {
  constructor(value) {
    this.value = value;
    this.prev = null;
    this.next = null;
  }
}

class DoublyLinkedList {
  constructor() {
    this.length = 0;
    this.head = null;
    this.tail = null;
  }

  push(value) {
    const newNode = new Node(value);
    if (!this.length) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      newNode.prev = this.tail;
      this.tail = newNode;
    }
    this.length += 1;
    return newNode;
  }

  unshift(value) {
    const newNode = new Node(value);

    if (!this.length) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.next = this.head;
      this.head.prev = newNode;
      this.head = newNode;
    }

    this.length += 1;
    return newNode;
  }

  get(index) {
    if (!this.length || index < 0 || index >= this.length) {
      return null;
    } else {
      let currentNode;

      if (index < this.length / 2) {
        let counter = 0;
        currentNode = this.head;

        while (counter < index) {
          currentNode = currentNode.next;
          counter += 1;
        }
      } else {
        let counter = this.length - 1;

        currentNode = this.tail;

        while (counter > index) {
          currentNode = currentNode.prev;
          counter -= 1;
        }
      }

      return currentNode;
    }
  }
}
```

---

## Thoughts

First, we should think about the constraints and possibilities:

If the index is less than 0:

- return null

If the index is greater than the list's length:

- return null

If the index equals 0:

- use the `unshift` method to add the data

If the index equals length:

- use the `push` method to add the data

All remaining cases:

- create a new node
- find the node that is currently before the desired place and connect it to the new node
- find the node that is currently at the desired place and connect it to the new node
- increase the list's length by 1
- return the new node

## Example

```js
// current list:
A <===> B
// desired list:
A <===> X <===> B
```

Steps:

```js
// current list:
A <===> B

// find the node that is currently before the desired place and connect it to the new node
// there is still the connection from B.prev to A
A <===> X
A <==   B

// find the node that is currently at the desired place and connect it to the new node
A <===> X <===> B

// desired list:
A <===> X <===> B
```

=> list after last step equals the desired list

---

## Implementation (Short)

```js
class Node {
  constructor(value) {
    this.value = value;
    this.prev = null;
    this.next = null;
  }
}

class DoublyLinkedList {
  constructor() {
    this.length = 0;
    this.head = null;
    this.tail = null;
  }

  push(value) {
    const newNode = new Node(value);
    if (!this.length) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      newNode.prev = this.tail;
      this.tail = newNode;
    }
    this.length += 1;
    return newNode;
  }

  unshift(value) {
    const newNode = new Node(value);

    if (!this.length) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.next = this.head;
      this.head.prev = newNode;
      this.head = newNode;
    }

    this.length += 1;
    return newNode;
  }

  get(index) {
    if (!this.length || index < 0 || index >= this.length) {
      return null;
    } else {
      let currentNode;

      if (index < this.length / 2) {
        let counter = 0;
        currentNode = this.head;

        while (counter < index) {
          currentNode = currentNode.next;
          counter += 1;
        }
      } else {
        let counter = this.length - 1;

        currentNode = this.tail;

        while (counter > index) {
          currentNode = currentNode.prev;
          counter -= 1;
        }
      }

      return currentNode;
    }
  }

  insert(index, value) {
    // if the index is less than 0 or greater than the list's length, return null
    if (index < 0 || index > this.length) {
      return null;
    } else if (index === 0) {
      // if the index equals 0, use the `unshift` method
      return this.unshift(value);
    } else if (index === this.length) {
      // if the index equals length, use the `push` method
      return this.push(value);
    } else {
      // create new node
      const newNode = new Node(value);

      // find the new previous node
      const newPrevNode = this.get(index - 1);
      // find the new next node
      const newNextNode = newPrevNode.next;

      // connect the new node to the new previous node
      newNode.prev = newPrevNode;
      newPrevNode.next = newNode;

      // connect the new node to the new next node
      newNode.next = newNextNode;
      newNextNode.prev = newNode;

      // increase the list's length by 1
      this.length += 1;

      // return the new node
      return newNode;
    }
  }
}
```

---

## Result

Let's have a look how to use the Doubly Linked List's `insert` method and its results.

```js
const newDLL = new DoublyLinkedList();

// index too low
console.log(newDLL.insert(-1, "too low"));
// null

// shoould display the new node
console.log(newDLL.insert(0, "at 0"));
// Node { value: 'at 0', prev: null, next: null }

// shoould display the new node
console.log(newDLL.insert(1, "at 1"));
// <ref *1> Node {
//   value: 'at 1',
//   prev: Node { value: 'at 0', prev: null, next: [Circular *1] },
//   next: null
// }

// should insert the node between the other two nodes
console.log(newDLL.insert(1, "new at 1"));
// <ref *1> Node {
//   value: 'new at 1',
//   prev: Node { value: 'at 0', prev: null, next: [Circular *1] },
//   next: Node { value: 'at 1', prev: [Circular *1], next: null }
// }

// should show three nodes in the list: at 0 => new at 1 => at 1
console.log(newDLL);
// DoublyLinkedList {
//   length: 3,
//   head: <ref *1> Node {
//     value: 'at 0',
//     prev: null,
//     next: Node { value: 'new at 1', prev: [Circular *1], next: [Node] }
//   },
//   tail: <ref *2> Node {
//     value: 'at 1',
//     prev: Node { value: 'new at 1', prev: [Node], next: [Circular *2] },
//     next: null
//   }
// }
```

---

## Next Part

We will implement our next method for the Doubly Linked List: `remove` a specific node.

If you want to get notified, [subscribe](https://miku86.com/pages/about)!