JavaScript Data Structures: Stack: Recap

#webdev #javascript #beginners #tutorial

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; } } }