Java Stack Implementation using Linked List: In the last post, we learned Java Stack Implementation using Array. Here is the post which explains the implementation of the most useful data structure i.e. Stack using Linked List. First of all, we need to know what actually Stack is and what is its basic operations? So, let’s know about Stack.
Stack: A Stack is an abstract data type that follows a certain principle/rule for its set of operations i.e. insertion, deletion, search, etc. The principle followed by the stack is commonly known as LIFO (Last In First Out) or FILO (First In Last Out). i.e. the set of elements inserted first into the stack will be out at the last and the elements inserted last into the stack will be out first.
Best real Life example to understand Stack:
- A pile of plates in a canteen. The plates are stacked over one another using the LIFO order. The plate kept at first will be used and the plate kept at the bottom will be used at last.
- Undo and Redo process in the computer system: The process of undoing will fetch the last done activity from the Activity Stack and implement it similarly as Stack does through the principle of LIFO or FILO.
| Stack Operations: | |
|---|---|
| Basic Operations | Descriptions of the Operations |
| Push | Insert a new element on the top of the stack. It throws Overflow error if the stack is full. |
| Pop | Removes the topmost element from the stack. It throws Underflow error if the stack is Empty. |
| Peek | Returns the topmost element of the stack. |
| Contains | Check if the stack contains the specified element. |
| isFull | Check if the stack is full i.e. Stack’s capacity is equal to the total size of the stack. |
| isEmpty | Check if the stack is Empty. |
| Size | Returns the total size of the stack array. |
Implementation of Stack using Linked List in Java:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 |
package stacks; //Class Node to represent a single Node having value along with the address of the next node class Node<T>{ T value; Node<T> nextNode; //Single parameter constructor public Node(T value){ this.value = value; this.nextNode = null; } } //Class StackList for different Stack operations public class StackList<T> { //HeadNode refers to the Top Node in the List Node<T> headNode = null; //Push operation of the Stack public void push(T value){ Node<T> newNode = new Node<T>(value); newNode.nextNode = this.headNode; this.headNode = newNode; } //Pop operation of the Stack public void pop(){ if(this.headNode == null){ System.out.println("UnderFlow! The Stack is Empty"); }else{ T val = this.headNode.value; this.headNode = this.headNode.nextNode; System.out.println("The popped Element from the Stack is: " + val); } } //Peek operation of the Stack i.e. returns the First element of the Stack public T peek(){ if(this.headNode == null){ System.out.println("UnderFlow! The Stack is Empty"); return null; }else{ return this.headNode.value; } } //Returns the total size of the Stack public int size(){ if(this.headNode == null){ return 0; }else{ Node<T> tempNode = this.headNode; int count = 0; while(tempNode!=null){ count++; } return count; } } //Contains operation of the Stack public boolean contains(T value){ if(this.headNode == null){ return false; }else{ Node<T> tempNode = this.headNode; while(tempNode!=null){ if(tempNode.value.equals(value)){ return true; } tempNode = tempNode.nextNode; } return false; } } @Override public String toString() { String stackArray = "[ "; Node<T> tempNode = this.headNode; while(tempNode != null){ stackArray += tempNode.value + "-->"; tempNode = tempNode.nextNode; } stackArray += "null ]"; return stackArray; } //Main Function public static void main(String[] args) { StackList<Integer> s1 = new StackList<Integer>(); s1.push(10); s1.push(30); s1.push(50); s1.push(20); s1.push(100); System.out.println(s1); s1.pop(); System.out.println(s1); System.out.println("s1 contains 20 ? " + s1.contains(20)); System.out.println("s1 contains 40 ? " + s1.contains(40)); System.out.println("Peek element of s1: "+ s1.peek()); } } |
The output of the above code Implementation:
|
1 2 3 4 5 6 |
[ 100-->20-->50-->30-->10-->null ] The popped Element from the Stack is: 100 [ 20-->50-->30-->10-->null ] s1 contains 20 ? true s1 contains 40 ? false Peek element of s1: 20 |
That’s it for now. Hope you understood the concepts of Java Stack Implementation using Linked List now.
Read more on Computer Programming articles:-
Contribute to EduTechLearners:-
Please write comments if you want to share more information regarding the above notes. If you want some more notes/books on any of the topics please mail to us or comment below. We will provide you as soon as possible and if you want your’s notes to be published on our site then feel free to contribute on EduTechLearners or email your content to contribute@edutechlearners.com (The contents will be published by your Name).
