Lab 10: Linked Lists

This goal of this lab is to practice writing operations for linked lists.

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 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 and ListSelection.java are classes that contain completed static sort methods for lists (the methods will be explained below). IList.java is a partially-written list class, similar to the one we have workd 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. Selection Sort

Now, do the same thing with 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 is the most difficult method in this lab. Note that because you are deleting from the unsorted list, you need to consider that you might sometimes be removing the head. Complete the method appropriately.

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.

Definitely commit things before your try the extra credit.

5. Extra credit

5a. Inserting into empty lists

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.

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

Commit.

5b. 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). Important: Before you start on this, be sure that you have committed your changes, and copy IList.java to IList1.java so that you can turn in both versions.

6. Turn in

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