JavaScript Data Structures: Stack: Recap

Intro

Last time, we added the last method.

I hope you learned something about the concept of a Stack and tried your best to implement it on your own.

Thoughts about the Stack

We implemented the Stack using a Singly Linked List.

The Stack data structure is a very important concept, because we use it all the time.

The fundamental difference to the Singly and Doubly Linked List is the fact, that we only add and remove a node to/from the top of the Stack, so we use the "Last In, First Out"-Principle.

Examples in real life are a stack of cards, a pile of dishes, a browser history.

• Access: O(N)
• Search: O(N)
• Insert: O(1)
• Remove: O(1)

Final Implementation

Our Stack has these methods:

• push, to add a node to the top of the stack
• pop, to remove the top node from the stack

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 (!this.length) {
      return null;
    } else {
      const nodeToRemove = this.last;
      this.last = nodeToRemove.next;
      nodeToRemove.next = null;

      this.length -= 1;
      return nodeToRemove;
    }
  }
}

Further Reading

• Wikipedia: Stack
• Wikibooks: Stack
• Wikipedia: Call Stack
• Wikipedia: Stack Overflow

Next Part

Now that we have looked at the Stack, we will take a look at the Queue.

Don't miss interesting stuff, subscribe!