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 lab. 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 in lab 9. 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 9, and a handful of other methods that you 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.

2. Recursive lists

The implementation of lists that we have gone over in class has been iterative: 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 a complete class RList that implements the List235 interface. Your job is to complete the implementation of the methods in the RNode class. Note how the RList class takes care of most of the head-of-list or empty-list conditions.

Tip: It probably helps to think of an RNode as representing "the chain of nodes that begins with this one" or "the rest of this list". The recursive methods then can be thought of working on that collection of nodes.

You can use the ListDriver to test your methods.

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. Turn in

Restore the tests in ListDriver so that the original tests are all there.

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 them should produce exactly the same

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

DUE: Monday, April 7 Wednesday, April 9, at 5:00 PM.