How to Implement a Stack Using Linked List in Java

Stacks are a fundamental data structure in computer science, used extensively in programming for various applications, such as managing function calls, parsing expressions, and backtracking algorithms. In this article, we'll explore how to implement a stack using a linked list in Java. This approach offers dynamic memory allocation, allowing the stack to grow and shrink as needed.

Understanding Stacks and Linked Lists

What is a Stack?

A stack is a linear data structure that follows the Last In First Out (LIFO) principle. This means that the last element added to the stack will be the first one to be removed. The primary operations of a stack include:

• Push: Add an item to the top of the stack.
• Pop: Remove and return the item from the top of the stack.
• Peek: View the item at the top of the stack without removing it.
• isEmpty: Check if the stack is empty.

What is a Linked List?

A linked list is a linear data structure where elements, called nodes, are connected through pointers. Each node contains two parts:

1. Data: The actual value.
2. Next: A reference (or pointer) to the next node in the sequence.

Using a linked list to implement a stack allows for efficient memory usage because it can dynamically allocate memory as needed.

Why Use a Linked List for Stack Implementation?

Using a linked list for stack implementation offers several advantages:

• Dynamic Size: Unlike arrays, linked lists can grow and shrink in size, which means you don't need to define a maximum size for your stack.
• Efficient Memory Usage: Memory is allocated only when necessary, reducing waste.
• No Resizing: There's no need for resizing as with arrays, which can be time-consuming.

Implementing a Stack Using Linked List in Java

Let's dive into the step-by-step process of implementing a stack using a linked list in Java.

Step 1: Create the Node Class

First, we'll define a Node class, which represents each element in our linked list.

class Node {
    int data;     // Stores the data
    Node next;    // Pointer to the next node

    Node(int data) {
        this.data = data;
        this.next = null; // Initialize next as null
    }
}

Step 2: Create the Stack Class

Next, we will create a Stack class that will use the Node class to manage stack operations.

class Stack {
    private Node top; // This will point to the top of the stack

    public Stack() {
        this.top = null; // Initialize stack as empty
    }

    // Push operation
    public void push(int data) {
        Node newNode = new Node(data); // Create a new node
        newNode.next = top; // Link new node to previous top
        top = newNode; // Update top to new node
        System.out.println(data + " pushed to stack.");
    }

    // Pop operation
    public int pop() {
        if (isEmpty()) {
            System.out.println("Stack is empty. Cannot pop.");
            return -1; // Or throw an exception
        }
        int poppedData = top.data; // Get data from top
        top = top.next; // Update top to next node
        return poppedData; // Return popped data
    }

    // Peek operation
    public int peek() {
        if (isEmpty()) {
            System.out.println("Stack is empty. Cannot peek.");
            return -1; // Or throw an exception
        }
        return top.data; // Return data from top
    }

    // Check if stack is empty
    public boolean isEmpty() {
        return top == null; // True if top is null
    }
}

Step 3: Testing the Stack Implementation

Now that we have our stack implemented, let's create a main method to test it.

public class Main {
    public static void main(String[] args) {
        Stack stack = new Stack();

        stack.push(10);
        stack.push(20);
        stack.push(30);

        System.out.println(stack.peek() + " is on the top of the stack.");

        System.out.println(stack.pop() + " popped from stack.");
        System.out.println(stack.pop() + " popped from stack.");
        System.out.println(stack.pop() + " popped from stack.");

        // Test popping from an empty stack
        stack.pop();
    }
}

Output

When you run the above code, you should see output similar to:

10 pushed to stack.
20 pushed to stack.
30 pushed to stack.
30 is on the top of the stack.
30 popped from stack.
20 popped from stack.
10 popped from stack.
Stack is empty. Cannot pop.

Troubleshooting Common Issues

When implementing a stack using a linked list, you might encounter a few common issues:

• Null Pointer Exceptions: Make sure to check if the stack is empty before performing pop or peek operations.
• Memory Leaks: In Java, garbage collection should handle this, but always ensure that you are not holding references to nodes that are no longer needed.

Conclusion

Implementing a stack using a linked list in Java is an excellent way to understand both data structures and their interplay. This approach not only demonstrates the flexibility of linked lists but also equips you with practical skills for handling dynamic data storage in your applications. Whether you're building a simple application or diving into more complex algorithms, mastering stack implementations will enhance your programming toolkit significantly. Happy coding!