Stack Implementation using Single LinkedList Java
Stack is one of the most used data structures in computer science. It is a linear data structure which supports ordering of elements in Last In First Out order(LIFO).
The very typical real world example is a stack of plates, where new plates are put on the top of the existing ones and the top ones are the first one to be removed.
There are numerous applications which involve stack in computer science, some of them are,
- Compilers/Run time environments, which use it to store recursive calls.
- Tree Traversals
- Software Applications which provide Undo/Redo operations like text editors.
- Evaluation of mathametical notations like Infix/Postfix etc.
Stack provides the following basic operations,
- Push
Pushes the element to the top of the stack. - Pop
Pops or removes the top element of the stak. - Top
Returns the top element of the stack. - isEmpty
Returns true if the stack is empty or returns a false otherwise. - Size
Returns a integer value which is the number of elements currently in the stack.
Implementation
Typically stack is implemented using,
- Array or a Dynamic Array
- Linked List
The major operations in a stack involve adding and removing elements at the top, if we use an array to implement it, we will end up moving the array elements one step to the right every time there's a push or pop operation which is very expensive.
On the other hand, a linked list allows addition and removal of an element at the start in constant time. Hence we will use a single linkedlist to implement a stack.
We can start with an empty linkedlist where 'head' is null, use it to append elements or remove for push and pop operations.
Psuedo Code
- Push
if head is null
create node with input value
assign head to the new node
else
create node with input value
point's new node's next to head
make the new node as head
- Pop
if head is null
return null
else
store head value to temp
point head to the head's next
return the temp
- Top
if head is null
return null
else
return head's value
- isEmpty
return head==null
Below is the full java implementation for stack using linkedlist,
/*
* Author : Venkatesh Thallam
*/
/*
* Node Definition for the underlying linked list we use to implement stack
* */
class Node {
int val;
Node next;
Node(int val) {
this.val = val;
}
}
public class StackImplementation {
Node head;
StackImplementation() {
head = null;
}
public static void main(String[] args) {
StackImplementation stack = new StackImplementation();
stack.push(8);
stack.push(28);
stack.push(38);
stack.push(48);
stack.push(68);
stack.pop();
stack.push(98);
System.out.println(stack.size());
System.out.println(stack.isEmpty());
System.out.println(stack.top());
}
/*
* Pushes an element to the top of the stack
*/
public void push(int val) {
if (head == null) {
head = new Node(val);
} else {
Node newhead = new Node(val);
newhead.next = head;
head = newhead;
}
}
/*
* Pops the top element and returns it
*/
public Integer pop() {
if (head == null)
return null;
else {
Integer poppedval = head.val;
head = head.next;
return poppedval;
}
}
/*
* Returns a boolean that tells if a stack is empty
*/
public boolean isEmpty() {
return head == null;
}
/*
* Returns the total elements currently in the stack
*/
public int size() {
int count = 0;
Node temp = head;
while (temp != null) {
count++;
temp = temp.next;
}
return count;
}
/*
* Returns the top element of the stack.
*/
public Integer top() {
if (head != null)
return head.val;
else
return null;
}
}
Time Complexity
The time complexity for each of the stack operations is below,
- Push - O(1)
- Pop - O(1)
- Top - O(1)
- isEmpty - O(1)
- Size - O(n), since this requires checking all values of stack.