DEV Community

miku86
miku86

Posted on

JavaScript Data Structures: Doubly Linked List: Remove a node at a specific index

#webdev #tutorial #beginners #javascript

Intro

Last time, we learned how to insert a new node at a specific index.

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

Starter Code

We start with code that has the push, shift, pop and get method,
because we can reuse them.

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;
  }

  shift() {
    if (!this.length) {
      return null;
    }

    const nodeToRemove = this.head;

    if (this.length === 1) {
      this.head = null;
      this.tail = null;
    } else {
      this.head = nodeToRemove.next;
      this.head.prev = null;
      nodeToRemove.next = null;
    }

    this.length -= 1;

    return nodeToRemove;
  }

  pop() {
    if (!this.length) {
      return null;
    } else {
      const nodeToRemove = this.tail;

      if (this.length === 1) {
        this.head = null;
        this.tail = null;
      } else {
        this.tail = this.tail.prev;
        this.tail.next = null;
        nodeToRemove.prev = null;
      }

      this.length -= 1;

      return nodeToRemove;
    }
  }

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

Thoughts

First, we should think about the constraints and possibilities:

If the index is invalid (list is empty, index less than 0, greater than or equal to the list's length):

  • return null

If we want to remove the first node (index equals 0):

  • use the shift method to add the data

If we want to remove the last node (index equals length minus 1):

  • use the pop method to add the data

All remaining cases:

  • store the node we want to remove, the node before it and the node after it
  • remove the connections from the node to remove to other nodes
  • update the connections from the node before the node to remove
  • update the connections from the node after the node to remove
  • decrease length by 1
  • return node

Example 

// current list:
A <===> B <===> C
// desired list:
A <===> C
Enter fullscreen mode Exit fullscreen mode

Steps:

// current list:
A <===> B <===> C

// remove the connections from the node to remove to other nodes
A   ==> B <==   C

// update the connections from the node before the node to remove
A   ==> C // A.next to C instead of B
B <==   C // C.prev to B, still

// update the connections from the node after the node to remove
A <===> C // finally, C.prev to A instead of B

// desired list:
A <===> C
Enter fullscreen mode Exit fullscreen mode

=> list after last step equals the desired list

Implementation (Short) 

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;
  }

  shift() {
    if (!this.length) {
      return null;
    }

    const nodeToRemove = this.head;

    if (this.length === 1) {
      this.head = null;
      this.tail = null;
    } else {
      this.head = nodeToRemove.next;
      this.head.prev = null;
      nodeToRemove.next = null;
    }

    this.length -= 1;

    return nodeToRemove;
  }

  pop() {
    if (!this.length) {
      return null;
    } else {
      const nodeToRemove = this.tail;

      if (this.length === 1) {
        this.head = null;
        this.tail = null;
      } else {
        this.tail = this.tail.prev;
        this.tail.next = null;
        nodeToRemove.prev = null;
      }

      this.length -= 1;

      return nodeToRemove;
    }
  }

  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;
    }
  }

  remove(index) {
    // if the index is invalid, return null
    if (!this.length || index < 0 || index >= this.length) {
      return null;
    } else if (index === 0) {
      // if we want to remove the first node
      return this.shift();
    } else if (index === this.length - 1) {
      // if we want to remove the last node
      return this.pop();
    } else {
      // store the node we want to remove, the node before it and the node after it
      const nodeToRemove = this.get(index);
      const prevNodeToRemove = nodeToRemove.prev;
      const nextNodeToRemove = nodeToRemove.next;

      // remove the connections from the node to remove to other nodes
      nodeToRemove.prev = null;
      nodeToRemove.next = null;

      // update the connections from the node before the node to remove
      prevNodeToRemove.next = nextNodeToRemove;

      // update the connections from the node after the node to remove
      nextNodeToRemove.prev = prevNodeToRemove;

      // decrease length by 1
      this.length -= 1;

      // return node
      return nodeToRemove;
    }
  }
}
Enter fullscreen mode Exit fullscreen mode

Result

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

const newDLL = new DoublyLinkedList();
newDLL.push("new 0");
newDLL.push("new 1");
newDLL.push("new 2");

// should be a list with 3 nodes
console.log(newDLL);
// DoublyLinkedList {
//   length: 3,
//   head: <ref *1> Node {
//     value: 'new 0',
//     prev: null,
//     next: Node { value: 'new 1', prev: [Circular *1], next: [Node] }
//   },
//   tail: <ref *2> Node {
//     value: 'new 2',
//     prev: Node { value: 'new 1', prev: [Node], next: [Circular *2] },
//     next: null
//   }
// }

// index invalid
console.log(newDLL.remove(-1));
// null

// index invalid
console.log(newDLL.remove(5));
// null

// should be new 0
console.log(newDLL.remove(0));
// Node { value: 'new 0', prev: null, next: null }

// should be new 2 (we deleted new 0)
console.log(newDLL.remove(1));
// Node { value: 'new 2', prev: null, next: null }

// should be a list with 1 node (we deleted 2 nodes from the initial 3 node list)
console.log(newDLL);
// DoublyLinkedList {
//   length: 1,
//   head: Node { value: 'new 1', prev: null, next: null },
//   tail: Node { value: 'new 1', prev: null, next: null }
// }
Enter fullscreen mode Exit fullscreen mode

Next Part

We will do a small recap of our Doubly Linked List.

If you want to get notified, subscribe!

Top comments (0)