JavaScript Data Structures: Singly Linked List: Pop

Intro

Last time, we learned how to push a new node to the end of our Singly Linked List.

Today, we learn how to pop something from the list. Pop means remove something from the end.

Current Code

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class SinglyLinkedList {
  constructor() {
    this.length = 0;
    this.head = null;
    this.tail = null;
  }

  push(value) {
    const newNode = new Node(value);
    if (this.length > 0) {
      this.tail.next = newNode;
    } else {
      this.head = newNode;
    }
    this.tail = newNode;
    this.length += 1;
    return newNode;
  }
}

Thoughts

First, we should think about the constraints and possibilities:

If there is currently NO other node in the Singly Linked List (so it is currently empty):

• return null, because we can't remove a node

If there is 1 node in the Singly Linked List:

• find the second to last node (it should become the new tail)
• set its next to null
• set it as tail
• decrease the Singly Linked List's length by 1
• set the Singly Linked List's head and tail to null, because it is empty now
• return the popped node

If there is more than 1 node in the Singly Linked List:

• find the second to last node (it should become the new tail)
• set its next to null
• set it as tail
• decrease the Singly Linked List's length by 1
• return the popped node

Examples:

• 0 nodes: before: null (head & tail) => after: null (head & tail)
• 1 node: before: A (head & tail) => after: null (head & tail)
• 2 nodes: before: A (head) -> B (tail) => after: A (head & tail)
• n nodes: before: A (head) -> ... -> n-1 -> n (tail) => after: A (head) -> ... -> n-1 (tail)

Implementation (Short version, DRY)

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class SinglyLinkedList {
  constructor() {
    this.length = 0;
    this.head = null;
    this.tail = null;
  }

  push(value) {
    const newNode = new Node(value);
    if (!this.length) {
      this.head = newNode;
    } else {
      this.tail.next = newNode;
    }

    this.tail = newNode;
    this.length += 1;
    return newNode;
  }

  pop() {
    // no node in the list, therefore return null
    if (!this.length) {
      return null;
    } else {
      /*
       * find the second to last node (it should become the new tail):
       * - set the current head as currentNode (we always have to start from the List's head node)
       * - set the current head as secondToLastNode (we can't go back a node, therefore we have to save the second to last)
       * - as long as the current node has a next node (so it is not the last node)
       * - then set the current node to the second to last
       * - then set the current node's `next` as the current node
       */
      let currentNode = this.head;
      let secondToLastNode = this.head;
      while (currentNode.next) {
        secondToLastNode = currentNode;
        currentNode = currentNode.next;
      }
      // set the second to last node's `next` to `null` (the second to last should "cut" its connection to the next node)
      secondToLastNode.next = null;
      // set it as `tail`
      this.tail = secondToLastNode;
      // decrease the Singly Linked List's `length` by 1
      this.length -= 1;
      // if the Singly Linked List now is empty, set its `head` and `tail` to `null`
      if (!this.length) {
        this.head = null;
        this.tail = null;
      }
      // return the popped node (found some lines above)
      return currentNode;
    }
  }
}

Result

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

const newSLL = new SinglyLinkedList();
newSLL.push("1");
newSLL.push("2");
console.log(newSLL);
/* SinglyLinkedList {
 *   length: 2,
 *   head: Node { value: '1', next: Node { value: '2', next: null } },
 *   tail: Node { value: '2', next: null }
 * }
 */
console.log(newSLL.pop()); // Node { value: '2', next: null }
console.log(newSLL.pop()); // Node { value: '1', next: null }
console.log(newSLL.pop()); // null
console.log(newSLL); // SinglyLinkedList { length: 0, head: null, tail: null }

---

Next Part

We will implement how to add a node to the beginning of the Singly Linked List. If you want to be notified, subscribe :)