Project 7: Linked Lists

The goal of this project is to practice working with linked lists and with recursion. You will be completing several implementations of the linked lists.

0. Setup

As, usual, move into your directory for this class, clone the repository to make a directory for this assignment, and change into it.

$ hg clone /cslab/class/csci235/projects/project7
$ cd project7

Look first at List235.java. This specifies the interface for our various list implementations in this project. You won't need to change this file.

There are two driver programs included here. One is a version of the ListSort program from lab 11. In addition to the ListInsertion class from the lab, there is a ListSelection class that sorts using the selection sort algorithm. In the first phase of this project, you will be completing methods in the IList class so that both of these sorting algorithms work.

The file ListTest.java provides a main method that does a variety of tests, and it works on any class that implements the List235 interface. (The file List235Maker.java contains the Java magic to make it work with any class you specify; you do not need to understand what is in there.) You can run ListTest on a specific list class, say IList, with the command

$ java ListTest IList

As you work on your various list classes, you will probably want to fill in the main() method there for testing with, for example,

$ java IList

When you get close to finishing a list class, you'll want to run ListTest on it. For comparison, I've provided correct sample output in correct.out. You can put the output of a run into a file with a command like

$ java ListTest IList >& test.out

$ tkdiff correct.out test.out &

As you work on the methods for the various list classes, you may want to comment out some of the tests within main(), or you may want to add some tests of your own.

The remaining pairs of files are for three different implementations of lists. Your job is to complete those classes.

1. IList

Your first task is to finish the class IList, which is the version of linked lists that we have looked at in class and in lab 11b. So copy in method bodies from your lab version of IList.java. Also, copy in the name of your lab partner(s) in the heading, on the line below the @author tag, and label those as your lab partners.

Tip: You can search in emacs by typing ^S and then start typing what you want to search for. The easiest way to stop searching is to hit one of the arrow keys. Don't use the mouse while you are in the middle of a search. The places you need to do something all contain a throw statement.

1a. Insertion sort

You should have completed removeHead() and insertSorted() in lab. Verify that they work by compiling

$ javac ListSort.java ListInsertion.java IList.java

$ java ListSort ListInsertion

Commit again.

1b. Selection sort

Now it is time to finish whatever you did not get done to make selection sort work.

Take a moment to read ListSelection.java. Selection sort works by taking the smallest item from the unsorted pile and putting it at the back of the sorted pile. For this, you need the following methods.

removeSmallest() A first version of this method has been written for you. It needs to (a) find the int value (not the node) in the list that is smallest; (b) delete the node that contains that value; and (c) return that value. The work is done in the next two methods.

findSmallest() This method returns the value of the smallest item in the list. You may find it helpful to think about how you would do this for an array first, and then translate it to list usage.

deleteFirstOccurrence() This needs to find a value in the list and remove the node containing it.

addToBack() This should not be too hard now that you've completed the other methods. You merely need to find the last node in the list, and add a new node there.

Remember that you can put test specific sequences of method calls by putting them in the main() method in IList.java.

Once these methods are working, you should be able to test selection sort as a whole with

$ java ListSort ListSelection

Be sure to commit.

1c. Remove the smallest in a single pass

The method removeSmallest() runs down the list twice: once in findSmallest(), and a second time in deleteFirstOccurrence(). Rewrite removeSmallest() so that it searches the list only once (instead of calling the other two methods).

1e. Finishing the class

Fill in the other methods that are not yet implemented; makeReverse() and reverse() are optional, but good practice if you have time. (They are not part of the List235 interface. You'll have to test them from the main in IList.)

The ListTest class provides a main method that you can use to test the various implementations of List235 interface. To run it using your IList class, use the command

$ java ListTest IList

You can add other tests to ListTest if you find that helpful. As you work on other classes, you may wish to temporarily comment out some of the calls in the driver. Note that I have wrapped many of the calls in try blocks so that the program keeps running when it hits most of the unimplemented methods.

You can also put tests for a specific list class in a main() method in that class.

2. Recursive lists

The INode and IList classes provide an iterative (loop-based) version of lists, in which the node class is very simple, and the work is done in methods on the list class.

On Wednesday we worked on the same list abstraction, but using recursion instead of looping. In this approach, most of the work is done in methods on the node class. You have been provided with a class RList that implements the List235 interface, and some of the RNode class. For most of the list methods, you will need to add a corresponding method to the RNode class, as we did in class for length(), elementAt() and deleteFirstOccurrence().

As you write the rest of the methods in the list class (search for throw again), most of them will need a corresponding recursive method in the node class. As you work on these, here are some things to notice:

• Methods like findSmallest() that need to pass along an intermediate result can do that using additional parameters. So the node method findSmallest() will probably have a parameter that is the smallest value seen so far.
• Methods that count down the list, such as elementAt() can take the "steps to go" rather than the absolute position. The recursive calls will pass one step fewer.
• Methods that modify the list (such as deleteFirstOccurrence() are likely to be defined as returning a node to represent the rest of the modified list. Notice how the call in the list's deleteFirstOccurrence assigns the result to head, and the recursive calls in the node class assign to next. A node keeps itself in the list by (possibly) modifying its next link and returning this; a node removes itself from the list by returning a different node.

You can use the ListTest to test your methods. The results should be identical to what you get with the iterative list classes. (Note that ListSort is not set up to be usable with anything but IList.)

3. Doubly-linked

It is sometimes convenient to have a list with links going both forward (next) and backward (previous). The classes DList and DNode provide a framework for implementing this, based on the iterative version.

The DNode class has methods for splicing a node into or out of a list. You need to fill in the body of spliceAfter. Draw before and after pictures for this method, and note that four references must be assigned to accomplish a splice.

There are some methods to fill in on DList, too. Notice that you need to provide findLast(), which will make insertAtBack() work. The other missing methods can be copied from your IList with minimal changes, though the ones that modify the list can much simpler than the corresponding methods for the singly-linked IList.

4. Extra credit: circular doubly-linked, with a dummy node

Start by copying your DList.java to CDList.java; use the Mercurial command

$ hg copy DList.java CDList.java

1. The instance variable should be called dummy instead of head.
2. The list constructor creates the dummy node using the no-argument constructor for DLNode (which takes care of making the list circular).
3. Tests for the end of the list need to change, because there will be never be any null links. The next node after the last one will be dummy instead.
4. findLast() should become trivial.

Once you've done that, everything should work. The splicing methods on DLNode do not need to change. (The checks for null values will never be true.)

5. Comprehensive testing

Restore the tests in ListTest so that the original tests are all there. First make sure that all of your changes have been committed; the command

$ hg status

$ hg revert -r 11 ListTest.java

Make a typescript that shows you compiling all of your Java files and running ListTest for each of your list classes. Note that each of the list classes should produce exactly the same output (except for the first line, which identifies the class).

6. Turn in

Hand in all of your Java files and your typescript as project7.

DUE: Wednesday, April 6, at 5:00 PM.