miku86

Intro

Last time, we learned how to add data to the end of our Doubly Linked List.

Today, we'll learn how to pop data from the end 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:

• return null

If the list has one node:

• save current tail (to return it later)
• set the head and the tail to null
• decrease length by 1
• return the old tail

All remaining cases:

• save current tail (to return it later)
• set the node before the current tail as the new tail
• remove the connection from the new tail to the old tail
• remove the connection from the old tail to the new tail
• decrease length by 1
• return old tail

Differences:

• we can see some duplication (save current tail, decrease length, return node)

Example: three nodes

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

Steps:

// current list:
A <===> B        <===> C (tail)
// set the node before the current tail as the new tail:
A <===> B (tail) <===> C
// remove the connection from the new tail to the old tail:
A <===> B (tail) <== C
// remove the connection from the old tail to the new tail:
A <===> B (tail)     C (not connected to list anymore)
// desired list:
A <===> B (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;
  }

  pop() {
    // if empty: return null
    if (!this.length) {
      return null;
    } else {
      // save current tail (to return it later)
      const nodeToRemove = this.tail;

      if (this.length === 1) {
        // after removing the only node, there will be no head and tail
        this.head = null;
        this.tail = null;
      } else {
        // set the node before the current tail as the new tail
        this.tail = this.tail.prev;
        // remove the connection from the new tail to the old tail
        this.tail.next = null;
        // remove the connection from the old tail to the new tail
        nodeToRemove.prev = null;
      }

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

      // return old tail
      return nodeToRemove;
    }
  }
}

Result

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

// create new list and add three nodes
const newDLL = new DoublyLinkedList();
newDLL.push("A");
newDLL.push("B");
newDLL.push("C");
console.log(newDLL);
// DoublyLinkedList {
//   length: 3,
//   head: <ref *1> Node {
//     value: 'A',
//     prev: null,
//     next: Node { value: 'B', prev: [Circular *1], next: [Node] }
//   },
//   tail: <ref *2> Node {
//     value: 'C',
//     prev: Node { value: 'B', prev: [Node], next: [Circular *2] },
//     next: null
//   }
// }

console.log(newDLL.pop());
// Node { value: 'C', prev: null, next: null }

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

Next Part

We will implement our next method for the Doubly Linked List: unshift / add data to the beginning.

If you want to get notified, subscribe!