Learn how to implement stack using linked list in javascript.
A stack is an ordered collection of data in which data is inserted in LIFO (Last In First Out) order. We will see how to implement it using a object based single linked list in javascript.
List of operations performed on stack
- Push: Adds the item in the stack at the top.
- Pop: Removes the top item from the stack and returns it.
- Peek: Shows the top item from the stack.
- toArray: Convert the stack to the array.
- size: Returns the size of the stack.
- isEmpty: Returns
true
if stack is empty,false
other wise. - clear: Clears the stack.
Implementing stack using single linked list
We will see two different methods to implement stack using linked list in javascript.
1) Using function as a constructor.
2) Using class.
While implementing stack we will use length
to keep track of the size of the stack and head
to keep track of the list.
//Stack using linkedlist function stackUsingLL(){ //Node let Node = function(elm){ this.element = elm; this.next = null; } //To keep track of the size let length = 0; //To keep track of the list let head = null; //Other methods go here }
Push an item in the stack
As in the stack new item are added on the top, If the head is empty then the new node will be the first element, else we will make all the new node of the linked list to be the first node by assigning all the old nodes to the new node.
//Push data in the stack this.push = function(elm){ //Create a new node let node = new Node(elm), current; //Add the new node at the top current = head; node.next = current; head = node; length++; }
Pop an item from the stack
To remove an item from the stack we can just make the head to point the very next element.
//Pop the item from the stack this.pop = function(){ let current = head; //If there is item then remove it //and make the next element as the first if(current){ let elm = current.element; current = current.next; head = current; length--; return elm; } return null; }
Peek the top item in the stack
While peeking just return the first item in the list.
//Return the first element in the stack this.peek = function(){ if(head){ return head.element; } return null; }
Converting stack to an array.
To convert the stack to an array, we can copy all the items to the array and return it.
//Convert the stack to an array this.toArray = function(){ let arr = []; let current = head; while(current){ arr.push(current.element); current = current.next; } return arr; }
Get the size of the stack
Return the length of the stack
//Return the size of the stack this.size = function(){ return length; }
Check if stack is empty
//Check if stack is empty this.isEmpty = function(){ return length === 0; }
Clear the stack
//Clear the stack this.clear = function(){ head = null; length = 0; }
Complete code for stack using linked list
//Stack using linkedlist function stackUsingLL(){ //Node let Node = function(elm){ this.element = elm; this.next = null; } //To keep track of the size let length = 0; //To keep track of the list let head = null; //Push data in the stack this.push = function(elm){ //Create a new node let node = new Node(elm), current; //Add the new node at the top current = head; node.next = current; head = node; length++; } //Pop the item from the stack this.pop = function(){ let current = head; //If there is item then remove it //and make the next element as the first if(current){ let elm = current.element; current = current.next; head = current; length--; return elm; } return null; } //Return the first element in the stack this.peek = function(){ if(head){ return head.element; } return null; } //Convert the stack to an array this.toArray = function(){ let arr = []; let current = head; while(current){ arr.push(current.element); current = current.next; } return arr; } //Check if stack is empty this.isEmpty = function(){ return length === 0; } //Return the size of the stack this.size = function(){ return length; } //Clear the stack this.clear = function(){ head = null; length = 0; } }
Input: let stack = new stackUsingLL(); //creating new instance of Stack stack.push(1); stack.push(2); stack.push(3); console.log(stack.peek()); console.log(stack.isEmpty()); console.log(stack.size()); console.log(stack.pop()); console.log(stack.toArray()); console.log(stack.size()); stack.clear(); //clear the stack console.log(stack.isEmpty()); Output: 3 false 3 3 [2, 1] 2 true
We can make the properties and methods private using closure and IIFE (Immediately Invoked function expression).
let stackUsingLL = (function(){ //Stack using linkedlist return function stack(){ //Node let Node = function(elm){ this.element = elm; this.next = null; } //To keep track of the size let length = 0; //To keep track of the list let head = null; //Push data in the stack this.push = function(elm){ //Create a new node let node = new Node(elm), current; //Add the new node at the top current = head; node.next = current; head = node; length++; } //Pop the item from the stack this.pop = function(){ let current = head; //If there is item then remove it //and make the next element as the first if(current){ let elm = current.element; current = current.next; head = current; length--; return elm; } return null; } //Return the first element in the stack this.peek = function(){ if(head){ return head.element; } return null; } //Convert the stack to an array this.toArray = function(){ let arr = []; let current = head; while(current){ arr.push(current.element); current = current.next; } return arr; } //Check if stack is empty this.isEmpty = function(){ return length === 0; } //Return the size of the stack this.size = function(){ return length; } //Clear the stack this.clear = function(){ head = null; length = 0; } } }());
Class based implementation of stack using linked list in javascript.
We will use two different classes.
1) To create the Nodes.
//Node class Node { constructor(elm){ this.element = elm; this.next = null; } }
2) To implement the stack.
class stackUsingLL { constructor(){ this.length = 0; this.head = null; } //Push data in the stack push = (elm) => { //Create a new node let node = new Node(elm), current; //Add the new node at the top current = this.head; node.next = current; this.head = node; this.length++; } //Pop the item from the stack pop = () => { let current = this.head; //If there is item then remove it //and make the next element as the first if(current){ let elm = current.element; current = current.next; this.head = current; this.length--; return elm; } return null; } //Return the first element in the stack peek = () => { if(this.head){ return this.head.element; } return null; } //Convert the stack to an array toArray = () => { let arr = []; let current = this.head; while(current){ arr.push(current.element); current = current.next; } return arr; } //Check if stack is empty isEmpty = () => { return this.length === 0; } //Return the size of the stack size = () => { return this.length; } //Clear the stack clear = () => { this.head = null; this.length = 0; } }
Input: let stack = new stackUsingLL(); //creating new instance of Stack stack.push(1); stack.push(2); stack.push(3); console.log(stack.peek()); console.log(stack.isEmpty()); console.log(stack.size()); console.log(stack.pop()); console.log(stack.toArray()); console.log(stack.size()); stack.clear(); //Clear the stack console.log(stack.isEmpty()); Output: 3 false 3 3 [2, 1] 2 true
We can also wrap this inside a closure to make the implementation private.
let stackUsingLL = (function(){ //Node class Node { constructor(elm){ this.element = elm; this.next = null; } } return class stack { constructor(){ this.length = 0; this.head = null; } //Push data in the stack push = (elm) => { //Create a new node let node = new Node(elm), current; //Add the new node at the top current = this.head; node.next = current; this.head = node; this.length++; } //Pop the item from the stack pop = () => { let current = this.head; //If there is item then remove it //and make the next element as the first if(current){ let elm = current.element; current = current.next; this.head = current; this.length--; return elm; } return null; } //Return the first element in the stack peek = () => { if(this.head){ return this.head.element; } return null; } //Convert the stack to an array toArray = () => { let arr = []; let current = this.head; while(current){ arr.push(current.element); current = current.next; } return arr; } //Check if stack is empty isEmpty = () => { return this.length === 0; } //Return the size of the stack size = () => { return this.length; } //Clear the stack clear = () => { this.head = null; this.length = 0; } } }());