Introduction of Linked List Implementation
A linked list implementation of a stack in Java is a common data structure used to manage a collection of elements with Last-In-First-Out (LIFO) behavior. In this implementation, we use a singly linked list to represent the stack. Each element (node) in the linked list contains data and a reference to the next element in the stack.
Basic Java implementation of a stack using a linked list:
class Node<T> {
T data;
Node<T> next;
public Node(T data) {
this.data = data;
}
}
class LinkedListStack<T> {
private Node<T> top; // The top of the stack
// Push an element onto the stack
public void push(T data) {
Node<T> newNode = new Node<>(data);
newNode.next = top;
top = newNode;
}
// Pop the top element from the stack
public T pop() {
if (isEmpty()) {
throw new IllegalStateException
("Stack is empty");
}
T data = top.data;
top = top.next;
return data;
}
// Peek at the top element without removing it
public T peek() {
if (isEmpty()) {
throw new IllegalStateException
("Stack is empty");
}
return top.data;
}
// Check if the stack is empty
public boolean isEmpty() {
return top == null;
}
// Get the size of the stack
public int size() {
int count = 0;
Node<T> current = top;
while (current != null) {
count++;
current = current.next;
}
return count;
}
}
public class Main {
public static void main(String[] args) {
LinkedListStack<Integer> stack
= new LinkedListStack<>();
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println("Top element: "
+ stack.peek());
System.out.println("Stack size: "
+ stack.size());
while (!stack.isEmpty()) {
System.out.println("Popped element: "
+ stack.pop());
}
}
}
Adding A Node To The Stack (Push operation)
Adding a node to the stack is referred to as push operation. Pushing an element to a stack in linked list implementation is different from that of an array implementation.
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
class Stack {
Node head;
boolean isEmpty() {
return head == null;
}
void push(int data) {
Node newNode = new Node(data);
newNode.next = head;
head = newNode;
System.out.println
(data + " pushed to the stack.");
}
void display() {
Node current = head;
if (isEmpty()) {
System.out.println
("Stack is empty.");
return;
}
System.out.println("Elements of the stack are:");
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
}
// Example usage:
public class Main {
public static void main(String[] args) {
Stack stack = new Stack();
stack.push(10);
stack.push(20);
stack.push(30);
stack.display();
}
}
Deleting A Node From The Stack (POP operation)
Deleting a node from the top of stack is referred to as pop operation. Deleting a node from the linked list implementation of stack is different from that in the array implementation. In order to pop an element from the stack, we need to follow the following steps :
- Check for the underflow condition: The underflow condition occurs when we try to pop from an already empty stack. The stack will be empty if the head pointer of the list points to null.
- Adjust the head pointer accordingly: In stack, the elements are popped only from one end, therefore, the value stored in the head pointer must be deleted and the node must be freed. The next node of the head node now becomes the head node.
import java.util.Stack;
public class StackExample {
public static void main(String[] args) {
// Creating a stack
Stack<Integer> stack = new Stack<>();
// Pushing elements onto the stack
stack.push(10);
stack.push(20);
stack.push(30);
System.out.println
("Stack before POP operation:");
printStack(stack);
// Performing POP operation
int poppedElement = popFromStack(stack);
System.out.println
("Element popped from the stack:
" + poppedElement);
System.out.println
("Stack after POP operation:");
printStack(stack);
}
// Function to perform POP operation on the stack
private static int popFromStack
(Stack<Integer> stack) {
if (stack.isEmpty()) {
System.out.println
("Stack is empty. Cannot perform POP operation.");
return -1;
// Return a sentinel value indicating failure
}
return stack.pop();
}
// Function to print the elements of the stack
private static void printStack
(Stack<Integer> stack) {
System.out.println("Stack: " + stack);
}
}
