# Implementing a Queue Using a Linked List

Sven Woltmann
Last update: May 16, 2022

In the last part of this tutorial series, I showed you how to implement a queue with stacks. In this part, we will implement a queue using a linked list.

## The Algorithm – Step by Step

Our queue consists of two references to list nodes: `head` and `tail`.

The `head` reference points to a list node containing the queue's head element and a `next` pointer to a second list node. The second node, in turn, contains the second element and a pointer to the third list node, and so on.

The last node is referenced by both the `next` pointer of the second-to-last element and the `tail` pointer. It contains the last queue element, and its `next` reference points to `null`.

The following image shows an example queue in which the elements "banana", "cherry", and "grape" (in this order) have been inserted:

How do we reach this state?

### Enqueue Algorithm

We start with an empty queue. Both `head` and `tail` references are `null`:

We insert the first element into the queue by wrapping it in a list node and having both `head` and `tail` point to that node:

We insert more elements as follows:

1. We wrap the element to be inserted in a new list node.
2. We let the `next` pointer of the last node, i.e., `tail.next`, point to the new node.
3. We also let `tail` point at the new node.

In the following image, you can see how to insert a second element, "cherry", into the example queue:

### Dequeue Algorithm

Retrieving the head element with `dequeue()` then works as follows:

1. We remember the element of the node referenced by `head` (in the example, that would be "banana").
2. We let `head` point to `head.next` (in the example to the node that wraps "cherry"). If `head` is `null` afterward (i.e., the queue is empty), we also set `tail` to `null`.
3. We return the element remembered in step 1 (in the example, "banana").
4. In a programming language with a garbage collector (such as Java), the GC will delete the node that is no longer referenced; in other languages (such as C++), we would have to delete it manually.

The following image illustrates the four steps:

The dashed border around the "banana" node in steps 2 and 3 represents that this node is no longer referenced at this time.

## Source Code for the Queue with a Linked List

The following code shows the implementation of a queue with a linked list (LinkedListQueue in the GitHub repo). The class for the nodes, `Node`, can be found at the very end as a static inner class.

``````public class LinkedListQueue<E> implements Queue<E> {

private Node<E> tail;

@Override
public void enqueue(E element) {
Node<E> newNode = new Node<>(element);
if (isEmpty()) {
} else {
tail.next = newNode;
tail = newNode;
}
}

@Override
public E dequeue() {
if (isEmpty()) {
throw new NoSuchElementException();
}
tail = null;
}
return element;
}

@Override
public E peek() {
if (isEmpty()) {
throw new NoSuchElementException();
}
}

@Override
public boolean isEmpty() {
}

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

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

You can see how to use the `LinkedListQueue` class in the QueueDemo program.

## Outlook

In the next part of the tutorial, I will show you how to implement a queue using an array.