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 bears 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.
Clone the repository with the files for this lab from the course directory.
The files INode.java and IList.java are what we have seen in class, with a few additions. You will be doing all of your work today in IList.java.
The other files provide additional testing, but you will not modify them. IListTest.java provides a main method that does more extensive testing, and the file correct.out contains an example of what its output should (eventually) be. The other three source files implement sorting on linked lists; they will be explained below.
Open IList.java in emacs and inspect it. There is one new feature from Java that it uses: you’ll see the statement
in several methods, such as removeFront(), that have not been implemented. Executing this statement causes (throws) a new exception, which carries the string along as a message about what happened.
The file already contains the methods isEmpty(), insertAtFront(), deleteFront() and printList() that we wrote in class, plus our incomplete effort on deleteAt(). In addition, the method elementAt() has been filled in; you should note that it is similar to what we had written for printList() and deleteAt(). (There is a copy of those methods at the end of these instructions.) The form here provides a model that can be adapted to other uses. The while loop tests for the end of the list; so we can put whatever should happen at the end after the loop. (In this case, the precondition has been violated; so we cause an exception.) The if inside the loop tests whether we have found the node we want and provides appropriate action (including, in this case, returning). The rest of the loop body is what we do for nodes we are skipping over.
Next look at deleteAt(). Finding the correct node is the same: counting does the job. But now we want to remove the node place. To do that, we need to change the link in the node before place. Depending on our test, there may be ways to stop one node early, but a more general solution is to introduce another variable that keeps track of the node before place. Try that, without worrying too much about deleteAt(0). There is already a call for deleteAt(2) in the test cases; so you should be able to see if your method works.
Now think about how to deal with deleting the node at position 0. Make it work, and add another test to main() to demonstrate it. After a successful test, commit your changes to the repository.
Now continue to fill other unimplemented methods, testing and committing after each works. Do these first:
If you have some extra time after you do the rest of the lab, you might come back to these, and any others that look interesting:
You can put whatever you need for testing into the main() method in IList.java.
I have also provided IListTest.java to test more methods. Compile it (along with IList.java) and run it. It catches the exceptions from the methods you might not have implemented yet. If you want to check your output, you can run
to capture the output in the file test.out. You can compare that file with the correct, complete, output in correct.out with the command
You won’t have complete output until you do the remaining steps, but you can check things as far as you have done.
The rest of this lab will walk you through how to write the methods needed to make sorting work.
ListSort.java is a driver program similar to the one from projects 3 and 4; you will not need to change ListSort, but you can look at it later when you have some time (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), using the IList class.
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.
The lists we will be sorting today contain only positive integers. To make your job a little easier, the sorting methods create the new pile (list) with the method newSortList() instead of the constructor. This starts it out already containing an element with the value zero, which means that you will be inserting (positive elements) after a node that already exists. When the sorted list is printed, it will therefore have an extra zero at the front; we’ll live with that for now.
Although the sort method is done for you, the method insertSorted() is not. You need that, along with the removeFront() that you should have already written.
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
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 (if you haven’t already).
Once you have those done, you should be able to sort by selection with the command
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.
Commit again when you do that.
Turn in your modified source files with
If you worked on part 4, turn in IList0.java along with IList.java.
Be sure that you copy your work to your account, because you will want it for project 7. In fact, the first phase of project 7 will include completing whatever you did not get done in lab today.
Back.