JavaScript Data Structures: Stack: Pop / Remove the last node

Intro

Last time, we learned how to add a new node to the Stack.

Today, we learn how to pop / remove the node on top of the Stack.


Starter Code

We start with the code from the last part.

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

class Stack {
  constructor() {
    this.length = 0;
    this.last = null;
  }

  push(value) {
    const newNode = new Node(value);

    if (!this.length) {
      this.last = newNode;
    } else {
      newNode.next = this.last;
      this.last = newNode;
    }

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

Thoughts

First, we should think about the constraints and possibilities:

If the Stack is empty:

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

All remaining cases:

  • set the current last node as the node to remove
  • set the last node's next node as the new last node
  • remove the connection from the node to remove to its next node
  • decrease the stack's length by 1
  • return the node

Example

// current stack:
A        <== B (last)

// desired stack:
A (last)

Steps:

// current stack:
A        <== B (last)

// set the last node's next node as the new last node
A (last) <== B

// remove the connection from the node to remove to its next node
A (last)

// desired stack:
A (last)

=> stack after last step equals the desired stack


Implementation

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

class Stack {
  constructor() {
    this.length = 0;
    this.last = null;
  }

  push(value) {
    const newNode = new Node(value);

    if (!this.length) {
      this.last = newNode;
    } else {
      newNode.next = this.last;
      this.last = newNode;
    }

    this.length += 1;
    return newNode;
  }

  pop() {
    // if the Stack is empty, return null, because we can't remove a node
    if (!this.length) {
      return null;
    } else {
      // set the current last node as the node to remove
      const nodeToRemove = this.last;
      // set the last node's next node as the new last node
      this.last = nodeToRemove.next;
      // remove the connection from the node to remove to its next node
      nodeToRemove.next = null;

      // decrease the stack's length by 1
      this.length -= 1;
      // return the node
      return nodeToRemove;
    }
  }
}

Result

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

const newStack = new Stack();
newStack.push("A");
newStack.push("B");

// should have two nodes, B at the top of the stack
console.log(newStack);
// Stack {
//   length: 2,
//   last: Node { value: 'B', next: Node { value: 'A', next: null } }
// }

// remove the top one
console.log(newStack.pop());
// Node { value: 'B', next: null }

// should have one node, A at the top of the stack
console.log(newStack);
// Stack { length: 1, last: Node { value: 'A', next: null } }

// remove the top one
console.log(newStack.pop());
// Node { value: 'A', next: null }

// no node left :C
console.log(newStack);
// Stack { length: 0, last: null }

Next Part

We will do a small recap of our Stack.

If you want to get notified, subscribe!