Assignment 2 - More Java Constructs

Due in Lecture Jan 27

Implement and test a Java class MyList that implements a linked list. Your class should provide the following methods:

boolean add(Object x) - add x to the end of the list and return true
boolean contains(Object x) - return true if the list contains x
boolean remove(Object x) - remove the first occurence of x from the list. Return true if the list contained x
boolean isEmpty() - return true if the list is empty, and otherwise false
Iterator iterator() - return an iterator for this list
int size() - return the number of elements in the list
Object[] toArray() - return an array containing all the elements in the list

For precise specifications for these operations, see the online documentation for the List interface. (If we were really doing this right, you'd have MyList implement the List interface, but then you'd have to implement all of the list operations, so we're not requiring this. You can just make it a subclass of Object.)

You will need to define your own iterator class for MyList. Use an inner class (inside of MyList) for this. If next() is called on an iterator that has reached the end of the list, raise an appropriate exception. This iterator doesn't need to support the remove operation - throw a UnsupportedOperationException if this method is called. See the spec for the Iterator interface for details.

You should also define your own MyLink class - also use an inner class for this.

The return type for add may seem a bit odd. This is the general signature for the add method in Collection, which returns false if this collection does not permit duplicates and already contains the specified element. However, lists can have duplicate elements, so this version add always returns true.

You don't need to handle the problem of adding or removing elements from a list with an active iterator. (The problem here is: what should you do if the list is modified by another part of the code while you're in the middle of iterating through it? In case you're curious, see Class LinkedList for a description of how this is handled in Java itself.)

Testing

Write a JUnit test that provides good tests for all of the methods of MyList.

Deliverables

Turn in the hardcopy listing for your class MyList and also for MyListTest (the JUnit test class). Also turn these in electronically using turnin - see the homework submission guidelines. To do this, use the "export" command in Eclipse to export your MyList and MyListTest classes (just the Java source) to a zip file (say listclasses.zip). Then turn in the zip file using the turnin program:

turnin listclasses.zip

(turnin will prompt you for the course and section)

Suggested Approach

There are two new things to try in this assignment: JUnit and inner classes, as well as the general linked list manipulation issues. Take these one at a time. First, make sure you understand JUnit. Define some very simple little class (not to hand in), and write a JUnit test for it, and make sure everything is working. Then, start defining your MyList class. An excellent approach is to test as you go, as much as you can, writing the tests at the same time you implement the MyList methods.

To serve as a somewhat analogous example, we've put the MyArray class online, as well as a class MyArrayTest. The easiest way to get these is via cvs -- see See Using cvs with Eclipse for details.

Otherwise you can download them here:

zip file with MyArray, MyArrayTest, BankAccount, BankAccountTest

Note that MyArray is improved a bit over the version distributed in class on Jan 15, since the iterator now handles remove correctly. You can handle remove in exactly the same way in your class, and test it in the same way as well. If you don't use cvs, you will need to link in JUnit as an external JAR to use this in a new project -- see the 341 Java help file.

Extra Credit

For 10% extra credit, implement the remove method for the list iterator (so that it actually removes something rather than throwing an exception), and so that your iterator is fail-fast in case the list is modified by something other can calling the iterator's remove method, as described in the Java documentation. You should definitely get the basic homework assignment working before trying this.