JavaScript Data Structures: Singly Linked List: Remove
Tags: beginners, tutorial, javascript, webdev
Published: 2019-12-01 15:27:46

---
title: "JavaScript Data Structures: Singly Linked List: Remove"
description: "JavaScript Data Structures: Singly Linked List: Remove"
published: true
tags: ["Beginners", "Tutorial", "JavaScript", "Webdev"]
series: JavaScript Data Structures
---

## Intro

[Last time](https://dev.to/miku86/javascript-data-structures-singly-linked-list-insert-3in4), we learned how to insert a new node at any a specific index.

Today, we learn how to remove a node at any specific index.

---

## Current Code

We start with code that has `push`, `shift`, `pop` and `get`, because we can reuse these methods:

- `push` to add some nodes to test the stuff
- `shift` to remove at the beginning of the List
- `pop` to remove at the end of the List
- `get` to get a specific node

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

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

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

    this.tail = newNode;
    this.length += 1;
    return newNode;
  }

  shift() {
    if (!this.length) {
      return null;
    } else {
      const nodeToRemove = this.head;
      this.head = this.head.next;
      this.length -= 1;

      if (!this.length) {
        this.tail = null;
      }

      return nodeToRemove;
    }
  }

  pop() {
    if (!this.tail) {
      return null;
    } else {
      let currentNode = this.head;
      let preTail = this.head;
      while (currentNode.next) {
        preTail = currentNode;
        currentNode = currentNode.next;
      }
      this.tail = preTail;
      this.tail.next = null;
      this.length -= 1;
      if (!this.length) {
        this.head = null;
        this.tail = null;
      }
      return currentNode;
    }
  }

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

      while (count < index) {
        currentNode = currentNode.next;
        count += 1;
      }

      return currentNode;
    }
  }
}
```

---

## Thoughts

First, we should think about the constraints and possibilities:

If we want to remove a node "outside" the List (index is less than 0 or greater than or equal to the length of the current List):

- return null

If we want to remove a node from the beginning of the List (index is 0):

- we can use our `shift` method

If we want to remove a node from the end of the List (index is length - 1):

- we can use our `pop` method

All remaining cases:

- find the node before the nodeToRemove
- set the found node's `next` as the nodeToRemove
- set the nodeToRemove's `next` as the `next` of the node before nodeToRemove

Example:

- current List: A -> B -> C
- we want to remove `B`
- desired List: A -> C

Steps:

- find the node before `B` (=`A`)
- point `A`'s `next` to `B`'s `next` (=`C`)

---

## Implementation (Short version, DRY)

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

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

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

    this.tail = newNode;
    this.length += 1;
    return newNode;
  }

  shift() {
    if (!this.length) {
      return null;
    } else {
      const nodeToRemove = this.head;
      this.head = this.head.next;
      this.length -= 1;

      if (!this.length) {
        this.tail = null;
      }

      return nodeToRemove;
    }
  }

  pop() {
    if (!this.tail) {
      return null;
    } else {
      let currentNode = this.head;
      let preTail = this.head;
      while (currentNode.next) {
        preTail = currentNode;
        currentNode = currentNode.next;
      }
      this.tail = preTail;
      this.tail.next = null;
      this.length -= 1;
      if (!this.length) {
        this.head = null;
        this.tail = null;
      }
      return currentNode;
    }
  }

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

      while (count < index) {
        currentNode = currentNode.next;
        count += 1;
      }

      return currentNode;
    }
  }

  remove(index) {
    // remove a node "outside" the List (=> invalid)
    if (index < 0 || index >= this.length) {
      return null;
    } else if (index === 0) {
      // remove a node from the beginning of the List
      return this.shift();
    } else if (index === this.length - 1) {
      // remove a node from the end of the List
      return this.pop();
    } else {
      // find the node before the nodeToRemove
      const preNodeToRemove = this.get(index - 1);

      // we want to return the removed node later
      const nodeToRemove = preNodeToRemove.next;

      // set the node after the node to remove (=C) as the new node after the node before the node to remove (=A)
      preNodeToRemove.next = nodeToRemove.next; // from A -> B -> C to A -> C

      // decrease the List's length by 1
      this.length -= 1;

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

---

## Result

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

```js
const newSLL = new SinglyLinkedList();
newSLL.push("A");
newSLL.push("B");
newSLL.push("C");

console.log(newSLL);
// SinglyLinkedList {
//   length: 3,
//   head: Node { value: 'A', next: Node { value: 'B', next: [Node] } },
//   tail: Node { value: 'C', next: null }
// }

console.log(newSLL.remove(1));
// Node { value: 'B', next: Node { value: 'C', next: null } }

console.log(newSLL);
// SinglyLinkedList {
//   length: 2,
//   head: Node { value: 'A', next: Node { value: 'C', next: null } },
//   tail: Node { value: 'C', next: null }
// }
```

## Conclusion

We did it. Our Singly Linked List can do a lot of stuff.
If you want to learn something new, here are some ideas:

- Write your own implementation of the methods
- Add checks to prevent wrong user inputs (e.g. text as index)
- Write a test suite
- Add a graphical user interface
- ???