How to implement a LispList?

[fultonwilcox]

Hi everyone,
I've been working on Java problems over the summer, and I haven't found anything especially hard, but here's a problem I'm not sure how to start implementing.

The LISP language implements linked lists in a very elegant way. There is a Java version of this. The tail of an abstract list(list with head removed) is also a list. It goes on and on, until an empty list is reached. An interface of this would be:

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

There are two kinds of lists:

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

EmptyList has no instance variables. Head and tail methods simply throw unsupported operation exception and isEmpty returns true. NonEmptyList has instance variables for head and tail.
One way of implementing one would be:

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

It would be a good idea to make a function cons(Object obj) that builds up from the tail:

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

So far, I have this:

public interface LispList {

	boolean isEmpty();
	Object head();
	LispList tail();
	String toString();
	class Node
	{
		public Object data;
		public Node next;
	}
}

public class EmptyList implements LispList{

	public EmptyList()
	{
	}
	
	public boolean isEmpty()
	{
		return true;
	}
	
	public Object head()
	{
		return null;
	}
	
	public LispList tail()
	{
		return null;
	}
	
	public String toString()
	{
		return "";
	}
}

public class NonEmptyList implements LispList {

	private Node head;
	private Node tail;
	
	public NonEmptyList(Object o)
	{
		head = new Node();
		head.data = o;
		head.next = tail;

	}
	
	public boolean isEmpty() {
		return false;
	}


	public Object head() {
		return head.data;
	}

	public void cons(Object o)
	{
		Node newNode = new Node();
		newNode.data = o;
		newNode.next = null;
		tail = newNode;
	}
	
	public LispList tail() {
		removeHead();
		return this;
	}
	
	private void removeHead()
	{
		head = head.next;
	}
	
	public String toString()
	{
		return head() + " " + tail().toString();
	}
}

Question is:
How do I get cons to work? Also, I don't understand how .NIL should work too.
Also, I have to add in a function that returns the length, a a function that merges two lisplists together ( 1 2 3 4 + 5 6 = 1 5 2 6 3 4 ), and if it contains a certain element.
I would be extremely grateful for some help.