In this report we are going to discuss a rather sophisticated design of a linked list class in Java. It will be built in such a way as to use a minimum of ad-hoc polymorphism. Doing this well will require that we utilize a number of simple design patterns. We will use the visitor pattern to permit a client to use the list with great flexibility. We will also use the Null Object pattern to avoid using null to terminate the list. This will require building two kinds of nodes for the list; non-empty nodes and the single nil node. These come from different classes since they behave differently and we want to use dynamic polymoprphism to distinguish this behavior. Because we build two classes, we will write quite a lot of code, but we also will have a very clean design that is very flexible.
Lisp is a language that is built around lists. It is a functional language that works without loops or variables. To do "real" work requires writing recursive functions and the lists of lisp are designed to be processed recursively. A list class in Java like the lists of lisp is a very nice way to give students lots of practice writing recursive functions and in general "thinking recursively." A lisp like list has the following abstract "interface." No, it isn't a Java interface, but we have used a similar form for presentation of its elements.
INTERFACE Lisp
{ static final List nil;
static final List cons(Object o, List l);
Object head();
List tail();
}
In Lisp, there is a constant list called nil that is empty and holds no elements. Other lists are not nil and do contain elements. We build lists from other lists (including nil) by using the cons operation (short for construct) that takes an element and a list and gives us a new list that has the element as its "head" and the other argument (a list) as its "tail". This has the effect of extending the list by one element. A non empty list can be asked for its head and it will return the element at the head. It can also be asked for its tail and will then return a "new" list that consists of everything but its head, though the original list is unaffected by this operation. In fact, lists are immutable. You can create new lists from old, but you can't change existing lists.
Here is an example of building up a list using cons.
List trial = List.nil; trial = List.cons(new Integer(2), trial); trial = List.cons(new Integer(1), trial);
The list trial now has two elements, a 1 is now at the head, and the tail is a list with only one element (a 2). Note that cons is a static function of the List class. We can put any Objects into a List. Note that after the second statement we had two lists (nil and trial). The third statement didn't modify the trial list but gave us a new list that we also referred to with the variable trial. This means that the original value then had no (apparent) reference to it (though we could have given it one before we executed the third statement). A list having no reference will be garbage collected so cease to exist.
Note that sometimes a list will have a reference that is not immediately apparent. That is actually the case here, but you need to know about the implementation to see that. Logically, however, nothing requires this implemenation so the original list input to cons might be garbage collected.
We can also extract information from a list using the head and tail functions. These are methods of the List class and are not static.
while(trial != List.nil)
{ System.out.println(trial.head());
trial = trial.tail();
}
This will write out the elements of the list in order of the list, but it also destroys the list, since we use the same variable (trial) to refer to the tail that we just previously used to refer to the list as a whole. If before we started this loop we had copied the reference trial into another variable (say temp) then the original list would have been preserved, since the garbage collector only collects an Object when it has no references.
Lisp and these lists were created precisely for recursive programming. We show an example of how a list can be manipulated directly but recursively using the head and tail functions. Here is a recursive function on lists that also prints out the list backwards. This is because it recurses before it prints. Switch the last two lines to get it to print in the forward direction.
public static void show(List list)
{ if(list == List.nil)return;
show(list.tail());
System.out.println(list.head());
}
The function to extract the last element of a list can also be written recursively.
public static Object last(List l)
{ if(l == List.nil) throw new List.EmptyException("Failed in 'last'.");
if(l.tail() == List.nil) return l.head();
return last(l.tail());
}
Now we will do something a bit more exciting. One of the most important simple Lisp functions is called map or mapcar. Its purpose is to return a new list from an existing one after applying some function to each element of the original list. The new list contains the results of applying the function.
Java can't pass a function as an argument to another
function. It can only pass an object. However, we can simulate passing a function
by passing an object and then calling some method of that object. We will find
it useful to define an interface named fun. An object of a class that implements
fun will act like a function when it is passed.
interface fun // Function object
{ Object doIt(Object o);
}
Now we can write mapcar in terms of fun. Note, in early versions of lisp, the head of a list was called its car because lisp was implemented on a machine that divided up a memory location (register) into two parts, its address part and its data part. CAR was the Contents of the Address part of the Register, where the head was kept. Likewise the tail of a list was called its CDR (pronounced could-er) for Contents of the Data part of the Register in which a pointer to it was held. So mapcar meant map (apply) a function over the car of a list and of all its sublists. In recent versions of lisp (Scheme, for example) head and tail are usually preferred to car and cdr and mapcar has become just map.
public static List mapcar(List l, fun f)
{ if(l == List.nil) return l;
return List.cons(f.doIt(l.head()), mapcar(l.tail(), f));
}
Notice that mapcar is recursive on the tail of the list, and applies the function by calling doit on the head of the list. The results of these two operations are combined with cons.
Also note that we distinguish between empty lists and non empty lists in this function. This is a form of ad-hoc polymorphism that object-orientation tries to avoid. We will see later that it can be avoided. However, here we are programming in the lisp style or paradigm, which is functional, and such ad-hoc polymorphism is very natural there.
We can double a list (double all the elements in it) by defining a doubler implementing fun and mapping it over a list like trial.
static class doubler implements fun
{ public Object doIt(Object o)
{ return new Integer(2 * ((Integer) o).intValue());
}
}
...
List doubled = mapcar(trial, new doubler());
Immutablility of these lists gives the implementer great flexibility. While the tail of a list is conceptually different from the list as a whole, if the list can't be modified then the two lists can actually share storage. If either was mutable and the implementation is shared, then changing one of the lists might also change the other as well. Immutability prevents this. Therefore, in our implementation we will indeed have many lists sharing the same parts.
You need to interpret "immutable" correctly, however. If we put an object into a list then as long as that list exists that object will be in it in the same location. We can create other lists based on this list and those lists might not contain the object but this list always will until we are done with the list and it is garbage collected. However, the object itself may not be immutable and if we get access to it, via head or otherwise, then we can send mutator messages to the object causing it to change its state. Thus the list doesn't change and the objects it contains don't change their "containment" but they might change their states.
Since this is Java we will be using and since a List is a container (contains other objects) we should also give our Lists an Enumeration interface so that they can be used just like other Java containers. This is an "interface" something like:
INTERFACE Container
{ Enumeration elements();
}
This just means that we can ask a List for its elements and will get a java.util.enumeration that we can use to access the list elements one after the other.
Supposing that we have a List called trial, the following will write out all of its elements from beginning (the head) to the end.
java.util.Enumeration e = trial.elements();
while(e.hasMoreElements())
{ System.out.println(e.nextElement());
}
This isn't nearly as flexible as the recursive programming we did above, however. It would be difficult to use it to produce something like mapcar, for example. We could certainly print out values which were double those in the list, but creating the list of doubled values would be harder.
We note that the above is only a Java 1 Enumeration.
Java 2 Iterators are left as a non-trivial exercise.
There is one more way in which we can manipulate lists. This will let us process them without using ad-hoc polymorphism to distinguish between nil and non-nil lists. In effect it will let us write separately what we want to happen at an empty node and what we want to happen at a non-empty node.
A List.Visitor has the following form. This is a proper Java interface.
public interface Visitor // visit one node of the list
{ public Object apply(List.Node aList, Object o);
public Object apply(List.NIL empty, Object o);
}
A Visitor defines two operations, one for Node (non-empty node) and one for NIL (empty node, nil). The visitor functions also take an arbitrary object that the apply function may use however it likes and it may return an Object as well, though the client may ignore it as usual. A simple example uses null for inputs and also for outputs. To use a Visitor, a List must "accept" it, using the next abstract "interface."
INTERFACE Visitable
{ Object accept(List.Visitor v, Object o);
}
The Object in the accept message is passed to the apply methods. The accept message will be sent to either an empty node (nil) or a non empty node. That node will execute only one of the apply methods of the Visitor--namely the appropriate one with the first parameter that matches its own type. The Object returned by apply will be returned as the result of accept. Here we show a Visitor that will print the list backwards from its tail towards its head. This is because the apply method sends the accept message to its tail prior to printing its own head. The nil node also prints a representation of itself here, namely the word "nothing". We don't need the extra Object argument here so we just pass in null and we ignore the result.
class Printer implements List.Visitor
{ public Object apply(List.Node n, Object o)
{ n.tail().accept(this, o);
System.out.println(n.head());
return null;
}
public Object apply(List.NIL n, Object o)
{ System.out.println("nothing");
return null;
}
}
...
trial.accept(new Printer(), null);
The statement above will print something like the following if we execute it immediately after creating list trial above.
nothing 2 1
We can write a Visitor to produce the last element in a list also, but doing so requires a bit of ad-hoc polymorphism. Avoiding it would be difficult, since the test required is performed on a different element than the one executing the code. This is again recursive on the tail, but this time the call to accept follows the other operations.
static class laster implements List.Visitor
{ public Object apply(List.Node n, Object o)
{ if(n.tail() == List.nil) return n.head();
return n.tail().accept(this, o);
}
public Object apply(List.NIL n, Object o)
{ throw new List.EmptyException("Failed in 'last'.");
}
}
We can do something like mapcar with Visitors also. Again we recurse first to obtain the results on the tail. Actually, we don't need to use a temporary variable at all here. We could just expand the right hand side of the assignment as the second argument of cons. The effect would be the same. Notice that there is nothing to do with the NIL version of apply.
static class mapper implements List.Visitor
{ public Object apply(List.Node n, Object o)
{ List l = (List)n.tail().accept(this, o);
return List.cons(((fun) o).doIt(n.head()), l);
}
public Object apply(List.NIL n, Object o)
{ return n;
}
}
...
List doubled = trial.accept(new mapper(), new doubler())
Note that apply functions on Nodes are usually recursive. Thus, the visitor can control the recursion, rather than the list itself doing so. Therefore you can recurse either before or after handling the current node. This is a different kind of recursion than you may be used to, however. Note that apply doesn't recurse by calling apply, but by having another node again accept the same visitor. When the node accepts the visitor it again call an apply method, however. That is why it is recursive.
Our overall structure will be quite complex. List itself is an abstract class, so we can't instantiate it. We will define two inner classes within List; Node and NIL. Node is the type of the non-empty list and NIL is the type of the single empty node. We will implement NIL so that it follows the Singleton pattern. It is also an example of the Null Object pattern since it is an object that fulfills the same basic role as null, it terminates linked structures. The classes Node and NIL are inner to List, but they also extend List.
Furthermore, we will need Enumeration classes for both Node and NIL. These will implement the java.util.Enumeration interface and will be built as inner to the respective classes whose elements they enumerate. So, our overall structure looks like this:
public abstract class List implements Cloneable, java.io.Serializable
{ ...
interface Visitor
{ ...
}
public static class NIL extends List implements java.io.Serializable
{ ...
private static class Enum implements java.util.Enumeration
{ ...
}
}
public static class Node extends List implements java.io.Serializable
{ ...
private static class Enum implements java.util.Enumeration
{ ...
}
}
}
Additionally, the constant nil and the static function cons are defined in List itself. The head and tail functions will be abstract in List and only implemented in Node and in NIL.
We will want a new Exception class to indicate that we have tried to extract the head or tail from nil. This class is also inner to List, but we didn't show it above.
public static class EmptyException extends java.util.NoSuchElementException
{ public EmptyException(String s){super(s);}
}
The NIL class has no instance variables. However, the Node class has a field for the element stored in the head of the list and another to refer to the tail of the list of which it is the head. We make objects of these two classes behave differently so as to avoid ad-hoc polymorphism. In our implementation, some of the behavior of the NIL class will actually be defined in the List abstract parent class. This makes the NIL behavior the default behavior. The only justification for this is that an abstract List is certainly empty, and the behavior defined here is appropriate for an empty list. It will be overridden in the Node class as appropriate. Here is the abstract List class.
public abstract class List implements Cloneable, java.io.Serializable
{ public static List cons(Object h, List t)
{ if(t==null) t = NIL.val;
Node n = new Node(h,t);
return n;
}
public static List withElements(Object[] elements) //Create list from array
{ List result = nil;
for(int i = elements.length-1; i >= 0; --i)
{ result = cons(elements[i], result);
}
return result;
}
public static final NIL nil = NIL.val;
public static List nil(){return nil;}
public abstract Object head(); // Return the head of the list or throw exception
public abstract List tail();// Return the tail of the list or throw exception
public interface Visitor // visit one node of the list
{ public Object apply(Node aList, Object o);
public Object apply(NIL empty, Object o);
}
public abstract Object accept(Visitor action, Object o);
public abstract Enumeration elements();
// The following functions provide default behavior. This is NIL behavior.
public void copyInto(Object[] A){} // Copy this into A.
public int size(){return 0;}
public Object clone(){ return this;}
public boolean contains(Object o){return false;}
public boolean isEmpty() // Is this empty?
{ return true;
}
... inner classes defined.
}
Note that the only ad-hoc polymorphism here is a guard that the user doesn't try to cons something onto null. If it is attempted, the cons operator will use nil instead. NIL.val is a constant defined in the NIL class. It is exported from this class as List.nil. The withElements static function provides an easy way to create a list from an array. The list elements will be in the same order as the array elements. We create the list with cons, which requires that we process the array in reverse.
Integer [] somevals = {new Integer(3), new Integer(4)};
List test = List.withElements(somevals);
Given the definition of List, NIL is quite easy.
public static class NIL extends List implements Serializable
// This is a Singleton Null Object (2 patterns)
{ public String toString()
{ return "NIL" ;
}
public Object head()
{ throw new EmptyException("Head");
}
public List tail()
{ throw new EmptyException("Tail");
}
public Object accept(Visitor action, Object o)
{ return action.apply(this, o);
}
public boolean equals(Object other){return other instanceof NIL;}
public int hashCode(){return 337;}
private NIL(){}
public Enumeration elements(){return Enum.e;}
public static final NIL val = new NIL();
... inner Enum class defined.
}
Asking for the head or tail of nil throws an exception.
We have made NIL into a singleton by making its constructor private and providing a single value of this type. Since it is also Serializable, we have guarded against writing nil and then reading it into a copy, by defining its equals (and hashCode) method to consider any such copy to be equal to the original. NIL inherits size and other methods from List, which provided the correct implementation for this class.
We will look at the inner Enum class after we examine the Node class.
A note about Singletons in Java. When build a Singleton class like NIL you are likely to think that there will ever be only one such object. We showed above how this may not be the case if the class also implements Serializable. However there is another way that things might not happen the way you suspect. Java uses a dynamic loader (and unloader). Suppose you build a class named Trial and it is a singleton. There is a reference to a Trial object from within the Trial class, of course. Suppose your program reaches a point at which this is the only reference to a Trial object. Then Java is free to unload the Trial class to make room in memory. If it does so, your Trial object will disappear. This isn't necessarily a problem, but if you later need to reference a Trial object (the singleton) the class will be reloaded and the object created anew. You should either guard against this (by making sure that you never lose a reference to the singleton from outside Trial) or be prepared for it, by having all values of Trial be considered "equals" to each other and being sure to compare with the equals method rather than the == operator, which you should be doing in any case. We have done a little of each here. There is a reference to the singleton nil from within List. Thus nil won't be collected and NIL unloaded unless List can also be unloaded and this would only happen if there were no List objects in our program. We have also made all objects in class NIL equal to each other and guaranteed that all will hash to the same bucket.
This class has a field called element to hold the head of this list and a field called next to refer to the tail.
public static class Node extends List implements Serializable { public Object head(){return element;} public List tail(){return next;} public Object accept(Visitor action, Object o) { return action.apply(this, o); } public int size(){return 1 + next.size();} public Object clone() // returns a list like this one. { return new Node (element, (List)next.clone()); }
As a side note, the implementation of clone shown here is not needed. Immutablility of the lists says that returning this would be good enough. Note that the list is cloned here, but not its elements.
public boolean contains(Object o) // Does this contain o? { if (o == null) { if(element == null) return true; return next.contains(null); } if(o.equals (element)) return true; return next.contains(o); } public void copyInto(Object[] A) // Copy into a preexisting array. { int i = 0; for(Enumeration e = elements(); e.hasMoreElements();) { A[i++] = e.nextElement(); } } public Enumeration elements(){return new Enum(this);} public boolean isEmpty(){ return false;} public String toString() { return element.toString() + " " + next.toString(); } private Node(Object o, List first) { next = first; element = o; } private List next = NIL.val; private Object element = null; ... inner Enum class defined. }
Note that we do use if in the contains method. This is because null must be treated separately and since null doesn't represent an object we can't use dynamic polymorphism for this.
Each of the concrete classes has an inner class with the same name Enum that implements java.util.Enumeration.
The NIL enumeration always returns false for hasMoreElements. This class also defines a singleton. It is standard to return a NoSuchElementException when you ask for a non existant element of a container. We do so here also.
private static class Enum implements java.util.Enumeration
{ public boolean hasMoreElements(){return false;}
public Object nextElement()
{ throw new NoSuchElementException("Fail in List.");
}
private Enum(){}
private static final Enum e = new Enum();
}
This works by maintaining a reference to a List (which may be a Node or nil).
private static class Enum implements java.util.Enumeration
{ private List here;
protected Enum(List n){here = n;}
public boolean hasMoreElements(){return ! here.isEmpty();}
public Object nextElement()
{ if(here == NIL.val) throw new NoSuchElementException("Fail in List.");
Object result = ((Node)here).element;
here = ((Node)here).next;
return result;
/* Alternatively we could say the following and avoid the test for nil:
try
{ Object result = ((Node)here).element;
here = ((Node)here).next;
return result;
}
catch(ClassCastException e)
{ throw new NoSuchElementException("Fail in List.");
}
*/
}
}
We really only need the test in nextElement since we want to control which exception is thrown if the user ignores the result of hasMoreElements and calls nextElement anyway. Without the test or the try block we would throw a ClassCastException instead of the desired NoSuchElementException.
The code shown here is available in the downloads directory. It includes the List.java file and a test file, Main.java.
Most of the patterns used here are discussed in Design Patterns by Gamma, Helm, Johnson, and Vlissides (Addison-Wesley, 1995). This is the now famous "Gang of Four" or GOF book. Null Object is by Bobby Wolfe and can be found in Pattern Languages of Program Design 3, edited by Martin, Riehle, and Buschmann (Addison-Wesley, 1998)
While object oriented programmers try to avoid ad-hoc polymorphism it isn't always possible. The hard-to-impossible cases are when dealing with primitive (non-object) data in hybrid languages like Java, parsing input, and when creating new objects. Here, however, we have solved the creational problem with a simple factory containing singletons. The creational problem can be solved in general through the use of reflection, such as the Java Reflection API. The other situations are less tractable.
The Visitor patterns implements an idea called Double Dispatch. When a List accepts a visitor what happens depends on two types. It depends on the type of the visitor and the type of the node visited. Normally the behavior of an operation only depends on the type of the receiver of a message. Here it is more general. Some complex programs take advantage of this idea and use something like a Visitor even when you don't have a container, though the name implies "visiting" each of the elements of a container. This idea is also sometimes called "call backs" since the argument passed in to accept (the Visitor) is immediately passed a message (called back).
For more on ad-hoc polymorphism, see Bergin's Selection
Patterns.
For more on dynamic polymorphism, see Bergin's Polymorphism
Patterns.
For more on how the object oriented programmer thinks, see Bergin's Object
Patterns.
My friend Owen Astrachan of Duke University points out that the Visitor interface to List is overkill. I generally agree, except that providing it has a very small footprint in the code. Also, if List is part of a larger container library in which other containers are Visitable, then consistency would indicate that List should also. On the other hand, the Enumerations took quite a bit of work and are far less useful. The right way to manipulate these lists is to use the recursive interface: cons, head, and tail. Owen is the author of A Computer Science Tapestry which, in its second edition, has a class in C++ that is similar to this one. Thanks also to Duane Buck of Otterbein College and Eugene Wallingford of the University of Northern Iowa for pointing out a few flaws and keeping me on my toes.
Last Updated: April 30, 2000