Comp 212 Spring 2001, Homework 1: Lists

Due Monday 5 Feb. 2001 10:00 AM.

This homework serves as a transition from functional programming to object-oriented programming. It also serves as a warm up for the larger programming projects that will come later. It is based on the Scheme list example discussed in class (PS, PDF) and in lab.


You are given the following object model for a Scheme-like list structure:

list.png (9749 bytes)

Your task is to add the following public methods and implement the classes in Java:

  1. Modify the toString method to return a string containing AList's elements surrounded with matching parentheses and separated with spaces, as in Scheme, e.g., (1 3 a bcd). The empty list should print as ().

  2. Add the method AList makeClone() to class AList to build and return a new list that is a copy of the receiver object.

  3. Add the method Object nthElement(int n) to class AList to return the nth element of the receiver. Here, 0 <= n < the list length, and the case n equals 0 corresponds to the first element of the list.

  4. Add the method Object lastElement() to class AList to return the last element of the receiver.

  5. Add the method AList firstElements(int num_elts) to class AList to compute and return an AList that contains the first num_elts elements of the receiver. Here, 0 <= num_elts <= the list length. E.g., when num_elts = 0, you should return the empty list.

  6. Add the method AList reverse() to class AList to build and return a new list like the receiver object, but with its elements in reverse order.

  7. Add the method AList append(AList list2) to class AList to return the appending of the receiver list with the argument. For a pseudo-code example, (a b c).append(1 2) returns (a b c 1 2).

Remember that the methods' implementations belong in the supporting classes, not the abstract class AList. Aside from the constructors, none of the methods should modify any object's fields. I.e., all methods should be written in a purely functional style. You may add any private or protected methods to your classes to support these public operations. Your code should follow the factory pattern described in lab 02, including its use of a package named list.

In these new methods, computing the length of the list is unnecessary and inefficient, so you should not do that.

Testing: You must provide a ListClient class with a main method. It should create and use list objects, printing all interesting test cases of all these methods. It is your responsibility for understanding what the interesting cases are.

Code and documentation style

As with all programs in this course, you are expected to use good coding style, including reasonable variable names, a header before each non-overridden function, and reasonable indentation. It should be documented in Javadoc style. The provided code in lab 02 can serve as examples of acceptable coding style and documentation.

In general, it is bad style to check for the type of an object at run-time, e.g., by using instanceof or adding a method to check for the type. For this assignment, there is no need to make such a check.


The homework is due Monday 5 Feb., 2001 10:00 AM. It should contain the following files and be submitted electronically. Place all the following in a directory called


Submit the assignment using the following UNIX command from your comp212 directory:

     turnin -c comp212 -p hw-list hw-list
(This says to turn in to the class COMP 212 and the project we call hw-list, all the documents in your directory hw-list.) Verify that your submission was successful by checking that the file ~comp212/submit/hw-list/your-user-id.tar.Z exists and is not of zero length.

You may resubmit using the same command. We will only see the last submission.