CompSci-61B Lab 3
Iterable Lists

In this assignment, we complete development of a CompSci-61B version of the "ArrayListWithIterator" class that appears in Carrano chapter 8. The final step in the development of these classes is to add support for "iteration". Using for-loops and the "size" and "getEntry" accessors, it is already possible to traverse these data structures. Iteration is a more general way to do the same, and does not depend upon having an indexed "getEntry" accessor, so it is a more versatile way to traverse a data structure.

The array-based implementation is exactly the same as the one developed in the previous lab, except that iteration is added. So this provides an opportunity to apply "inheritance" -- the new "compsci61b.MyArrayList" extends the old "compsci61b.testing.MyArrayList".

We also take this opportunity to improve the linked-list implementation, by replacing the simple singly-linked list with a doubly-linked list implementation. Since this change is so extensive, inheritance is not used -- instead, the old version "compsci61b.testing.MyLinkedList" is copy/pasted and modified to make "compsci61b.MyLinkedList".

The classes "MyArrayList" and "MyLinkedList" are similar to Java's own "ArrayList" and "LinkedList" classes. They implement a new version of the "MyList" interface to be stored in the package "compsci61b". They also implement the two interfaces created in the previous lab: "MyArrayBasedDataStructure" and "MyLinkedDataStructure", both already stored in the package "compsci61b".

This assignment is worth 40 points, and consists of 3 exercises. Zero points will be awarded for programs with misspelled filenames, or incorrect case. Zero points will be awarded for programs that do not compile or run on the department's UNIX server. Partial points will be awarded for programs that are run but do not conform to all specifications, at the discretion of the grader. Be sure to complete both exercises and post the lab3.jar before midnight of the due date, because there is a 5-point-per-day lateness penalty for late work. Check the course outline for due dates for lab assignments.

This interface should inherit from "compsci61b.testing.MyList", and from Java's "Iterable". Only one accessor specification needs to be added: public Iterator<T> iterator(), to satisfy the "Iterable" interface requirements. All others are inherited from "compsci61b.testing.MyList", and do not have to be repeated.

Compile and jar, and validate the interface as you did with "MyIntList" in lab 2a's exercise 1. Use the same test.java, with "compsci61b.MyList" instead of "MyIntList", to validate the public interface. (Since there are two "MyList" classes, and you import everything in the packages that contain both, it is necessary to be specific about which one you are using by prepending the package name.)

Since this uses inheritance, most of the work is already done. There are no data members to add -- just the private class "MyIterator", and the accessor "public Iterator<T> iterator()".

To test the class operation, include a main inside the class. In main, create a "MyList" object using "MyArrayList", and exercise all of its methods. It can be similar to the one you wrote for lab 2a's exercise 3. But to test the iteration feature, use something like this, for an Integer data structure reference named a:

for (Integer value: a)
  System.out.println(value);

For public interface validation, use the same test.java as in lab 2a's exercise 2, but import compsci61b instead of compsci61b.testing, and use these statements to create and validate the data structure object:

MyList<Integer> a = new MyArrayList<Integer>();
...
System.out.println("Should be true: " + (a instanceof compsci61b.MyList));
System.out.println("Should be true: " + (a instanceof compsci61b.MyArrayBasedDataStructure));
System.out.println("Should be true: " + (a instanceof compsci61b.MyArrayList));
System.out.println("Should be true: " + (a instanceof java.io.Serializable));

Implement the "MyList", "MyLinkedDataStructure", and "java.io.Serializable" interfaces. It should have a private inner class named "Node", similar to the old version of this class, but with an added link: prev. So write it like this:

private class Node implements java.io.Serializable
{
  private T value; // a single value (or a reference to one, actually)
  private Node next; // link to downstream Node
  private Node prev; // link to upstream Node
}

Also add a new data member, private Node tail, to track the last node in the list. This will speed up the operation of public boolean add(T value) significantly. (We'll look at this in the next lab assignment.)

Add 2 more data members: private Node currentNode, which is a reference to the last-accessed node (to speed up accesses to adjacent values) and a integer to track the index associated with this reference, private int currentIndex. Set and manage these in the constructor, the accessors "getEntry" and "contains", and the mutators "clear", "remove", "replace", and "add".

Here is an updated version of "getNode", for a head reference named head, a tail reference named tail, and #of values tracked in nValues.

  private Node getNodeAt(int index) // seek index from closest reference: head, tail, or currentNode
  {
    Node result = null; // null if index < 0 or index >= nValues -- usually when index == nValues (adding to end)

    // initialize current position to its default, the head
    if (currentNode == null)
    {
      currentNode = head; // possibly still null
      currentIndex = 0; // ignored if currentNode is null
    }

    // find which reference is close and traverse from there
    if (0 <= index && index < nValues && nValues > 0)
    {
      assert head != null && tail != null;
      assert currentNode != null && currentIndex >= 0 && currentIndex < nValues;
      assert index >= 0 && index < nValues;

      // "intelligent" seeking by chosing the best of 4 possible starting points and directions
      if (index < currentIndex) // requested index is LEFT of current -- seek towards head from current, or towards tail from head
      {
        if (index < (currentIndex - index)) for (currentNode = head, currentIndex = 0; index != currentIndex; currentNode = currentNode.next, currentIndex++);
        else for (; index != currentIndex; currentNode = currentNode.prev, currentIndex--); // search towards head from currentNode
      }
      else // requested index is RIGHT of current -- seek towards tail from current, or towards head from tail
      {
        if ((index - currentIndex) < (nValues - index)) for (; index != currentIndex; currentNode = currentNode.next, currentIndex++);
        else for (currentNode = tail, currentIndex = nValues - 1; index != currentIndex; currentNode = currentNode.prev, currentIndex--);
      }

      assert currentNode != null;
      result = currentNode;
    }

    return result;
  } 

For public interface validation, use the same test.java as in lab 2a's exercise 2, but import compsci61b instead of compsci61b.testing, and use these statements to create and validate the data structure object:

MyList<Integer> a = new MyLinkedList<Integer>();
...
System.out.println("Should be true: " + (a instanceof compsci61b.MyList));
System.out.println("Should be true: " + (a instanceof compsci61b.MyLinkedDataStructure));
System.out.println("Should be true: " + (a instanceof compsci61b.MyLinkedList));
System.out.println("Should be true: " + (a instanceof java.io.Serializable));

[ Home | Contact Prof. Burns ]