The TAO of Java


Laboratory: Vector-Based Lists

Summary: In this laboratory, you will have an opportunity to enhance your understanding of the list ADT through an implementation using vectors.

Contents:

Required Code Files:


Exercises

Exercise 0: Preparation

a. Create a package named username.lists.

b. Put all of the files linked above in that package.

c. Make sure to change the package name in each file.

Exercise 1: Code Reading

a. Read the SimpleList interface and verify that all the operations you expect to see are there.

b. Read the SortedList interface and explain how, if at all, that interface differs from the SimpleList interface.

Exercise 2: Using Simple Lists

a. Sketch a method, toString(SimpleList<T> lst) that converts a simple list to a string of the form (val1 val2 ... valn). By sketch I mean that you should write approximate code, but you need not test the code.

b. Sketch a method, zap(T val, SimpleList<T> lst) that removes all values equal to val from lst.

c. Compare your methods to the similar methods in ListHelper.java.

Exercise 3: Testing Simple Lists

The class TestVBSimpleList permits you to test the vector-based implementation of simple lists. You can run it with

ji username.lists.TestVBSimpleList val1 val2 ... valn

Verify that vector-based simple lists behave the way you expect.

Exercise 4: Testing Sorted Lists

The class TestVBSortedList permits you to test the vector-based implementation of sorted lists. You can run it with

ji username.lists.TestVBSortedList val1 val2 ... valn

Verify that vector-based sorted lists behave the way you expect.

Exercise 5: Implementing Sorted Lists

a. Examine VectorBasedSortedList and explain why it contains only one method.

b. What flaws do you anticipate in this implementation?

Exercise 6: Improving remove

You may note that the remove method in VectorBasedSimpleList is implemented as follows:

public void remove(ListCursor<T> c)
{
  int pos = ((VectorBasedListCursor<T>) c).pos;
  // Vector.remove shifts elements left.
  this.contents.remove(pos);
} // remove(ListCursor<T>)

As we've discussed previously, the Vector.remove operation is not very efficient, as it must shift the remaining values left in the Vector. Since simple lists need not maintain the order of values, we can make remove more efficient by moving the last element in the Vector to the designated position.

a. Implement that change in VectorBasedSimpleList.

b. Verify that VectorBasedSimpleList continues to work correctly, as in problem 3.

Exercise 7: Unforseen Consequences

Because VectorBasedSortedList inherits from VectorBasedSimpleList, changes to the latter may affect the former.

a. Determine whether the changes have had any effect (presumably by using the test program and removing values).

b. Repair any difficulties that the change to remove has had (perhaps by reinserting code for remove in VectorBasedSortedList.

History

Sunday, 27 November 2005 [Samuel A. Rebelsky]

Monday, 28 November 2005 [Samuel A. Rebelsky]

Tuesday, 29 November 2005 [Samuel A. Rebelsky]


This page was generated by Siteweaver on Tue Nov 29 10:44:01 2005.
The source to the page was last modified on Tue Nov 29 10:43:59 2005.
This page may be found at http://www.cs.grinnell.edu/~rebelsky/TAO/Labs/vector-lists.html.

You may wish to validate this page's HTML ; Valid CSS! ; Check with Bobby

Samuel A. Rebelsky
rebelsky@grinnell.edu