Implementing a Queue Using a Linked List

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> head;
  private Node<E> tail;

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

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

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

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

  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.

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.