How to Implement a Stack Using a LinkedList in Java?

Introduction

The Stack is a fundamental data structure in computer science. It is used to store elements in a Last-In-First-Out (LIFO) order, meaning that the most recently added element is the first one to be removed. In this article, we will explore how to implement a stack in Java using a LinkedList.

While Java provides a built-in Stack class, implementing a stack from scratch using a LinkedList offers greater flexibility and understanding of how the stack operations work. A linked list-based stack can grow dynamically as we add new elements, unlike an array-based implementation where the size is fixed.

Understanding the Stack Data Structure

A stack supports the following core operations:

• Push: Adds an element to the top of the stack.
• Pop: Removes the element from the top of the stack and returns it.
• Peek: Returns the element from the top of the stack without removing it.
• isEmpty: Checks if the stack is empty.

These operations form the foundation of the stack behavior, and we can implement them using a LinkedList where each node represents an element of the stack.

Implementing a Stack Using a LinkedList

The LinkedList is a linear data structure where each element (node) points to the next one. In the context of a stack, we will treat the head of the linked list as the top of the stack. The push operation will add a node at the head, while the pop and peek operations will interact with the head node.

Step 1: Create the Node Class

First, we need to create a class to represent the node in the linked list. Each node will contain the data and a reference to the next node.

class Node {
    int data;
    Node next;
    
    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}
        

Here, the Node class has two members:

• data: Stores the value of the element.
• next: Points to the next node in the linked list.

Step 2: Implement the Stack Class

Now, we can implement the Stack class that will use the Node class. The Stack class will include methods for the basic stack operations.

class Stack {
    private Node top;
    
    public Stack() {
        this.top = null;
    }

    // Push operation
    public void push(int data) {
        Node newNode = new Node(data);
        newNode.next = top;
        top = newNode;
        System.out.println("Pushed: " + data);
    }

    // Pop operation
    public int pop() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        int poppedData = top.data;
        top = top.next;
        return poppedData;
    }

    // Peek operation
    public int peek() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return top.data;
    }

    // isEmpty check
    public boolean isEmpty() {
        return top == null;
    }
}
        

Explanation of Methods:

• push(int data): This method creates a new node with the given data, links it to the current top of the stack, and makes this new node the top.
• pop(): This method removes the top node and returns its data. If the stack is empty, it throws an EmptyStackException.
• peek(): This method returns the data of the top node without removing it. Again, it throws an exception if the stack is empty.
• isEmpty(): This method checks if the stack is empty by verifying if the top node is null.

Step 3: Testing the Stack

Now that we have implemented the stack using a linked list, let’s test it by performing some stack operations.

public class StackTest {
    public static void main(String[] args) {
        Stack stack = new Stack();
        
        // Testing push operation
        stack.push(10);
        stack.push(20);
        stack.push(30);

        // Testing peek operation
        System.out.println("Peek: " + stack.peek()); // Should print 30

        // Testing pop operation
        System.out.println("Popped: " + stack.pop()); // Should print 30
        System.out.println("Popped: " + stack.pop()); // Should print 20
        System.out.println("Popped: " + stack.pop()); // Should print 10

        // Testing empty stack condition
        try {
            stack.pop(); // Should throw EmptyStackException
        } catch (EmptyStackException e) {
            System.out.println("Error: " + e);
        }
    }
}
        

When you run the above code, you should see the following output:

Pushed: 10
Pushed: 20
Pushed: 30
Peek: 30
Popped: 30
Popped: 20
Popped: 10
Error: java.util.EmptyStackException
        

This confirms that the stack operations are working correctly.

Advantages of Using LinkedList for Stack Implementation

Using a LinkedList to implement a stack has several advantages:

• Dynamic Memory Allocation: Linked lists do not have a fixed size, unlike arrays. As a result, the stack can grow dynamically without worrying about the capacity limits.
• Efficient Operations: The time complexity of all stack operations (push, pop, peek) is O(1), as we only interact with the head node of the linked list.
• No Wasted Space: Linked lists do not require contiguous memory, so there’s no wasted space compared to an array-based stack that might allocate unused space.

Conclusion

In this article, we’ve implemented a stack using a LinkedList in Java. We covered the fundamental stack operations, such as push, pop, and peek, and explained the code step by step.

By using a linked list, we can take advantage of dynamic memory allocation and efficient operations. Understanding this implementation helps solidify your grasp of both stacks and linked lists as essential data structures in computer science.