Homework #3, Circular Doubly-Linked List and Iterator

Due: Monday, June 9, 2003

Last modified: "June 7, 2003 22:24:04 by evett"

Modify Weiss's implementation of the LinkedList class (a doubly-linked list class, actually) so that is also a circular list. Do this by creating a new class, CircularLinkedList that is a modification of Weiss's class. Your class will also have to provide an inner class, CircularLinkedListIterator (which is, in turn, a modification of Weiss's LinkedListIterator inner class) that implements ListIterator.

The main difference between a circularly linked list and a regular linked list is that as long as there is at least one element in the list, hasNext and hasPrevious will always return true.

Provide these additional methods in your class:

String toString() Return a string representation of the list. You should assume the constituent objects in the list provide their own toString methods.
bool fromString(String list) The given argument, list, should have been created by a previous call to toString. The existing contents of the list are lost, and should be replaced by the list that is encoded in the argument. Return true upon success, and false otherwise.

fromString and toString should work like a matched pair. You may make no assumptions about the string representation of each element of the list (i.e., you have no idea what characters might appear in each constituent's string representation.) You should use run-length encoding to provide this flexibility.

The only thing you may assume about the constituent class is that it implements the Storeable interface. Thus, you may invoke fromString(String st) on an instance of that class. Again, you may assume that fromString and toString work like a matched pair in this constituent class. So,

  ExampleConstituent ec = new ExampleConstituent("test1");
  ExampleConstituent ec2 = new ExampleConstituent("secondTest");
  String strRep = ec.toString();
  ec2.fromString(strRep);  // Reconstitute ec in ec2
  if (ec2.equals(ec))
  	System.out.println("The original and the copy are equals.");

...should print, "The original and the copy are equals."

To test your class, I'll use something very like this driver. Make sure your code compiles and runs with this driver! Hopefully your output looks like this, but at least make sure your code compiles and runs!

What to Hand in:

Submit your code, a single file named CircularLinkedList.java, containing the implementation of your class. This file should not be in any package. I will use the given driver to test your code. You do not need to provide an implementation of Storeable or ExampleConstituent, as I will use my own. (Actually, I will use a modified driver, where I use a class named something other than ExampleConstituent in its place, but this other class will have an implementation identical to ExampleConstituent.)

Hints:

The assignment is a bit tricky because you don't know the data type of the constituents of the list. You may assume the list is homogenous (i.e., all the constituents are of the same type), and that that class implements the Storeable interface. To see why this is tricky, consider an outline of fromString(String list):

  foreach substring, s, of list:
    Type t = new Type();
	t.fromString(s)
	listBeingConstructed.add(t);

The problem is "Type", above. How can you know what the data type (the class) of the constituent is? You know that s is the result of invoking toPrint on the constituent, but that is all. You need some way to determine the type of the constituent dynamically. Luckily, there is a way to do this in Java, using the Reflection libary. Given the name of a class as a string, W, the static method Class.forName(W), returns a Class object, c, that represents the class with that name. With this object you can obtain a constructor (zeroConstructor) for that class. With the constructor, you can create an instance of that class (instanceOfClass). Here is an example, again, assuming W is a String, consisting of the name of the constituent class:

  Class c = Class.forName(W);
  Class[] argTypesOfConstructor = new Class[0];  // We want a zero-argument constructor
  Constructor zeroConstructor = c.getConstructor(argTypesOfConstructor);
  Object[] argsToConstructor = new Object[0]; //  The zero arguments for the constructor
  Object instanceOfClass = zeroConstructor.newInstance(argsToConstructor);

At this point, instanceOfClass should be an instance of the class whose name is W. Here is a code example showing this stuff at work. In the example, I create an instance of the "Date" class using nothing more than the string "Date" (well, actually, "java.util.Date"--the fully qualified name of the class--so W == "java.util.Date".) In the example code, try to ignore all the "catch" statements--there are a lot of them there, but then tend to occlude the simplicity of the process, which is outlined above, without all the exception handling code. You probably want to use the makeInstanceOfType method in your assignment.

[If you're not impressed, you should be! This is way cool stuff. You cannot do anything like this in C++. Very frabjous, indeed!]

So, where are you going to get the name of the constituent class? (You should not assume this class will be called, ExampleConstituent, because it won't be!) You will have to record it, somehow, in the string created by CircularLinkedList.toString, and then retrieve it in CircularLinkedList.fromString.