JavaScript Data Structures: Doubly Linked List: Shift / Remove data from the beginning
Tags: beginners, tutorial, javascript, webdev
Published: 2019-12-10 11:08:57

---
title: "JavaScript Data Structures: Doubly Linked List: Shift / Remove data from the beginning"
description: "JavaScript Data Structures: Doubly Linked List: Shift / Remove data from the beginning"
published: true
tags: ["Beginners", "Tutorial", "JavaScript", "Webdev"]
series: JavaScript Data Structures
---

## Intro

[Last time](https://dev.to/miku86/javascript-data-structures-doubly-linked-list-unshift-add-data-to-the-beginning-1gd7), we learned how to unshift / add data to the beginning of our Doubly Linked List.

Today, we'll learn how to shift / remove data from the beginning of our Doubly Linked List.

---

## Starter Code

We start with [code that has the `push` method](https://dev.to/miku86/javascript-data-structures-doubly-linked-list-push-add-data-to-the-end-5ad5), because to remove data, we first have 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;
  }
}
```

---

## Thoughts

First, we should think about the constraints and possibilities:

If the list is empty:

- we can't remove data from an empty list, therefore we return `null`

If the list has 1 element:

- set head as nodeToRemove
- after removing the only element, the list will be empty, so `head` and `tail` should be `null`
- decrease length by 1
- return nodeToRemove

All remaining cases:

- set head as nodeToRemove
- the node after the nodeToRemove should become the new head
- remove both connections from the new head to the old head (our nodeToRemove)
- decrease length by 1
- return nodeToRemove

Differences:

- we can see some duplication (set head as nodeToRemove, decrease length, return nodeToRemove)

---

## Example:

```js
// current list:
A (head) <===> B (tail)

// desired list:
               B (head & tail)
```

Steps:

```js
// current list:
A (head) <===> B (tail)

// the node after the nodeToRemove should become the new head
A        <===> B (head & tail)

// remove both connections from the new head to the old head (our nodeToRemove)
A              B (head & tail)

// desired list:
               B (head & tail)
```

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

  shift() {
    // we can't remove data from an empty list
    if (!this.length) {
      return null;
    }

    // set head as nodeToRemove
    const nodeToRemove = this.head;

    if (this.length === 1) {
      // after removing the only element, the list will be empty, so `head` and `tail` should be `null`
      this.head = null;
      this.tail = null;
    } else {
      // the node after the nodeToRemove should become the new head
      this.head = nodeToRemove.next;

      // remove both connections from the new head to the old head (= nodeToRemove)
      this.head.prev = null;
      nodeToRemove.next = null;
    }

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

    // return nodeToRemove
    return nodeToRemove;
  }
}
```

---

## Result

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

```js
const newDLL = new DoublyLinkedList();
newDLL.push("A");
newDLL.push("B");

// should show two nodes
console.log(newDLL);
// DoublyLinkedList {
//   length: 2,
//   head: <ref *1> Node {
//     value: 'A',
//     prev: null,
//     next: Node { value: 'B', prev: [Circular *1], next: null }
//   },
//   tail: <ref *2> Node {
//     value: 'B',
//     prev: <ref *1> Node {
//       value: 'A',
//       prev: null,
//       next: [Circular *2]
//     },
//     next: null
//   }
// }

// should show node with value A
console.log(newDLL.shift());
// Node { value: 'A', prev: null, next: null }

// should show one node left, B
console.log(newDLL);
// DoublyLinkedList {
//   length: 1,
//   head: Node { value: 'B', prev: null, next: null },
//   tail: Node { value: 'B', prev: null, next: null }
// }
```

---

## Next Part

We will implement our next method for the Doubly Linked List: `get` / get a specific node by its index.

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