52233 Algorithms and Data Structures

Algorithms and Data Structures

Quick Links
What's New Home Contacts Course Book Java Book JDK & JDSL Slides Notes Demos Exercises Marks

Generic Lists

Abstract: Making the List generic, dealing with objects, not just integers. A small example with a ToDo list.

The initial definition of the List class only allowed us to have lists of integers. What we would really like is to have a list of any type, class, object, what you will. We want to do ths while preserving the functionality of our integer list. That is, we want methods for delete, insert, etc for any class.

The Polymorphic List Class, and its methods (java code for the generic List class)
Our first definition of the List Class, and its methods is defined textually below. A List is defined as a triple:

       boolean eol;
       Object data;
       List   next;

This is very similar to the definition used before except that instead of data being an integer (int) it is now an Object.
The constructors
The constructors are the same as before, except that we have e as an Object.

List(): Construct an empty list.
List(e): Construct a list of a single element with Object e as the data and an empty list as the next of the list
List(e,l): Construct a list of a single element with Object e as the data and l as the next of the list

But also note that we have introduced a class variable (see the code) (i.e. that is private static int num_cons = 0;) that counts the number of calls made to a constructor method. Whenever a constructor method is called it increments this class variable. But its a class variable so we cannot get at it via an instance of the class. So we have a method cons() that returns num_cons for the class. public int cons() { return List.num_cons; }

The accessors
Again, we have the 3 accessor functions, but now head delivers an Object.

L.head(): delivers the value of the data within the 1^st element of L, and it is an Object.
L.isEmpty(): delivers the value of the eol attribute of the first element of L.
L.tail(): delivers the value of the next attribute, the list that follows the first element of L.

To print a list (using the toString method)
In java every object should have a toString() method. This is then used by System.out.println. That is, System.out.println(X) applies the toString method to the object X, delivering a string. The System.out.println method is then applied to that string. So, to print a List we should really just have a method that takes a List and delivers a string representation for printing. So, if we have a list L we can print it just like any other object by calling System.out.println(L).

We will use the convention that the printed image of a list starts with a "(" and ends with a ")". The method toString below just delivers an open round bracket "(", calls a method to deliver the rest of the list as a string (RestOfString), and then delivers a closing round bracket ")". Note that the operator + is over loaded by java so that it works between strings, concatenating strings ("Pat"+"rick").

 public String toString()
  {
    return "(" + RestOfString() + ")";
  }

To deliver the list as a string we use method RestOFString below. Note that it is private so cannot be accessed outside of the class definition, but it may be used by the methods within the class definition (and toString in particular).

 private String RestOfString()
  {
    if (isEmpty())
      return "";
    else return head().toString() + " " + tail().RestOfString();
  }

Method RestOfString is very similar to the print method, viewed as a pattern, but is a bit more interesting. It's similar because it deals with the situation of the list being empty (isEmpty) and delivers the null string "", and if the list is not empty, doing something with the head of the list (head()) and then making a recursive call with the tail of the list (tail().RestOfString()).

What is interesting is the application of the toString method to the head of the list. Isn't that a recursive call to the method we are defining? And does that not suggest that the method will not terminate? In fact, since head() now delivers an Object, and we expect all objects to have a toString method, java should work out just what to do here. So, it generally is not a recursive call to the toString method defined here. But ... it might be! It would be if the head() is a List! So, we can print a list of lists, as well as a list of any objects (so long as they have a toString method)!

The isEmpty, length, append, delete, and reverse methods
These methods are unchanged.

The add method
The add method only has one minor change: it now takes as argument an Object e (rather than an int e).

The insert method
Previously, the insert method delivered as a result a new list with the integer e inserted into the List L, retaining the increasing order of the list. But how do we insert an arbitrary object into a list in order? What happens if that element is an animal (a dog, cat, or elephant) into a list of animals, or a task into a list of tasks, or books into a list of books? If we want our List class to be generic we must be able to do this.

We do this by using interfaces. The idea is as follows. To insert an object into a list we want the user to define the concept of order between objects. So, we will have a class of object called a comparator (for wont of a name). The comparator class is essentialy empty, having no attributes, but has a method for comparing two objects. The insert method is then passed:

an object to insert into the list, and
a comparator object, which has a method for comparing objects of the required class.

The insert method is defined below.

1.  public List insert(Object e, Comparator c)           
2.  {
3.    if (isEmpty())                                   
4.      return new List(e);
5.    else if (c.compare(e,head()) < 0)                 
6.      return new List(e,this);
7.    else return new List(head(),tail().insert(e,c));
8.  }

I'll define the method, numbered line by numbered line, below:

Defining the parameters, note that we pass in, along with the object e to be inserted, a Comparator object c. The Comparator object has a method called compare. Convention has it that a comparison between objects delivers an integer result. So, compare(X,Y) delivers -1 if X < Y, delivers 0 if X == Y, and delivers +1 if X > Y (see line 5).
Yet another squiggly bracket.
As before, if the list isEmpty() then ...
... deliver a new list that has e as its head and the empty list as its tail.
Remember, c is an object of class Comparator and has a compare method. So, to get the compare method from the object c we have c.compare, and this then wants as arguments two objects, in this case e (the object we are inserting) and the head() of the list.
So, e is less than head(). Deliver a new list that has e as the head and this (the current object) as the tail of the list.
the list aint empty and e is not less than head(), so we need to deliver a new list that has head() as the first element, and a tail that is the insertion of e into the tail of the list. This is yet another example of a recursive call (in fact a tail recursive call). Note that in the recursive call we have to respect the inser method's parameters, passing it the object to insert (e) and the comparator object (e).
Yet another squiggly bracket (can't get enough of them, can you?)

Now that wasn't easy, but I've explained it as best I can. Later, I will show just how we then go about defining an instance of the Comparator so that we can use.

Source Code

Acknowledgements
Ewan MacIntyre (aka Ewen MacIntypo) and Andrew Forrest helped me make the list generic, and then helped me apply it to ToDo and Integer. And they never shouted at me (at least, not to my face.)