Queues with Circular Lists

Abstract

Previous labs have considered implementations of queues with arrays and simple linked lists. This lab considers a queue implementation using circular linked lists.

Acknowledgement

Most of this reading is an edited version of Henry M. Walker, Computer Science 2: Principles of Software Engineering, Data Types, and Algorithms, Little, Brown, and Company, 1989, Section 5.6, with programming examples translated from Pascal to C and then Java. This material is used with permission from the copyright holder.

Alternative Implementations of Queues

Previously, the lab on Queues with Arrays described how the queue abstract data type might be implemented with an underlying array structure. Then the lab on Queues with Linked Lists discussed an implementation of queues using linear linked lists. This lab considers a variation of a linked structure involving a circular list.

Circular Lists

In the original pointer implementation of queues in the lab on Queues with Linked Lists, a queue was implemented as a singly linked list. Insertion into the queue took place at the head of the list, whereas deletion took place at the tail of the list. Queue variables, therefore, referenced QueueNode objects, with one field pointing to each end of the list, and we used the following QueueNode declarations:

package queues;

public class QueueNode <E>
{
   /**
    * Each QueueNode has a data field of type E
    * and a next field to support a singly-linked list
    */
   private E data;
   private QueueNode next;

   /**
    * The default construtor sets the data and next fields to null
    */
   public QueueNode ()
   {
      data = null;
      next = null;
   }

   /**
    * An alternative constructor has both data and next parameters
    */
   public QueueNode (E origData, QueueNode origNext)
   {
      data = origData;
      next = origNext;
   }

   // other methods include the usual getters and setters

}

and the Queue class began with these fields:

public class Queue {
   QueueNode head;
   QueueNode tail;
   /* method definitions follows */
}

One alternative approach to this implementation simplifies this structure so that the head element of the list follows the tail element, as shown in the following figure.

In this list, each item points to the next, and this chain of pointers eventually forms a loop back to the first one. With this structure, we need only one pointer to the tail of the queue, and, from this last element, the next field specifies the location of the head of the queue. This requirement of only one pointer allows the declarations to be simplified somewhat, and a queue variable can take the place of this pointer to the last item.

public class Queue {
   QueueNode head;
   QueueNode tail;
   /* method definitions follows */
}

This implementation illustrates another commonly used list structure, called a circular list, in which the last list item points back to the first one.

Such structures have the advantage that once processing starts within the list, there is no possibility of encountering a null pointer; all next fields always specify existing list items. On the other hand, the insertion of a first queue item requires a little care, as does the deletion of an item that is the only one contained in a queue. Thus, while a circular list does allow for a simplified implementation of queues, this circular structure still requires some special cases for queues with no elements or with just one element.

created 17 April 2008 revised 5 April 2010 minor editing 1 February 2020
For more information, please contact Henry M. Walker at walker@cs.grinnell.edu.