Project 7: Linked Lists

The goal of this project is to practice working with linked lists and with recursion.

0. Setup

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

$ cd cs235
$ 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.

ListDriver.java provides a main method that does a variety of tests. The file List235Maker.java contains the Java magic to make it work with any class that implements List235; you don't need to understand what is in there. What you need to know is that you can run ListDriver on a specific list class, say IList, with the command

$ java ListDriver IList

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 (with a little variation) in lab 10. Much of this is already done, using code that we wrote in class. There are a couple of methods that you can copy from what you wrote for lab 10, and a handful of other methods that you still need to write. There are also a couple of methods that have been written, but that you should rewrite to waste less effort.

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. The places you need to do something all contain the text "write" or "copy".

The ListDriver 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 ListDriver IList

You can add other tests to ListDriver 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.

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

2. Recursive lists

We have spent most of the time in class on an iterative version of lists, in which the node class (INode) is very simple, and the work is done in methods on the list class (IList).

Another way to operate on lists is to do so by recursing on the node class. In this approach, most of the work is done in methods on the node class. You have been provided with an almost complete class RList that implements the List235 interface, and much of the RNode class. The things you must do are:

1. Fill in removeFromFront() in RList.
2. Complete the unfinished methods in RNode.

Take a close look at the interface for the delete methods in the node class: they return a node representing the rest of the modified list. You should not change the delete methods in the list class, which uses them properly.

There are two RNode methods from class that we left with ugly names. Fix those two, document them properly, and modify the places they are called in Rlist.

Finally, if you need a little more challenge, see if you can figure out how to provide suitable methods in the node class so that the removeFromBack() in RList calls just one recursive method. As the comment says, this is tricky.

You can use the ListDriver to test your methods. The results should be identical to what you get with the iterative list classes.

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 both addToBack() and removeFromBack() 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 consttructor 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.
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 ListDriver so that the original tests are all there. Fill in additional test to make sure that you test all of the methods in the List235 interface, including all of the interesting cases.

Make a typescript that shows you compiling all of your Java files and running ListDriver for each of your list classes. Note that each of list class should produce exactly the same output.

6. Turn in

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

DUE: Monday, November 17, at 5:00 PM.