CSC 207 Grinnell College Fall, 2014
Algorithms and Object-Oriented Design

Lab on Queues with Singly-Linked Lists


This laboratory provides practice in using a singly-linked list to implement queues. Specifically, class Queue207Implementation1 will implement the interface, using a QueueNode class to store specific queue items.


Much 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 7.2, with programming examples translated from Pascal to Java. This material is used with permission from the copyright holder.


One common implementation of a Queue involves a singly-linked list of QueueNodes, for which a QueueNode class has the following basic structure:

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


With this QueueNode structure, a Queue207Implementation1 of the class maintains three private fields numberItems, head, and tail. In this design, numberItems is an integer that specifies the number of items in the queue. Also, head and tail are pointers, as shown in the following diagram:

A List/Pointer Implementation of a Queue

In this structure, head and tail mark the two ends of the queue, inserting items at the tail and deleting them from the head. Here, we view the queue as ordering items from the head to the tail; the head is the first item we will remove, and the tail is the last item. Also, the data field of a QueueNode contains the string for one item on the queue, and the next field is a reference to the next QueueNode on the list.

The following notes outline some additional implementation details.

Steps for this Lab

  1. Write class Queue207Implementation1 that provides a singly-linked-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 29 March 2012
last revised 4 April 2012
Valid HTML 4.01! Valid CSS!
For more information, please contact Henry M. Walker at