DEV Community

miku86
miku86

Posted on

JavaScript Data Structures: Doubly Linked List: Shift / Remove data from the beginning

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

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

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)
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() {
    // 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;
  }
}
Enter fullscreen mode Exit fullscreen mode

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

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!

Top comments (0)