How to Implement a Stack Using Linked List in Java with Comprehensive Examples for Programmers
- Ashish Vashisht
- Apr 22
- 4 min read
Stacks are a core data structure in programming, used in many algorithms and scenarios where a last-in, first-out (LIFO) structure is needed. Implementing a stack with a linked list provides the advantage of dynamic memory allocation compared to its array-based counterpart. In this article, we will explore how to implement a stack using a linked list in Java, enhanced with practical examples for better clarity.
Understanding Stacks
Before we jump into the implementation, let’s clarify what a stack is. A stack is a linear data structure that operates on the LIFO principle. This means the last element added to the stack is the first one to be removed. Stacks are commonly used for various purposes in programming, such as:
Function Call Management: Keeping track of active functions in programming languages.
Expression Parsing: Evaluating mathematical expressions or parsing syntax in compilers.
Backtracking Algorithms: Managing paths in search algorithms, like depth-first search.
Key Operations
A standard stack supports several key operations:
Push: Adds an element to the top of the stack.
Pop: Removes the element from the top of the stack.
Peek: Allows viewing the top element without removing it.
IsEmpty: Checks if the stack is empty.
In our implementation, we will handle these operations using a linked list.
Why Use a Linked List?
Utilizing a linked list to implement a stack has distinct advantages:
Dynamic Size: No need for a preset maximum size; the stack can grow and shrink as needed.
Efficient Memory Utilization: Memory is allocated when nodes are created. This feature is particularly beneficial when handling varying amounts of data. For instance, if you needed to store 1000 elements today and 10,000 tomorrow, a linked list adapts well without reservation for unused memory.
Linked List Structure
Before we implement the stack, let's define the basic structure of a linked list. Each node will hold data and a reference to the next node.
```java
class Node {
int data; // Data of the node
Node next; // Pointer to the next node
Node(int data) {
this.data = data;
this.next = null;
}
}
```
With our node structure established, we can now implement the stack.
Stack Implementation Using a Linked List
Stack Class
We will create a `Stack` class that includes methods to perform key stack operations. The top of the stack will be represented by the first node of the linked list.
```java
class Stack {
private Node top; // Top of the stack
public Stack() {
top = null; // Initialize an empty stack
}
// Push operation
public void push(int data) {
Node newNode = new Node(data); // Create a new node
newNode.next = top; // Link new node with the top
top = newNode; // Update the top to the new node
}
// Pop operation
public int pop() {
if (isEmpty()) {
throw new EmptyStackException(); // Throw exception if the stack is empty
}
int poppedData = top.data; // Fetch the top data
top = top.next; // Move top to the next node
return poppedData; // Return the popped value
}
// Peek operation
public int peek() {
if (isEmpty()) {
throw new EmptyStackException(); // Throw exception if the stack is empty
}
return top.data; // Return the top data
}
// Check if the stack is empty
public boolean isEmpty() {
return top == null; // Return true if the top is null
}
}
```
Explanation of the Stack Operations
Push Operation: This method creates a new node and places it at the top of the stack. By linking the new node's `next` pointer to the current top, we effectively position the new node at the head of the linked list.
Pop Operation: When the stack is empty, this method throws an exception. Otherwise, it stores the data from the top node, moves the `top` reference to the next node, and returns the stored data.
Peek Operation: This method views the top element without removing it, similar to the pop operation but retains the top node.
IsEmpty Operation: This utility checks if the `top` pointer is null to determine if the stack is empty.
Example Usage
Let’s demonstrate the stack implementation with some sample code.
```java
public class Main {
public static void main(String[] args) {
Stack stack = new Stack(); // Create a stack
// Push elements onto the stack
stack.push(10);
stack.push(20);
stack.push(30);
System.out.println("Top element is: " + stack.peek()); // Should print 30
// Pop elements from the stack
System.out.println("Popped element: " + stack.pop()); // Should print 30
System.out.println("Popped element: " + stack.pop()); // Should print 20
// Checking if the stack is empty
System.out.println("Is stack empty? " + stack.isEmpty()); // Should print false
System.out.println("Popped element: " + stack.pop()); // Should print 10
// Now the stack is empty
System.out.println("Is stack empty? " + stack.isEmpty()); // Should print true
}
}
```
Explanation of the Example
In the above example, we create a new `Stack` instance and execute a series of operations. Initially, we push three elements onto the stack and print the top element using the `peek` method. Next, we pop elements one by one, checking the stack's state with the `isEmpty` method after popping all elements.
This hands-on approach clearly illustrates how a stack operates and how to effectively use a linked list for its implementation.
Wrapping Up
Implementing a stack using a linked list in Java not only enhances our understanding of data structures but also provides real-world coding experience. Following the structured approach outlined in this article, programmers can master the essential stack operations and adapt them to fit their specific needs.
Whether your projects involve algorithms, compilers, or simply improving your Java programming skills, understanding how to build a stack with a linked list is an invaluable addition to your toolkit. Embrace this knowledge and explore the diverse applications of stacks in your coding endeavors!
Comments