Last Updated:

Stack using linked list in Java

Earlier, we already wrote our stack using a one-dimensional array. However, in this article, we'll write a stack implementation using a linked list and write a few unit tests for it.

Own java stack implementation

The theory can be found in our previous stack implementation.

"Why reinvent the wheel?"

you may ask, because everything has already been written before us and you just need to be able to use. I absolutely agree with this position, but for a deeper understanding of how the stack works and how it works, you should often write your own implementation. In this stack implementation, we'll use a linked list.

Best Practices for Writing a Stack

To begin with, I would like to highlight the basic rules and approaches that I will follow when writing a stack in Java. Naturally, this applies not only to the implementation in Java, because approaches to the implementation of the data structure should be universal. However, some points will be in the context of the Java implementation.

Push, pop operations for a constant time

The time complexity for insert () and receive () operations must be O(1). It doesn't matter how many items we have in the stack, these operations should be done in a constant amount of time. For example, if we call a pop operation, it should return the last item added, O(1).pushpop

Avoid printing to the console

Methods that are responsible for displaying list items must also be testable. And testing a method that just prints something to the console isn't quite right. Instead, in a Java implementation, you can override the method and work with it.toString()

Universal Stack

Instead of being tied to a specific type of data, we can make our stack generic using generics. And use .T

Invention of the wheel

When we write our implementation of some established data structure, algorithms or patterns, it is desirable to inherit the existing approach (whether it is a way of naming methods, handling errors, etc.). To do this in Java, a good example is the java.util.LinkedList class we know.

Writing a stack using a linked list in Java

The following implementation uses the parameterized LinkedListStack class, which uses an internal linked list to work with data:

From the implementation it is clear that we have only 3 classes:

  • LinkedList<T> - Implementation of a linked list
  • Node<T> is an internal class that represents a list item
  • LinkedListStack<T> is a class that implements the basic operations of the stack. Internally, it uses LinkedList<T> to manipulate data.

Now let's write some unit tests to test the operations in our stack implementation. We use the standard JUnit:

All our tests pass, the implementation of the stack in Java is successful.