This goal of this lab is to practice writing operations for linked lists, which you will continue in the next project.

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 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.

INode.java and IList.java are the same as what we have seen in class, with a few additions. ListSort.java is a driver program; you will not need to change ListSort, but feel free to look at it after you get done with your work (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).

2. The IList class

Open IList.java in emacs and inspect it. It already contains the methods isEmpty(), insertAtFront(), deleteFront() and printList() that we wrote in class. There is one new method, elementAt(), which provides a model for working down the list looking for a particular node. (There is a copy 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.

Copy the body of this method into 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.

3. Insertion Sort

The rest of this lab will walk you through how to write the methods needed to make sorting work.

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 methods removeFromFront() and insertSorted() are not. You need to write these. Note that removeFromFront() is similar to the deleteFront() that we wrote in class: the difference is that it returns the value of the removed item.

removeFromFront()
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

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.

4. Insert at the head

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.

5. If you have time

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.

Once you have those done, you should be able to sort by selection with the command

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.

6. Turn in

7. Copy your work

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.

Appendix: from IList.java

    /**
     * Get the value of the item at a specified position.
     * @param position The position in the list.
     * @return The value at position in the list.
     * PRECONDITION: position >= 0 and position < length of this list
     */
    public int elementAt(int position) {
        /* This is not the most compact way to write this,
         * but this form can be adapted to other uses.
         */
        INode place = head;  // the node we are looking at
        int i = 0;           // the position of place
        while (place != null) {
            if (i == position) { // is place the node we want?
                return place.datum();
            }
            // do something before going to the next node
            i += 1;
            place = place.next();
        }
        // ran off the end
        place = place.next(); // cause an exception  -- precondition violated
        return 0;
    }

    /**
     * Delete the item at a specified position.
     * @param position The position in the list.
     * PRECONDITION: position >= 0 and position < length of this list
     */
    public void deleteAt(int position) {
        System.out.println("IList.deleteAt() has not been written.");

    }

CSCI 235 Lab 11: Linked Lists