Comp 271 lab 7 - sorted lists
Goals
- keeping a linked list in sorted order
- sort comparisons
Overview
Start with the sortedlist.zip project.
Note that the element type is constrained here to be something that
implements the Comparable interface, so that you are
guaranteed that elements can be compared with compareTo().
Implement the add() method that inserts a new element in order.
Note that you are using the Comparable interface here. Make sure all list mutators keep the elements in order!
I had to consider three cases in my add(T value):
- inserting into an empty list
- inserting the new element before the existing first element
- inserting the new element after an existing element
The last case theoretically has two subcases -- inserting at the end
and not at the end -- but in my code these turned out not to be
different. I had a (while p!=null && p.data is less than value)
loop; if it ends with p==null then you're inserting at the end,
otherwise in the middle. Either way, you will need a Cell pointer prev
that points to the previous cell -- Bailey calls this the "finger"
technique -- which is the one that is actually modified. There's an
example of such a loop in the remove() method.
Also implement a verifySorted() method that verifies that the
data present are in ascending order.
Then, compare the speed of our earlier Insertion Sort with the speed
of inserting the same number of elements, from the array master,
into your SortedList. (Arrays are faster. How much faster?)
I had originally planned to include a binary search, but that fails
to be faster than O(n) on a linked list (versus O(log n) for an array).
The problem is that jumping to a middle element is sloooow.
To submit your project, create a zipfile and email it to me at
pld@cs.luc.edu.