In the last part of this tutorial series, I showed youhow 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 andtail.

Thehead reference points to a list node containing the queue's head element and anext 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 thenext pointer of the second-to-last element and thetail pointer. It contains the last queue element, and itsnext reference points tonull.

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. Bothhead andtail references arenull:

We insert the first element into the queue by wrapping it in a list node and having bothhead andtail 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 thenext pointer of the last node, i.e.,tail.next, point to the new node.
3. We also lettail 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 withdequeue() then works as follows:

1. We remember the element of the node referenced byhead (in the example, that would be "banana").
2. We lethead point tohead.next (in the example to the node that wraps "cherry"). Ifhead isnull afterward (i.e., the queue is empty), we also settail tonull.
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.

publicclassLinkedListQueue<E>implementsQueue<E>{private Node<E> head;private Node<E> tail;@Overridepublicvoidenqueue(E element){    Node<E> newNode =new Node<>(element);if (isEmpty()) {      head = tail = newNode;    }else {      tail.next = newNode;      tail = newNode;    }  }@Overridepublic Edequeue(){if (isEmpty()) {thrownew NoSuchElementException();    }    E element = head.element;    head = head.next;if (head ==null) {      tail =null;    }return element;  }@Overridepublic Epeek(){if (isEmpty()) {thrownew NoSuchElementException();    }return head.element;  }@OverridepublicbooleanisEmpty(){return head ==null;  }privatestaticclassNode<E>{final E element;    Node<E> next;    Node(E element) {this.element = element;    }  }}Code language:Java(java)

You can see how to use theLinkedListQueue class in theQueueDemo program.

Outlook

In the next part of the tutorial, I will show youhow 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? Thenclick here to sign up for the HappyCoders.eu newsletter.