Lists exercises

COM 1201 – Spring 2003 – Jeff Raab

Introduction

In this exercise set you will write code that implements linear lists using different techniques. You must follow the course guidelines for type- or handwritten answers, diagrams, and writing code, as posted on the course website.

Programming exercises

Each of the programming exercises requires you to write an implementation of the given IList interface. Before you begin, take a moment to read the HTML documentation for this interface and familiarize yourself with the methods it specifies.

1. Write two IList implementations that make up the recursive list design described in the following class hierarchy:

The IList and Position interfaces are provided with the exercise, and details of their methods can be found in their HTML documentation.

The EmptyRecursiveList class represents an empty IList. Its implementation of the IList methods must produce the results specified in the IList documentation for the case when the list is empty. For some methods this involves throwing an exception, and for some methods this involves producing a nonempty list.

The EmptyRecursiveList class must follow the Singleton design pattern. The Singleton pattern fits a structure for which only one object of its type may ever exist. The only constructor is declared to be private, and a public static final (constant) object of its type is part of its data definition.

Add tests to the ListTests class that thoroughly test each of the methods of this class, in all cases you can identify.

The RecursiveList class represents a single Position in a nonempty IList. Each RecursiveList object must behave as if it is the first Position in its list. Its implementation of the IList methods must consider both the case when it is the last Position in the list, and the case when it is not the last Position in the list. This type of list is recursively defined, in the sense that a RecursiveList object is an IList that contains a reference to another IList object representing the rest of the list.

You must write two constructors for the RecursiveList class. The first must take an Object as input and construct a list containing the given element and an empty rest of its list. The second must take an Object and an IList as input and construct a list whose first element is the given object and whose rest is the given list.

Add tests to the ListTests class that thoroughly test each of the methods of this class, in all cases you can identify.

2. Modify the createList method in the ListFactory class so that it produces the singleton object named EMPTY that represents an empty recursive list. Run the application and click the RunAudioPlayer button to see your class in action.

3. Write an IList implementation that uses doubly linked nodes to store the elements in the list. The design you must use is described in the following class hierarchy:

The IList and Position interfaces are provided with the exercise, and details of their methods can be found in their HTML documentation.

The Node class must represent a Position in a doubly linked list. The LinkedList class must represent an IList made up of doubly linked nodes.

No constructor is required in the Node class, but you may write constructors if you like.

The head and tail nodes in each LinkedList object must be “sentinel” nodes that are not considered to be actual Positions in the list. They are placeholders that only exist to make the code in the various insert and remove methods easier to write and understand.

The LinkedList implementation of the IList methods must consider both the case when it represents an empty list, and the case where it represents a nonempty list. Since a LinkedList object maintains its list by adding and removing Node objects as necessary, the various insert and remove methods must not construct and return a new LinkedList each time they are called. Instead each of those methods must add or remove nodes as needed and then return the LinkedList object on which it was called.

Add tests to the ListTests class that thoroughly test each of the methods of this class, in all cases you can identify.

4. Modify the createList method in the ListFactory class so that it produces a LinkedList object that represents an empty list. Run the application and click the RunAudioPlayer button to see your class in action.

5. Write a class named CircularIList that uses the Proxy design pattern to create a circular IList. A circular list is one where the first Position in the list is considered to be after the last Position in the list, and the last Position is considered to be before the first Position. In a normal – not circular – list it is considered a precondition for the before method that the given Position is not the first in the list, and a precondition for the after method that the given Position is not the last.

Your class must implement IList and proxy the work of its methods to an IList object taken as input to the constructor and stored as a data member. The data member must be hidden. Other than the constructor and the IList methods, you do not have to write any additional methods.

Add tests to the ListTests class that thoroughly test each of the methods of this class, in all cases you can identify.

6. Modify the createCircularList method in the ListFactory class so that it produces a CircularLinkedList object that represents an empty circular list. Run the application and click the RunGamingWheel button to see your class in action.

Written exercises

You should only perform these exercises after the programming exercises are completed.

7. The abstract type for a recursive list object is the interface type named IList. A nonempty recursive list contains a data member of type IList that represents the rest of its list. Write the names of all the classes of objects that can be used as the “rest” of a recursive list. Which of these classes might make a recursive list work incorrectly if used as the “rest” for a RecursiveList object?

8. What changes would have to be made to the hierarchy of classes provided with the exercise, and written by you in exercises 1, 3, and 5, so that the types of IList that work incorrectly can’t be used as the “rest” for a RecursiveList object? Feel free to describe the changes in English, draw a UML diagram that shows the changes, or both.

Submission

You must submit the following written and/or printed material:

• Type- or handwritten answers to written problems

• Printouts of classes and tests you wrote for programming problems

You must submit the following electronic material:

• A folder containing all of the provided files in the exercise

• Classes and tests you wrote for programming problems

Details for electronic submission are given on the course website.