Lab 10: Linked Lists

This goal of this lab is to practice writing operations for linked lists, which you will continue in the next project.

1. Introduction

In this lab we revisit the problem of sorting, but this time we will be sorting linked lists instead of arrays. This lab will bear some similarities to project 3, which you may want to glance at for review.

Sorting of arrays is often done in place (in situ, if you like Latin). Today, however, we will sort by creating a new list and filling it with elements removed from the old list.

Note: In this lab, you may assume that the lists will contain only positive values.

Clone the repository with the files for this lab from the course directory.

$ hg clone /cslab/class/csci235/labs/lab10

INode.java is the same node class as we have seen in class (for the iterative version of lists). ListSort.java is a driver program; you will not need to change ListSort, but feel free to look at it (though it contains some advanced stuff you don't have to understand). ListInsertion.java contains a complete static sort() method that does insertion sort (explained below) IList.java is a partially-written list class, similar to the one we have worked on in class; you will need to complete it.

2. The IList class

Open IList.java in emacs and inspect it. It already contains the necessary instance variable, the constructor, and methods isEmpty(), insertAtFront(), and print(). For the most part, we will be assuming that our lists are never empty; however, as we remove items from a list, it will eventually happen that we will remove everything and be left with an empty list. Thus we have the isEmpty() method, which simply checks if our head is null.

This lab will walk you through how to write the other methods.

3. Insertion Sort

Open ListInsertion.java in emacs and inspect it. Make sure you understand how it works before going on; it makes use of list operations you have not yet written. This is how insertion sort works: you have an unsorted pile and a sorted pile. In each step, you remove the next item in the unsorted pile and insert it in the correct place in the sorted pile. Read the method carefully and connect this description of the algorithm with the code.

One odd feature is that the new pile (list) is created with the method newSortList() instead of the constructor. This starts it out already containing an element with the value zero, which makes inserting into the correct place easier: you can be sure that you are always inserting after a node that already exists. When the sorted list is printed, it will therefore have an extra zero at the front.

Although the sort method is done for you, the methods removeFromFront() and insertSorted() are not. You need to write these. Note that in this lab the methods that begin with remove are similar to the delete methods we wrote in class, but they return the item that is removed from the list.

removeHead() To think through this first (and fairly easy) method, draw an example list, and include in your drawing a variable head referring to the head of the list. What would you need to do in order to get rid of it? What change would need to take place on the variable head? Now, be careful: this method does not only remove the old head from the list; it also returns the value of the old head (not the new head). Don't forget to add documentation to all of these methods as you write them.

insertSorted() Given an item, you need to find the right position for it, create a new node for it, and link it into the list. The trick is to keep track of the place in the list that the new items must come after. Also, one thing that will make this easier is the remember that the sorted list starts off with a zero item as its initial head. Since all the items you'll be sorting will be at least 1, you will never have to insert an item before the head.

Compile and test. You can use the main() method in class IList to test particular method calls or sequences of calls. When you think you have it working, you can test the sort with

$ java ListSort ListInsertion

You can run it more than once; each time it starts with a new randomly generated sequence.

This would probably be a good time to commit your changes to the Mercurial repository.

4. Insert at the head

Those extra zeros at the beginning of your sorted lists are annoying and wimpy. So fix the IList class to get rid of them.

Important: Before you start on this, be sure that you have committed your changes, and copy IList.java to IList0.java so that you can turn in both versions. You will continue to work on IList.java.

Modify newSortList() so that it returns an empty list instead of one that has a zero, and update its comments. Then fix the insertSorted() method that you wrote so that it works when inserting into an empty list or before the head.

Commit.

5. If you have time

If you have any time left, take a 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. This depends on two methods, insertAtBack() and removeSmallest().

insertAtBack() should not be too hard, because you have already written methods that do insertion; you just need to find the last node and insert after it.

You have been provided with an initial version of removeSmallest(): it calls the methods findSmallest() and deleteFirstOccurrence() to do the work. You need to fill on those two methods. Note that we wrote most of the latter in class; you need to deal with the possibility that you are deleting the first node.

Once you have those done, you should be able to sort by selection with the command

$ java ListSort ListSelection

Commit that.

It works now, but the provided removeSmallest() makes two trips down the list, first to find the smallest, and then again to delete it. Rewrite this method so that it finds and removes the smallest in a single pass.

6. Turn in

$ /cslab/class/csci235/bin/handin lab10 (names of java files)

7. Copy your work