Due April 8, 1997 before class

Implement linked lists of integers in Java. You should do this by defining a class List with subclasses Empty and Pair.

The class List should have the following methods:

• length which returns the number of elements in the list.
• cons which returns a new properly initialized Pair object.
• getElem and getRest which either raise the exception EmptyE or return the corresponding component of the list.

Here is a small class to test your implementation:

import List.EmptyE; 
import List.List; 
import List.Empty; 
import List.Pair;

class Test {
  public static void main (String args []) {
    List l1 = new Empty();
    List l2 = l1.cons(1);
    List l3 = l2.cons(2).cons(3).cons(4).cons(5);

    int i = l3.length();

    System.out.println("length = " + i);

    try { System.out.println("l3.getRest.getRest.getElem = " + 
                             l3.getRest().getRest().getElem()); }
    catch (EmptyE e) { System.out.println (e); }
    
    try { System.out.println("l2.getRest.getRest.getRest.getElem = " +
                             l2.getRest().getRest().getRest().getElem()); }
    catch (EmptyE e) { System.out.println (e); }
  }
}

To run this test, save the above code in Test.java. Put your classes for the linked list in a directory List and make them part of a package called List. Compile with javac Test.java, and then run the program using java Test. If your implementation is correct, this last step should produce the following output:

length = 5
l3.getRest.getRest.getElem = 3
EmptyE: Asking for tail of empty list