Implementing a Queue with a Linked List - Feature ImageImplementing a Queue with a Linked List - Feature Image
HappyCoders Glasses

Implementing a Queue Using a Linked List

Sven Woltmann
Sven Woltmann
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:

Implementing a queue using a linked list
Implementing a queue using a linked list

How do we reach this state?

Enqueue Algorithm

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

Queue using a linked list: empty queue
Queue using a linked list: empty queue

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:

Queue using a linked list: one element
Queue using a linked list: one element

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:

Queue using a linked list: inserting two elements
Queue using a linked list: inserting two elements

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:

Queue using a linked list: removing an element
Queue using a linked list: removing an element

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.