Complete an doubly-linked list implementation of the java.util.List interface.
Text: Java Tutorial: List interface.
Concepts: interfaces; abstract classes; List ADT.
First, familiarize yourself with the List interface with the reading above. In particular, pay attention to the description of how ListIterators work, since you will be implementing one. Also useful are the API pages for List, ListIterator, and AbstractSequentialList.
Then download the following code:
Do not change DLNode.java. Read through the LinkedList and LinkedList.LinkedListIterator code, then complete the 5 unfinished methods (each marked with //TODO). You should read the ListIterator API and tutorial to learn what each of these methods must do. (Clarification, 22 Oct 2012: You may have to slightly modify some of the existing LinkedListIterator methods to implement your own.)
We can leave the @Override methods undocumented since, if we do not write new documentation, the javadoc tool will pull the existing documentation from the method we are overriding/implementing. This is fine here, since that inherited documentation describes exactly what each of your methods is supposed to be accomplishing.
A07.java includes some tests of the existing methods. Rename this file (and the class inside) to UsernameA07.java For most of the tests, this class uses the provided assertEquals method that takes a description of the test, an expected value, and the actual value. This method will then report to the screen whether that test passed or failed based on whether the two values actually equal each other. Add similar tests using the assertEquals (or similar methods of your own) to test your implementation of the 5 new methods.
You will then submit these files to Tamarin, which will use (test) your complete ListIterator implementation.
As per A07.java, but more so.
Create a .jar file named UsernameA07.jar. This should include:
Upload your UsernameA07.jar to Tamarin.
Remember to follow the course coding standards on all assignments.
If you're using the last variable described in the FAQs below, remember that == tests object identity. That is, you can use last == next or last == previous to find out which of those two nodes last refers to.
It depends. See the API for how the remove method is supposed to work. Make sure to click the method name link and read the full description of what the method does.
When you read the API, you'll find that remove() is supposed to remove the Node of the element most recently returned by either next() or previous(). Also, remove() should throw an IllegalStateException if add() or remove() was called since the most recent call to either next() or previous().
For example, suppose you have this list:
A B C . D E
Suppose the iterator is currently between C and D, as marked by a '.'. That is, previous is the Node containing C (previousIndex() == 2) and next is the Node containing D (nextIndex() == 3). If remove() is now called, which Node gets removed? The one containing C or the one containing D?
The answer depends on how we got to this position. If the most recent movement was due to a call to next() (which would have advanced the iterator over the C node), then the node containing C should be removed. If the most recent movement was instead a call to previous() (which would have moved the iterator backwards over the D node), then the node containing D should be removed.
All of the requirements of the remove() method can be met with the addition of a single instance variable that holds a reference to the last Node from which you returned an element. You can call this variable whatever you want, but I'll call mine:
//node of value returned by last call to either next() OR previous() private DLNode<E> last;
This last variable should be set to null in the iterator's constructor. This null value will indicate that neither next() or previous() has been called yet, or that add() or remove() has been called since the most recent next() or previous().
In both next() and previous(), set last to whatever node you just passed over and returned a value from. (This means you'll have to update the code in the next() method.)
In the add method, always set last back to null. (Again, an edit of the existing code is required.)
Then, in remove(), if last == null, we don't know what node to remove(), so throw an IllegalStateException. Otherwise, remove the node that last points too, then set last to null to prevent a second call to remove.
The set method works similarly: you're supposed to change whatever was last returned by either next() or previous(). If these haven't been called yet or if add or remove has been called since (all of which mean last == null), then set should throw an IllegalStateException instead.
For the most part, no. For example, you won't throw any UnsupportedOperationsExceptions because you're going to support all of the operations. You don't need to throw any IllegalArgumentExceptions because we're not going to impose any restrictions on the elements you can put into our LinkedList. ClassCastExceptions won't get thrown because we're not casting or requiring particular element types.
So the only exceptions you really need to worry about are IllegalStateException in remove and set and NoSuchElementException in previous() (and next()).