CSC 207 Grinnell College Spring, 2012
Algorithms and Object-Oriented Design

Lab on Queues with Circular Lists


This laboratory provides practice in using a circular list to implement queues. Specifically, class Queue207Implementation will implement the interface, using a QueueNode class to store specific queue items.


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 Java. This material is used with permission from the copyright holder.


In the original pointer implementation of queues in the lab on Queues with Singly-linked Lists, a queue was implemented as a singly linked list, and elements of the list were objects of class QueueNode . Insertion into the queue took place at the head of the list, whereas deletion took place at the tail of the list.

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.

A Circular List Implementation of a Queue

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

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 considerably:

The following notes outline some additional implementation details.

Steps for this Lab

  1. Write class Queue207Implementation2 that provides a circular-list implementation of the Queue207 interface, including a default constructor and methods add, remove, element, and size.

  2. Test your implementation with the test suite that you developed in the lab on queues and testing.

This document is available on the World Wide Web as

created 1 April 2012
last revised 4 April 2012
Valid HTML 4.01! Valid CSS!
For more information, please contact Henry M. Walker at