Stack Implementation in Java using Linked Lists

More in The Data Structures series.

In our previous Stack implementation post, we saw how we can implement a Stack data structure using an ArrayList. But as you can imagine, that’s not the right way to implement a stack. A much better implementation is using a LinkedList. In this post, we’ll see just that. If you’ve missed it, I’ve already written about how to implement Single Linked List (SLL) and Double Linked List (DLL), and I’d encourage you to check those two out first as we’ll be using the same Linked List implementation here, and you can find more detailed Linked List explanation there. Assuming that you have done that, let’s now move on to the Stack.

The Node

The first thing we have to define when we’re dealing with Linked Lists is the node definition. This is important because we’re going to use this Node class as the class to store our actual data, and to also maintain the links in our Linked List (LL). So let’s see how our definition of the Node class looks:

public class Node<T> {

    private T data;
    private Node<T> next;

    public T getData() {
        return data;
    }

    public void setData(T data) {
        this.data = data;
    }

    public Node<T> getNext() {
        return next;
    }

    public void setNext(Node<T> next) {
        this.next = next;
    }
}

Pretty straight forward, and this is actually the same Node class we have in our SLL. Next, let’s see the Stack class, which we’ll be using to interact with the stack.

The Stack

First, we need to declare a private Node object, which will hold the reference to the head of the stack. So let’s start our Stack definition with that:

public class Stack<T> {

    private Node<T> head;

}

Next, we need a method to push values to the stack. In this method, we’ll create a new head if the stack is empty. If not, we’ll add a new node, link it to the current head of the LL, and then make the new node the head of the LL. Here is the method for that:

public void push(T value) {

    if (this.head == null) {

        this.head = new Node<T>();
        this.head.setData(value);
    
	} else {

        Node<T> newNode = new Node<T>();
        newNode.setData(value);
        newNode.setNext(this.head);
        this.head = newNode;

    }
}

And as you can see, we’re still sticking with the generic T class here, so that we can make the stack a lot more flexible at run time. Anyway, next, a method to pop a value from the stack. Because a stack is LIFO, we’ll pop the head from the stack, and make the next node the head. The code snippet for that is here:

public T pop() {

    T value = null;

    if (this.head != null) {
        value = this.head.getData();

        this.head = this.head.getNext();
    }

    return value;
}

There’s a pretty handy function in stacks, you can peek the value of the next element in the stack without actually popping the element from the stack.

public T peek() {

    T value = null;

    if (this.head != null) {
        value = this.head.getData();
    }

    return value;
}

As you can see from the code above, we’re not actually popping the value from the stack, we’re only returning the value of the “data” field in the node. So the node remains unchanged. This is how you can peek into your stack.

Next, once you’re done with the stack, you’d want to clear the stack, or flush it, so that you can start with an empty stack. For this, we’ll implement the following flush method:

public void flush() {
    System.out.println("Flushing stack!");
    this.head = null;
}

Once we lose all references to an object in Java, it becomes qualified to be garbage collected. That is exactly what we’re doing here. As we’re losing references to all the nodes in the stack, they’ll be collected by the Java GC and we’re left with an empty stack.

And just for the fun of it, here’s a method to print the complete stack at any given point in time:

public void printStack() {

    System.out.println("=====================================");
    System.out.println("Printing stack:");

    if (this.head != null) {
        Node<T> currentNode = this.head;

        while (currentNode != null) {
            System.out.print(currentNode.getData() + " -> ");
            currentNode = currentNode.getNext();
        }

        System.out.println("END");

    } else {
        System.out.println("Stack is empty.");
    }

    System.out.println("=====================================");
}

The next part is to test out our implementation.

Testing the Stack

I have used examples here which are similar to the original Stack implementation post I wrote earlier – one string example and one integer example. Let’s look at the string implementation first. For this, I declare a Stack object with type String. I’ll push values to it, peek from it, pop from it, and finally flush it. The code for this is below:

private static void stringStackExample() {

    System.out.println("--------------------------------------------------------------");

    System.out.println("String stack demo");

    Stack<String> stack = new Stack<String>();

    stack.push("First");
    stack.push("Second");
    stack.push("Third");

    String firstValue = stack.peek();
    System.out.println("Value from peek(): " + firstValue);

    String value = stack.pop();
    System.out.println("Popped value: " + value);

    stack.push("Fourth");

    stack.printStack();

    stack.push("Fifth");
    stack.push("Sixth");
    stack.push("Seventh");

    stack.printStack();

    stack.flush();

    stack.printStack();

    System.out.println("--------------------------------------------------------------");
}

As you can see, it’s a pretty simple example. And the output for that is as follows:

--------------------------------------------------------------
String stack demo
Value from peek(): Third
Popped value: Third
=====================================
Printing stack:
Fourth -> Second -> First -> END
=====================================
=====================================
Printing stack:
Seventh -> Sixth -> Fifth -> Fourth -> Second -> First -> END
=====================================
Flushing stack!
=====================================
Printing stack:
Stack is empty.
=====================================
--------------------------------------------------------------

That’s the exact same output that we expected. Next, let’s look at the integer example:

private static void integerStackExample() {

    System.out.println("--------------------------------------------------------------");

    System.out.println("Integer stack demo");

    Stack<Integer> stack = new Stack<>();

    stack.push(1);
    stack.push(2);
    stack.push(3);

    Integer firstValue = stack.peek();
    System.out.println("Value from peek(): " + firstValue);

    Integer value = stack.pop();
    System.out.println("Popped value: " + value);

    stack.push(4);

    stack.printStack();

    stack.push(5);
    stack.push(6);
    stack.push(7);

    stack.printStack();

    stack.flush();

    stack.printStack();

    System.out.println("--------------------------------------------------------------");
}

And the output for this is as follows:

--------------------------------------------------------------
Integer stack demo
Value from peek(): 3
Popped value: 3
=====================================
Printing stack:
4 -> 2 -> 1 -> END
=====================================
=====================================
Printing stack:
7 -> 6 -> 5 -> 4 -> 2 -> 1 -> END
=====================================
Flushing stack!
=====================================
Printing stack:
Stack is empty.
=====================================
--------------------------------------------------------------

As usual, if you’re interested to look at the complete project, you can clone the repo from my Github project.