/**
 * Represents the abstract notion of a list.
 * At this point, it has no behavior, i.e. no method.
 * We shall add behaviors later.
 */
public interface IList {
}

/**
 * Represents the immutable empty list, which is a list.
 * At this point, the empty list has no behavior.
 * Note that in contrast with the non-empty list, since it has
 * no first and no rest, there is no getFirst() nor getRest() method.
 */
public interface IEmptyList extends IList {
}

/**
 * Represents the immutable non-empty list, which is a list.
 * A non-empty list has a data object called first, and an
 * isomorphic subcomponent called rest.  Its structural behavior
 * provides access to its internal data (first) and substructure (rest).
 */
public interface INEList extends IList {
    /**
     * "Gettor" method for the list's first.
     * @return this INElist's first element.
     */
    public abstract Object getFirst();

    /**
     * "Gettor" method for the list's rest.
     * @return this INElist's rest.
     */
    public abstract IList getRest();
}

The above is only an abstract specification of the (immutable) list structure.  Note that the Scheme formulation is written as comments, whereas the Java formulation is written as actual Java code.  The Java code specifies in effect a "contract" of what the list structure "looks like" and what it "behaves" like (i.e. what it is capable of doing).  

In order to create concrete IList objects and work with them, we need to define concrete classes to implement the above interfaces.  Below is an example of concrete list implementations.

/**
 * Concrete implementation of the empty list interface, IEmptyList.
 * Since the empty list has no fields, there is no need to explicitly
 * define any constructor for EmptyList.
 * However, the compiler will generate the following constructor:
 * public EmptyList() {};
 * Note that there is no code inside the curly braces.
 * The above constructor has no parameter.  A constructor without any
 * parameter is called a "default" constructor.
 * To instantiate a concrete empty list, we simply call: new EmptyList();
 */
public class EmptyList implements IEmptyList {
}

/**
 * Concrete implementation of the non-empty list interface, INEList.
 * Contains two pieces of data:
 *   first: an Object representing the first data element
 *   rest: an IList object representing the rest of this non-emptylist.
 * When a class contains other objects that are isomorphic to itself,
 * this class is called a composite.
 * Provides concrete code for 
 * a constructor to initialize this NEList to a given first and rest,
 * the getFirst() method for accessing the first data element,
 * getRest() method for accesssing the rest of the list.
 */
public class NEList implements INEList {

    /**
     * The first data element of this NEList.
     */
    private Object _first;
    /**
     * The rest or "tail" of this NEList.
     * Data Invariant: _rest != null;
     */
    private IList _rest;

    /**
     * Initializes this NEList to a given first and rest.
     * @param first the first data element of this NEList.
     * @param tail != null, the rest of this NEList.
     */
    public NEList(Object first, IList tail) {
        _first = first;
        _rest = tail;
    }

    /**
     * Returns the first data element of this NEList.
     */
    public Object getFirst() {
        return _first;
    }

    /**
     * Returns the rest of this NEList.
     */
    public IList getRest() {
        return _rest;
    }
}

/**
 * A non object-oriented way of coding list operations.
 * Scheme functions are translated into public static methods.
 * The instanceof operator is used to check for the type of a
 * given list.
*/
public class ListOps {
    /**
     * Computes the length of a list.
     * @param L one of the two types of IList.
     */
    public static int GetLength(IList L) {
        if (L instanceof IEmptyList) {
            return 0;
        }
        else {
            return 1 + GetLength(((INEList)L).getRest());
            // Note how type-casting is used here!
            // Why do we need to type-cast?
        }
    }
}