CSE373 Data Structures Wi06 Homework 2

Programming problems due online Thursday, 1/19/06, at 11 pm.
Written problems due at the beginning of class, Friday, 1/20/06, 2:30 pm.
No late assignments will be accepted.

The programming part of this homework involves modifications to the BasicLinkedList and BasicLinkedListTest Java files from the course web. You should download a copy of those files (as well as the interface files from HW1) if you haven't already.

As usual, 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.

What to do - Programming

The goal of this part of the assignment is to modify the BasicLinkedList class to increase the efficiency of various operations. The key modification is to change the underlying representation from a single-linked list to a double-linked list. We also want to use JUnit tests to check that the list works properly initially and that as we make changes no errors are introduced.

You should make the following modifications to the linked list class and tests. We suggest you make the changes in this order, but you are free to do anything that works. Each time you make a small change you should rerun the unit tests to verify that everything still works properly. Your changes 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 the lists, etc.).
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 in BasicLinkedListIterator. Be sure to throw IllegalStateExceptions and ConcurrentModificationExceptions where appropriate.

Constraints

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

1. You may not change the public interface of the list class. Your changes will affect the implementation of the public operations, hopefully making them faster in some cases, but should not change the 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 and next and previous nodes, plus a constructor or two if that is convenient).
3. You should only use nodes needed to store the data in the list - no extra header or tail nodes, etc.

What to do - Written Questions

Answer the following questions on a separate sheet of paper.

1. Goodrich & Tamassa questions R-4.15 through R-4.17 (p. 182).
2. Show that the function 5n + 2n² + 12 is O(n²). (You will need to use the definition of O(g(n)) to do this properly.)
3. Goodrich & Tamassa question R-4.13 (p. 181).
4. Write down a chart of the running times of each of the public operations in the two linked-list implementations of the BasicList interface, including both the basic list operations and the iterator operations. You should include a column for each implementation: one giving the running times of the operations as implemented in the original single-linked list version of the BasicLinkedList class, and the other showing the running times of the modified version using a double-linked list that you produced in the first part of this assignment. For operations that were not implemented in the original class (some of the iterator operations), write down the times these operations would be expected to take if implemented using a single-linked list.

What to turn in

Turn in your programming assignment online using the turnin form linked from the course web site (when available). You should include the Java source code for BasicLinkedList and BasicLinkedListTest, including your modifications.

Turn in your written questions at the beginning of class, Friday, 1/20.