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 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 in lab 11b. You have already done much of this. So copy your version of IList.java in place of the one here. Go ahead and commit to your repository now, with a log message indicating that you copied in lab 11b. You need to make three changes to your file to prepare for this project:

1. Change the first line of the class declaration to

   public class IList implements List235 {
   

2. Insert a new @author tag line in the opening comment, with just your name. Leave the old line there (with credit to your lab partner), but replace "@author" with "Lab 11 author".
3. Change the comment about Lab 11 to identify this as Project 7.

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

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

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.

There are only a few methods in RList that you will have to change. Where I have provided a call to a method in RNode, feel free to change the node portion of the interface if you find it helpful.

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. First make sure that all of your changes have been committed; the command

$ hg summary

$ hg revert -r 8 ListDriver.java

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, November 17, at 5:00 PM.