CompSci-61B Lab 2b
ADT Lists

In this assignment, we complete the development of a CompSci-61B version of the "AList" class that appears in Carrano chapter 5. The classes "MyArrayList" and "MyLinkedList" are similar to Java's own "ArrayList" and "LinkedList" classes. They implement the "MyList" interface from the previous lab, and are stored in the package "compsci61b.testing". New versions of these classes will be written in future labs and stored in the package "compsci61b", when "iteration" support is added.

This assignment is worth 40 points, and consists of 4 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 lab2b.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.

It will be convenient in future labs to identify data structure classes as being either array-based or linked-list-based. So we will create two interfaces: "MyArrayBasedDataStructure" and "MyLinkedDataStructure", to be implemented in data structure classes. (These will be resuable for future labs, so they will be placed in the package "compsci61b" -- the first items to be placed there.)

Write the interface MyArrayBasedDataStructure.java in package compsci61b, using lab 2a's exercise 1 as a model. Include no method specifications -- the space between the curly braces of the public interface should be blank.

Compile and jar, but do not run, because this is an interface, and because it has no main.

Apply the same test.java as in lab 2a's exercise 1, changing the class name to MyArrayBasedDataStructure, and add this import statement:

import compsci61b.*;

Compile and jar, but do not run, because this is an interface, and because it has no main.

Apply the same test.java as in lab 2a's exercise 1, changing the class name to MyLinkedDataStructure, and add this import statement:

import compsci61b.*;

The class should be similar to Carrano's "AList" in chapter 5, without the 2nd constructor, with zero-based indexing, and with "toString" instead of "display", and with automatic array expansion so that the data structure is never full. Also, this new class should implement the "compsci61b.testing.MyList", "compsci61b.MyArrayBasedDataStructure", and "java.io.Serializable" interfaces. Since "MyArrayBasedDataStructure" is in a different package, you need to append "compsci61b.", or import it:

import compsci61b.MyArrayBasedDataStructure;

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. Make sure that the array expansion and shifting code works correctly. Your work will be scored using a separate testing program that is not provided to you. So make sure that your own testing is sufficient to assure yourself that the class works according to the specs. If you have any questions about the specs, ask in lab or use the online discussion group -- don't assume anything.

For public interface validation, use the same test.java as in lab 2a's exercise 2, but 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.testing.MyList));
System.out.println("Should be true: " + (a instanceof compsci61b.MyArrayBasedDataStructure));
System.out.println("Should be true: " + (a instanceof compsci61b.testing.MyArrayList));
System.out.println("Should be true: " + (a instanceof java.io.Serializable));

The class should be similar to Carrano's "LList" in chapter 7, with "toString" instead of "display". Also, the class should implement the "compsci61b.testing.MyList", "compsci61b.MyLinkedDataStructure", and "java.io.Serializable" interfaces. Since "MyLinkedDataStructure" is in a different package, you need to append "compsci61b.", or import it:

import compsci61b.MyLinkedDataStructure;

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
}

To test the class operation, include a main inside the class. In main, create a "MyList" object using "MyLinkedList", and exercise all of its methods. Your work will be scored using a separate testing program that is not provided to you. So make sure that your own testing is sufficient to assure yourself that the class works according to the specs. If you have any questions about the specs, ask in lab or use the online discussion group -- don't assume anything.

Here is a useful private method and the "toString" to get you started, for a head reference named head, and #of values tracked in nValues:

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

    if (0 <= index && index < nValues) // validate index
    {
      result = head;
      assert result != null;
      for (int i = 0; i < index; i++)
      {
        result = result.next;
        assert result != null;
    } }

    return result;
  } 

  public String toString()
  {
    String buf = getClass().getName();
    if (isEmpty())
      buf += " is empty";
    else
    {
      int i = 0;
      for (Node p = head; p != null; p = p.next)
        buf += "\n value[" + i++ + "] = " + p.value;
    }
    return buf;
  }

For public interface validation, use the same test.java as in lab 2a's exercise 2, but 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.testing.MyList));
System.out.println("Should be true: " + (a instanceof compsci61b.MyLinkedDataStructure));
System.out.println("Should be true: " + (a instanceof compsci61b.testing.MyLinkedList));
System.out.println("Should be true: " + (a instanceof java.io.Serializable));

[ Home | Contact Prof. Burns ]