Lab 11: 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.

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

hg clone /cslab/class/csci235/lab11

Node.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. ListInsertion.java and ListSelection.java are classes that contain completed static sort methods for Lists (the methods will be explained below). List.java is a partially-written list class that you must finish.

2. The List class

Open List.java in xemacs and inspect it. It already contains the necessary instance variable, the constructor, and methods empty(), addToFront(), 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 empty() 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 xemacs 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 quirky thing about this implementation is that we start the sorted pile with a zero element. This merely makes things a little easier, so that you will never have to deal with a possibly empty sorted list. The end result is that the sorted list will always have one extra element, a zero at the front.

Although the sort method is done for you, the methods removeHead() and insertSorted() are not. You need to write these.

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 test this sorting routine by

java ListSort ListInsertion

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 in the back of the sorted pile. For this, you need the following methods.

removeSmallest() Since this is kind of tricky, it is partially written for you, and part of it has been moved over into a separate method. Basically, to remove (and return) the smallest item, you need to (a) find the int value (not the Node) in the list that is smallest; (b) delete the Node that contains that value; (c) return that value. The actual deletion has been moved into a separate method. So, all you need to do here is traverse the list, looking for the smallest item. Add that part to the place in removeSmallest() that is indicated. You may find it helpful to think about how you would do this for an array first, and then translate it to list usage.

delete() This is the most difficult method in this lab. The best way to see it is to split it up into two possibilities: are you deleting the head, or some node other than the head? Complete the method appropriately.

Hint for the non-head case: try a for loop using a variable place like we've seen in class. It will be very difficult actually to delete place; however, deleting the node after place is easy.

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.

5. Extra credit

Those extra zeros at the beginning of your sorted lists are annoying and wimpy. So fix the List class to get rid of them. Important: Before you start on this, be sure that you commit your changes, and copy List.java to List0.java so that you can turn in both versions.

Add a new constructor to List.java that takes no parameters and makes an initially empty list. Also, change the lines List sorted = new List(0). in ListInsertion.java and ListSelection.java to be List sorted = new List(). Then fix up your solution for this lab so that your methods do not assume that you will never insert into an empty list or insert before the head.

6. Turn in

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