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 beB
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?
Top comments (0)