![Amazon Prime](https://technologystrive.com/images/amazonPrime.jpg)
Stack Using Linked List
Introduction
Stack is a linear data structure to store and manipulate data which follows LIFO (Last In First Out) order during adding and removing elements in it. There are two basic ways to implement stack data structure :
- Array based Implementation
- Using Array or Static Array (Array size is fixed and has to be given during initialization)
- Using Dynamic Arrays or Resizable Arrays (Arrays can grow or shrink based on requirement)
- Linked List Based Implementation
In this post we are going to discuss about linked list based implementation of stack data structure. Before proceeding with this post, it is highly recommended to understand what is linked list and how stack operations are performed.
Prerequisite
In a linked list, whenever we want to add/delete an element we either add/delete at the beginning or at random position or at the end of the linked list. Whereas in case of stack we do restrict add/delete at only one endpoint which is at the end as it follows Last In First Out ordering. So the last node is always the key element for stack operations.
Algorithm
Stack algorithm is defined in terms of adding an element which is called Push and deleting an element from the stack which is called Pop.
Initialization : Add variable last which points to the last node of the linked list. If there are no elements in the stack, it points to null.
Push Operation
- Create a new node for the data given. Let us assume newly created node as newNode
- If stack is empty (no elements left in the stack)
- initialize last to newNode
- Else
- in this case newNode will be the last element and the current last element will be the oldLast element.
- update newNode as the last element.
- the last element next points to the oldLast element.
1void push(int data) :2 Node newNode = new Node(data)34 if(last == null) :5 last = newNode67 else :8 // store oldLast pointer9 Node oldLast = last1011 // update newNode as the last element12 last = newNode1314 // add connection to oldLast element15 last.next = oldLast
Pop Operation
- If stack is empty (last == null)
- throw exception
- Else
- remove the last element
- It means second last element will be the last element which is last.next
1int pop() :2 if(last == null) :3 throw exception45 else :6 Node top = last78 // remove last element by updating last to next element9 last = last.next1011 return top.data
Dry Run
To understand push and pop operations clearly, let us perform below operations. Let us consider we have few balls and we want to place them or delete them on request basis in a container (stack)
Java Implementation
1public class StackUsingLinkedList {2 private Node last ;34 public void push(int data){5 // create new node for the given data6 Node newNode = new Node(data);78 //check stack is empty or not9 if(isEmpty()){10 // initialize last to newly created node11 last = newNode;12 }13 // if stack is not empty14 else {15 Node oldLast = last;1617 // newNode will be always on top18 // and is obviously last element19 last = newNode;2021 // add link to oldLast element22 // as last node next element23 last.next = oldLast;24 }25 }2627 public int pop(){28 // if stack is empty throw exception29 if(isEmpty()){30 throw new RuntimeException("Stack is Empty");31 }32 // take data of the last element33 int data = last.data;3435 // remove last element by36 // updating last to it's next element37 last = last.next;3839 //return data40 return data;41 }4243 // to check which element is on top44 public int peek(){45 if(isEmpty()){46 throw new RuntimeException("Stack is Empty");47 }48 // as stack is not empty49 // last element is always on top of stack50 return last.data;51 }5253 // code to check the stack is empty or not54 public boolean isEmpty(){55 return last == null;56 }5758 // node class59 private static class Node{60 Node next;61 int data;6263 Node(int data){64 this.data = data;65 }66 }6768 public static void main(String[] args) {69 StackUsingLinkedList obj = new StackUsingLinkedList();7071 int data = 20;72 obj.push(data);73 System.out.println("Top Element After pushing "+data+" >>>> "+obj.peek());7475 data = 30;76 obj.push(data);77 System.out.println("Top Element After pushing "+data+" >>>> "+obj.peek());7879 data = 45;80 obj.push(data);81 System.out.println("Top Element After pushing "+data+" >>>> "+obj.peek());8283 // As last element is 45, obj.pop should remove 4584 // and top element should be at 3085 System.out.println("POP >> "+obj.pop());86 System.out.println("Top Element After pop is "+obj.peek());87 }88}