Using Polymorphism to build Lists in Java

Defining the "list" data structure

You know what a list is: grocery lists, phone lists, "to-do" lists, etc. A list contains several pieces of information, like the instance variables of a Java class; but a Java class always has a fixed number of instance variables, decided in advance when you write it, whereas a list can have as many or as few pieces of information as you like.

In figuring out how to implement lists in Java, let's start by listing the operations people perform on lists.

• Create a list
• Add an object to a list
• Remove an object from a list
• Check whether an object appears in a list
• Find out how long a list is (i.e. how many objects are in it)
• Change the order of objects in a list

Now suppose you have a grocery list and, as you walk through the grocery store, you gradually cross off all the things on the list. You still have a list in your hand -- indeed, if you suddenly remembered another thing to buy, you could add it to the list -- it's just empty. This "empty list" will be the foundation of our implementation.

Every list is either empty or non-empty.
This sounds obvious, but it gives us a clue as to how we'll implement lists in Java: using the "variants pattern" (or "template pattern", as the book calls it on page 353). It leads to the class diagram at right: an abstract class StringList, with two concrete subclasses EmptyStringList and NonEmptyStringList. (The Testbed class is a place to put test cases.)

So what can be said about these classes? An EmptyStringList doesn't "have" anything -- that's why we call it "empty" -- but a NonEmptyStringList is guaranteed to have at least one String, which we'll call the "first" String in the list. It may or may not have more Strings; whatever's left after the first String will be referred to as the "rest" of the list. What type is the "rest"? Well, it could be empty (if there was only one string in the list), or it could be non-empty; in other words, it's a list. Adding the usual constructor and "getter" methods, we get the following code:

public abstract class StringList { }

public class EmptyStringList extends StringList { }

public class NonEmptyStringList extends StringList {
   private String first;
   private StringList rest;
   public NonEmptyStringList (String firstArg, StringList restArg) {
      this.first = firstArg;
      this.rest = restArg;
      }
   public getFirst () {
      return this.first;
      }
   public getRest () {
      return this.rest;
      }
   }
}

Defining methods on lists

Now, suppose we want to write a method that works on lists. As a first example, we'll use the "length" method, which tells how many items are in the list. Since the "list" data type is defined by choices (i.e. it's a variant type), a method that operates on it will normally have an abstract definition in the abstract class and concrete definitions in both of the concrete classes:

public abstract class StringList { 
   public abstract int length ();
   }

public class EmptyStringList extends StringList {
   public int length () {
      // insert code here
      }
   }

public class NonEmptyStringList extends StringList {
   ...
   public int length () {
      // insert code here
      }
   }
}

But what should the code be? The EmptyStringList version is easy: the length of an EmptyStringList is always 0 (because it's empty).

public class EmptyStringList extends StringList {
   public int length () {
      return 0;
      }
}

As for the NonEmptyStringList version, since a NonEmptyStringList is defined by parts (i.e. it's a structure with instance variables), the function will probably need to look at the instance variables:

public class NonEmptyStringList extends StringList {
   ...
   public int length () {
      ... this.first ...
      ... this.rest ...
      }
   }
}

In fact, this.first doesn't really matter in finding the length: we don't care what the first (or any) string is, only how many strings are in the list. So we can ignore that one for purposes of this function. What can we do with this.rest? Well, it is a variable of type StringList, so we should call a method that works on StringLists on it. The only such method is length:

public class NonEmptyStringList extends StringList {
   ...
   public int length () {
      ... this.rest.length() ...
      }
   }
}

Recall that this.rest.length() returns an int. Specifically, it returns the length of the rest of the list, i.e. the length of what's left after skipping the first element. The length of the whole list is obviously one more than that, which gives us our answer:

 public class NonEmptyStringList extends StringList {
   ...
   public int length () {
      return this.rest.length() + 1;
      }
   }
}

Test this interactively. Also test it by writing a test method in the StringList class:

public abstract class StringList { 
   public abstract int length ();

   public static void test () {
      StringList plainPizza = new EmptyStringList ();
      StringList cheesePizza = new NonEmptyStringList ("cheese", plainPizza);
      StringList shroomPizza = new NonEmptyStringList ("mushrooms", cheesePizza);
      StringList myPizza = new NonEmptyStringList ("pepperoni", shroomPizza);

      System.out.println ("plainPizza.length() = " + plainPizza.length() +
         " (should be 0)");
      System.out.println ("cheesePizza.length() = " + cheesePizza.length() +
         " (should be 1)");
      System.out.println ("myPizza.length() = " + myPizza.length() +
         " (should be 3)");

      StringList pizzaFromScratch = new NonEmptyStringList ("garlic",
         new NonEmptyStringList("sauce", new NonEmptyStringList("dough",
	 new EmptyStringList())));
      System.out.println ("pizzaFromScratch.length() = " +
         pizzaFromScratch.length() + " (should be 3)");
   }

Try one yourself!