CSE373 Data Structures Wi07 Homework 2

Due online Saturday, 1/20/07, at 11 pm.
No late assignments will be accepted.

This homework involves modifications to the BasicLinkedList and BasicLinkedListTest Java files from the course web. You should download a copy of those files if you haven't already.

Your code should not only work properly, but it also should be high-quality. In particular:

• Write clean code - prefer simple and clear to complicated, unless there is a compelling reason, which should be clearly explained in comments. Avoid duplicate code or other situations where the same thing appears in more than one place. Use sensible names, indent clearly, and format your code so it blends cleanly with existing code.
• Use appropriate JavaDoc comments to specify all public classes, interfaces, methods, and any other features of your code that need documenting.
• Use appropriate JUnit tests to check that your code works properly initially and continues to work as the code changes.

What to do

Modify the BasicLinkedList and BasicLinkedListIterator classes to implement missing operations and increase the efficiency of others as specified below. A key modification is to change the underlying representation from a single-linked list to a double-linked list.

You should make the following changes. We suggest you do them in this order, but you are free to do anything that works. Each time you make a change you should rerun the unit tests to verify that everything still works properly. For full credit, your code should produce correct results quickly if possible, i.e., if you can do something in O(1) time instead of O(n), you should.

1. The JUnit file BasicLinkedListTest is missing tests for some of the methods in BasicLinkedList. Add appropriate tests to verify the correctness of add(pos,item) (add item at specified position) and all of the remove(...) methods. Be sure to test typical cases as well as boundary cases (operations on empty or single-element lists as well as multi-element lists, operations at the beginning, end, and middle of lists, etc.). But think through the set of tests that you create. You need enough to verify that things work as expected, but creating lots of redundant, overlapping tests is just extra work that adds little value.
2. Speed up the size() method by adding an instance variable to keep track of the size of the list, so that it isn't necessary to count the number of nodes in the list to determine its size. [Hint: be sure to adjust this variable appropriately each time items are added to or deleted from the list.] Also, fix clear() so it uses O(1) time instead of O(n) [Hint: is the list traversal really necessary?].
3. Add an instance variable tail to the BasicLinkedList class to store a reference to the last node of the list (or null if the list is empty). Use this to modify the add(item) operation to add a new item at the end of the list in constant time instead of O(n).
4. Convert BasicLinkedList to use a double-linked list instead of a single-linked list as the underlying representation.
5. Complete implementation of the methods hasPrevious(), previous(), and remove() in BasicLinkedListIterator.
6. Modify the list interface, implementation, iterator, and test classes to use generic type parameters. The existing code handles lists of Objects, but it really should take advantage of generics and be declared as SimpleLinkedList<T>, using a generic type parameter T. This is a fairly extensive modification (hint: look for parameters and variables of type Object - these will almost certainly need to be changed), but it is mostly clerical. You will want to pick an actual type to use in the JUnit tests; it is probably simplest to use String as the type parameter in the tests, since this will allow you to reuse most of the code that is already there. Section 1.5 of the book discusses the basics of generic types in Java. Sun's online tutorial also has a section about generics at http://java.sun.com/docs/books/tutorial/java/generics/index.html.

Constraints

Your changes to the list implementation must follow the following rules.

1. You may not change the public interface of the list class, beyond the changes needed in the last step to use generic type parameters. Your changes will affect the implementation of the public operations, hopefully making them faster in some cases, but should not change their external interface. Of course you are free to modify, add, or delete internal (private) methods that are used only inside the implementation.
2. You should use simple nodes for the linked list (just references to the item stored by that node and next and previous nodes). The nodes may have constructors for convenience, and possibly a toString() method, but should not have other methods that manipulate the node data.
3. You should only use nodes needed to store the data in the list - no extra header or tail nodes, etc., and no circular lists.

Extra Credit

For a small amount of extra credit, once you have the basic assignment working, try the following.

• Add code to the iterator remove() method to throw IllegalStateExceptions if it is called before next() or previous() is called, or if it is called more that once between successive calls to next() or previous().
• Modify the BasicArrayList implementation and iterator to provide missing operations, and incorporate generic type parameters. To verify that your changes work and don't break existing code, create a set of tests for the array-based lists. An easy way to do this is to copy the tests for the linked list version and making appropriate changes.

What to turn in

Turn in your programming assignment online using the turnin form linked from the course web site (when available). You should turn in all of the files (interfaces, implementations, and tests).

Turn in your project early and often. We will grade the last set of files that you turn in. It is a good idea to turn in what you've done after completing major parts of the assignment so that you will have handed in something that works up to that point, even if you run into problems with later parts of the assignment.