This goal of this lab is to practice writing operations for linked lists, which you will continue in the next project.
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.
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.
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.
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.
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.
$ /cslab/class/csci235/bin/handin lab10 (names of java files)If you worked on part 4, turn in
IList0.java
along with
IList.java
.