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

There are two driver programs included here. One is a version of the ListSort program from lab 10. 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 ListDriver.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 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".

1a. Insertion sort

Start by copying in the bodies of the methods removeHead() and insertSorted() that you wrote for lab 10. Verify that they work by compiling

$ javac ListSort.java ListInsertion.java IList.java

$ java ListSort ListInsertion

1b. Selection sort

Now look at 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() We completed this method in class on Friday.

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. Get rid of the zeros

As you did in the lab, change newSortList() to return an empty list instead of one that has a zero. If you completed it in the lab, insertion sort should now work correctly; if not, it is now time to fix insertSorted() to deal with an empty list or insertion before the first node.

Fix addToBack() so that it works correctly on an empty list, and verify that selection sort works now, too.

Commit.

1d. 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.

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

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 Friday we worked on the same list interface, 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 has already been done, for example, for count() and deleteFirstOccurrence().

Notice how the methods in the node class that modify the list (such as the delete methods) return a node representing the rest of the modified list. A node keep 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.

One way to do removeFromBack() is to have the list method make two recursive calls on head: the first returns the value of the back node, and the second modifies the list by doing the removal. 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. It can be done, but it's a bit 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: Tuesday, April 14, at 5:00 PM.