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

Lab on Queues with Singly-Linked Lists

Summary

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

Acknowledgement

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.

Introduction

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 Queue207.java 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

http://www.walker.cs.grinnell.edu/courses/207.sp012/labs/lab-queues-singly-linked.shtml

created 29 March 2012
last revised 4 April 2012
Valid HTML 4.01! Valid CSS!
For more information, please contact Henry M. Walker at walker@cs.grinnell.edu.