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
Next Part
Now that we have looked at the Stack, we will take a look at the Queue.
Don't miss interesting stuff, subscribe!
Top comments (0)