JavaScript Data Structures: Stack: Intro

Intro

After completing the series about the Doubly Linked List, we start with the Stack.

What is a Stack?

• uses the "Last In, First Out"-Principle
• Examples: a stack of cards, a pile of dishes, a browser history
• there are multiple ways to implement a Stack: Array, Singly Linked List, Doubly Linked List

Big O of Stack

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

Example

We will use a Singly Linked List to build our Stack.

A <== B <== C (last)

• C is the last node we pushed (= added) on top of the Stack
• C has a pointer (next) to the next node (B)
• if we pop (= remove) C, the next node on top of the Stack should be B

Setup

We need the following parts to build our Stack:

• a Node with a value and a pointer to the next item in the Stack
• a Stack with a length and a pointer to the last item

// a Node has a value (`value`) and a pointer to the next node (`next`)
class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

// a Stack has a length and a last item (`last`)
class Stack {
  constructor() {
    this.length = 0;
    this.last = null;
  }
}

Thoughts

We set up our Stack. Now we need at least two methods within the Stack:

• a method that pushes a new node on top of the Stack: push
• a method that pops off the last node from the top of the Stack: pop

Next Part

We will implement our first method for the Stack.

If you want to get notified, subscribe!

Questions

• Can you think of some pros or cons of using the Singly Linked List instead of an Array or a Doubly Linked List?