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

#beginners #tutorial #javascript #webdev

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 }