miku86

Intro

Last time, 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, because to remove data, we first have to add data.

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:

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

// desired list:
               B (head & tail)

Steps:

// 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)

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.

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!