public class List
{
    private Object data;        // the value stored within list
    private List next;          // the remaining values of the list
    // an object to represent the empty list
    public final static List EMPTY = new List();

    private List()
    // post: construct nil list.  Called once only.
    {
        this.data = null;
        this.next = this;
    }

    public List(Object head, List rest)
    // pre: construct a "cons" head, followed by rest.
    {
        this.data = head;
        this.next = rest;
    }

    public List(Object head)
    // pre: head is non-null
    // post: construct a list with one element, d.
    {
        this(head,List.EMPTY);
    }

    public Object head()
    // post: return the first element of list
    {
        if (isEmpty()) return null;
        else return data;
    }

    public List rest()
    // post: return part of list following head
    {
        // note that EMPTY has EMPTY as rest
        return next;
    }
    
    public boolean isEmpty()
    // post: return true if this list is empty
    {
        return this == List.EMPTY;
    }

    public Object tail()
    // post: return the last value in list
    {
        if (isEmpty()) return null;
        else if (rest().isEmpty()) return head();
        else return rest().tail();
    }

/*
    public int length()
    // post: return the number of elements logically in this list
    {
        int result = 0;         // length, ultimately
        List l = this;          // l points to a sublist
        while (!l.isEmpty())
        {
            l = l.rest();       // skip over head, counting it
            result++;
        }
        return result;
    }
*/
    public int length()
    // post: return the number of elements logically in this list
    {
        if (isEmpty())
        {
            return 0; // empty list has no elements
        } else {
            // list has head plus elements of rest
            return 1 + rest().length(); 
        }
    }

    public int count(Object item)
    // post: compute # of elements that equals item in this list
    {
        if (isEmpty())
        {
            return 0; // empty list has no elements
        } else if (head().equals(item)) {
            // list has head (that matches) plus other possibles in rest
            return 1 + rest().count(item); 
        } else return rest().count(item);
    }

    public boolean contains(Object x)
    // pre: x is non-null
    // post: returns true if list contains x-value as an element
    {
        if (isEmpty()) return false;
        else if (head().equals(x)) return true;
        else return rest().contains(x);
    }

    /*
    public boolean contains(Object x)
    // pre: x is non-null
    // post: returns true if list contains x-value as an element
    {
        List item = this;
        while (!item.isEmpty())
        {
            if (item.head().equals(x)) return true;
            item = item.rest();
        }
        return false;
    }
    */

    public Object elementAt(int index)
    // pre: index is < length of the list
    // post: returns the index'th element of the list, where head is zero
    {
        if (isEmpty()) return null;
        if (index == 0) return head();
        else return rest().elementAt(index-1);
    }

    public List removeElementAt(int index)
    // pre: index is < length of the list
    // post: removes the index'th element of the list, where head is zero
    {
        if (isEmpty()) return this;
        if (index == 0) return rest();
        else return new List(head(),rest().removeElementAt(index-1));
    }

    public String printList()
    // post: print a string representation of the elements of this list
    {
        if (isEmpty())
        {
            return "";
        } else if (rest().isEmpty()) {
            return head().toString();
        } else {
            return head()+" "+rest().printList();
        }
    }

    public String toString()
    // post: print a string representation of this list
    {
        if (isEmpty())
        {
            return "";
        } else {
            return head()+" "+rest();
        }
    }

    public List append(Object item)
    // pre: list is non-null
    // post: nondestructively appends item onto end of list
    {
        if (isEmpty()) return new List(item);
        return new List(head(),rest().append(item));
    }

    public List reverse()
    // post: nondestructive reversal of List
    {
        if (isEmpty()) return this;
        return rest().reverse().append(head());
    }

    public boolean equals(Object other)
    // pre: other is another List
    // post: returns true if other is list with structure similar to this
    {
        List that = (List)other;
        
        if (isEmpty() || that.isEmpty()) return this == that;
        if (!head().equals(that.head())) return false;
        return rest().equals(that.rest());
    }

    public List remove(Object l)
    // pre: l is non-null
    // post: returns list with copies of l removed
    {
        if (isEmpty()) return List.EMPTY;
        if (head().equals(l)) return rest().remove(l);
        else return new List(head(),rest().remove(l));
    }

    public int index(Object x)
    // pre: x is non-null
    // post: returns index of entry containing list element, or -1
    {
        if (isEmpty()) return -1;
        else if (head().equals(x)) return 0;
        int position = rest().index(x);
        if (position == -1) return position;
        else return position + 1;
    }

    public static void main(String[] args)
    {
        List l = List.EMPTY;
        int i;

        for (i = 0; i < args.length; i++)
        {
            l = l.append(args[i]);
        }
        System.out.println("List ("+l+") is "+l.length()+" long.");
        System.out.println("List.head() is "+l.length()+" long.");
        System.out.println("\"Duane\" is a member of list? "+l.contains("Duane"));
        System.out.println("\"Duane\"'s position in list? "+l.index("Duane"));
        System.out.println(l.reverse()+" (reversed)");
        System.out.println(l+" (normal)");

        System.out.println(l.remove("Duane")+" (\"Duane\" removed)");
        System.out.println(l+" (normal)");
    }
}
/*

((now is the Duane time) jim)
List is 2 long.
List.head() is 5 long.
"Duane" is a member of list? true
(jim (time Duane the is now)) (tree-reversed)
((now is the Duane time) jim) (normal)
((now the Duane time) jim) ("is" removed)
((now is the Duane time) jim) (normal)

*/