This goal of this lab is to practice writing operations for linked lists.
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/lab13
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.
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.
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
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.
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: Be sure that you commit your changes
before you start the extra credit. Also, 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.
Create a script file (remove the .class
files,
compile, and run), then print the source files that you have
changed with the script. (If you did the extra credit, be sure to turn in both List.java
and List0.java
.)
a2ps --file-align=fill (names of java files) (the name of the script file)Turn in your modified source files with
/cslab/class/csci235/bin/handin lab13 (names of java files)