# Implement a Stack Using a Linked List

Sven Woltmann
Last update: May 17, 2022

In the previous part, we implemented a stack with an array. In this part, I will show you how to program a stack using a singly linked list.

## The Algorithm – Step by Step

The algorithm is quite simple: A `top` reference points to a node that contains the top element of the stack and a `next` pointer to the second node. This node, in turn, contains the second element and a pointer to the third node, and so on. The last node contains the bottom element of the stack; the `next` reference of the last node is `null`.

The following image shows an example stack on which the elements "apple", "orange", and "pear" (in that order) have been pushed:

But how do we get there?

### Enqueue Algorithm

Let's start with an empty stack. The `top` reference is initially `null`:

To push the first element onto the stack, we wrap it in a new node and let `top` point to that node:

We insert each additional element between top and the first node. For this, we need three steps:

1. We create a new node and wrap it around the element to be inserted.
2. We let the `next` reference of the new node point to the same node as `top`.
3. We let `top` point to the new node.

The following image shows the three insertion steps:

### Dequeue Algorithm

To retrieve an element with `pop()`, we proceed as follows:

1. We memorize the element of the node to which `top` points ("orange" in the example).
2. We change the `top` reference to the node referenced by `top.next`.
3. We return the element memorized in step 1.
4. In a language with a garbage collector (e.g., Java), the GC care of deleting the node that is no longer referenced. In languages without a garbage collector (e.g., C++), we have to do it ourselves.

The following image shows the four steps:

The dashed frame around the "orange" node in the second and third step is to indicate that this list node is no longer referenced.

## Source Code for the Stack with a Linked List

The following source code shows the implementation of the stack using a linked list (LinkedListStack class in the GitHub repo). You can find the class for the nodes, `Node`, at the end of the source code as a static inner class.

``````public class LinkedListStack<E> implements Stack<E> {

private Node<E> top = null;

@Override
public void push(E element) {
top = new Node<>(element, top);
}

@Override
public E pop() {
if (isEmpty()) {
throw new NoSuchElementException();
}
E element = top.element;
top = top.next;
return element;
}

@Override
public E peek() {
if (isEmpty()) {
throw new NoSuchElementException();
}
return top.element;
}

@Override
public boolean isEmpty() {
return top == null;
}

private static class Node<E> {
final E element;
final Node<E> next;

Node(E element, Node<E> next) {
this.element = element;
this.next = next;
}
}
}```Code language: Java (java)```

You can see an example of how the `LinkedListStack` class is used in the StackDemo demo program.

## Advantages and Disadvantages of Implementing the Stack Using a Linked List

Implementing a stack with a linked list has the following advantages over the array variant: it does not waste memory with unoccupied array fields, and it does not require resizing the array by copying the entire array.

The node objects, in turn, occupy more memory than a single field in an array. Creating node objects takes more time than setting an array field. A linked list also causes more work for the garbage collector since it must follow the complete list on each pass.

As a rule, the advantages of the array implementation outweigh the disadvantages, so you'll find the array implementation more often.

## Outlook

In the next part of the tutorial, I'll show you how to implement a stack with a queue.

If you still have questions, please ask them via the comment function. Do you want to be informed about new tutorials and articles? Then click here to sign up for the HappyCoders.eu newsletter.