This assignment is due on March 17th.

Some minor modifications have been made. Unfortunately, the second edition of the book dropped the chapter that was referenced by the ``recommended reading'' paragraph. I will give some help in the next class on this. In addition, I have added the hint that at least one of the list operations must be implemented as constructor or as static method in an object-oriented programming language.

A note about assertions in Java has been added.

Please register yourself first. Otherwise you do not know the email address you have to send your submission to.

Lisp and Scheme provide a built-in list data structure. Lisp even derives its name from it: List processing. Similar list structures are also supported by Prolog and Perl.

A list can be empty. Notation: ( ). This is implemented by having a null reference.

A list can consist of just one element only. Notation: (x). This is implemented by one node with two references. The first points to the next element which is null, the second reference points to x:

A list can have multipe elements. Example: (x, y, z)

Lists can be nested. Example: ((x, y), z)

Following common operations are defined for lists:

cons	constructs a new list node where the first parameter is a reference to its element and the second references the next list node.
append	constructs a new list that appends two lists.
car	returns the first element of a list.
cdr	returns the list behind the first element

Note that at least one of these operations need to be implemented as constructor or as static method in an object-oriented language. Which one(s)?

Design and implement a Java class that implements such an abstraction for lists including the four operations from which some are in fact constructors. In addition, a toString method should be provided that allows to print a list in the notation above. A small test program should be supplied as well.

Note that your Java classes are expected to follow our Java Coding Standard.

Hints:

• You have an externally visible class named List and a private class named Node. Note that nodes can be freely shared by different lists as cons and append create new lists but do not modify existing nodes.

• Note that references can be null, point to another list node, or to some arbitrary Java object. The Object class is helpful here.

• Allow an empty list to be created.

• A test method whether a list is empty or not might be useful.

Please feel free to use assertions in Java that are supported beginning with JDK 1.4. Just put /usr/local/j2sdk1.4.0/bin in the front of your PATH and pass the option -source 1.4 to javac.

You are invited to send me your Java class stub by email to get my comments on it.

Alternatively, it is permitted to solve this assignment in C++ but it is more difficult as

• no garbage collection eases the cleanup of shared nodes, and
• there is no general base type like Object in Java.

Reference counters can be used to decide whether a node is no longer referenced. The whole class must be designed as a template class with a base type as argument. As dubious casts are better avoided, it helps to have three pointers in each node. One referencing the next list node, and from the other two (a pointer to a node and a pointer to the given base type) one at maximum can be non-null. An output operator should be supplied instead of a toString method.

Submissions in C++ are expected to follow our C++ Coding Standard.

You are free to send me your include file with the class declaration by email to get my comments before this assignment is due.