The LISP language, created in 1960, implements linked lists in a very elegant way. You will explore a Java analog in this set of exercises. The key observation is that the tail of an abstract list—that is, the list with its head node removed—is also a list. The tail of that list is again a list, and so on, until you reach the empty list. Here is a Java interface for such as list:

public interface LispList
{
   boolean isEmpty();
   Object head();
   LispList tail();
   . . .
}

There are two kinds of lists, empty lists and nonempty lists:

public class EmptyList extends LispList { ... }
public class NonEmptyList extends LispList { ... }

These classes are quite trivial. The EmptyList class has no instance variables. Its head and tail methods simply throw an UnsupportedOperationException, and its isEmpty method returns true. The NonEmptyList class has instance variables for the head and tail.

Here is one way of making a lisp list with three elements:

LispList list = new NonEmptyList("A", new NonEmptyList("B",
new NonEmptyList("C", new EmptyList())));

This is a bit tedious, and it is a good idea to supply a convenience method cons that calls the constructor, as well as a static variable NIL that is an instance of an empty list. Then our list construction becomes

LispList list = NIL.cons("C").cons("B").cons("A");

Note that you need to build up the list starting from the (empty) tail.

To see the elegance of this approach, consider the implementation of a toString method that produces a string containing all list elements. The method must be implemented by both subclasses:

public class EmptyList
{
   ...
   public String toString() { return ""; }
}

public class NonEmptyList
{
   ...
   public String toString() { return head() + " " + tail().toString(); }
}

Note that no if statement is required. A list is either empty or nonempty, and the correct toString method is invoked due to polymorphism.

In this exercise, complete the LispList interface and the EmptyList and NonEmptyList classes. Write a test program that constructs a list and prints it.

Complete the following files:

EmptyList.java

public class EmptyList implements LispList { ... public String toString() { return ""; } }

LispList.java

public interface LispList { boolean isEmpty(); Object head(); LispList tail(); ... }

NonEmptyList.java

public class NonEmptyList implements LispList { ... public String toString() { return head() + " " + tail().toString(); } }

Use the following file:

LispListTester.java

public class LispListTester
{
   public static void main(String[] args)
   {
      LispList list1 = new EmptyList();
      System.out.println("[" + list1 + "]");
      System.out.println("Expected: []");

      LispList list2 = new NonEmptyList("A", new EmptyList());
      System.out.println(list2);
      System.out.println("Expected: A");

      LispList list3 = new NonEmptyList("A", new NonEmptyList("B",
         new NonEmptyList("C", new EmptyList())));
      System.out.println(list3);
      System.out.println("Expected: A B C");

      LispList list4 = LispList.NIL.cons("E").cons("D").cons("C").cons("B").cons("A");
      System.out.println(list4);
      System.out.println("Expected: A B C D E");
   }
}