Overview
This introduction to using linked lists walks you through building a class
that keeps a sorted list of numbers. That list is stored in a linked list.
The already-written supporting program reads in a series of double values,
stores them in your SortedList as they are read, and then prints out the
string representation of the sorted list that your class provides.
The data is stored like:
We provide the NodeDouble class in the NodeDouble.java file. This is a simplification of the text's DoubleNode class in that it contains only the constructor, getData, setData, getLink, and setLink methods. You will do the adds (and the removes when you use it for the sequence assignment) directly in your code. But the class encapsulates the private data, and its use is compatible with the class in the text.
We also provide a small program in the SortNumbers.java file. It reads in numbers typed by the user and asks to have them inserted into the SortedList object you will build.
There is a one case JUnit test class named TestSortedList.java. You will enhance it as part of this assignment.
Before coming to lab, do the following:
- Read through these directions.
- Copy the supporting files from ~rogers162/labs/SortedList to your space.
- Create a project.
- Create an initial SortedList.java class file.
Steps for Starting the SortedList class
Understand the representation. This class will have one instance variable, listHead, that is a pointer to the front of the list of NodeDouble type nodes. It may be null if the list is empty. If the list is not empty, its values are stored in increasing order in a linked list of NodeDouble nodes.
Create the representation. Write a class invariant comment describing the representation. Declare the private instance variable. Write a constructor that initializes the instance variable and ensures the class invariant is met. Hint: setting listHead to null is appropriate. Realize that the empty list is, by default, sorted. So your empty constructed list meets the class invariant.
Write a simple insert method that doesn't sort. Start simply. Write an insert method that takes in a value as its only parameter and adds it after the head. It will effectively put the value at the front of the list. This isn't the "right" action, but it gets values in the list. They will be stored with the last value entered at the beginning. No, this version does not meet the class invariant.
In this method, the one statement is to set the listHead instance variable to point to a newly created node containing the value and a link to the current listHead.
Draw a picture of what happens as you add three values to the list. Drawing pictures will help you tremendously as you build more complex data structures.
Add a descriptive comment to this method.
Add a toString method. To be able to see what is in the list, you need to create a string representation of it. Write a toString method that shows the data of the list with the elements separated by a single space. There are no leading or trailing spaces. The method returns a String.
The code will look a lot like the code for printing the list. Think about what needs to happen. Remember that you can't just look at the data instance variable of the node. Use the getData( ) method. Be sure to move to the next node in the list by getting the link to the next node with the getLink( ) method.
Don't make this harder than it is. However, you do need to have a special case to avoid leading or trailing spaces.
Include a useful descriptive comment on this method.
Play with it. At this point, you should be able to run the SortNumbers program. Test it with a few values. They are in backwards order to how you put them in, right? That's right. Does it work with one value? Three values? No values? Negative values? Characters like commas (it should stop with last good value before the things that aren't doubles)? Don't change SortNumbers.java.
Steps for Keeping the List Sorted
Understand insertion sort approach to keeping list sorted. The insert method will do an insertion sort by looking through the sorted list trying to find where the item should be inserted. To do that, it needs to walk down the list until the next node contains an entry bigger than the one to be inserted. Then, it inserts this value into a new node placed in front of the node with the bigger value. You need to find the node that will link into (preceed) this new node.
Find the node that will preceed the new node.
In insert, declare a node pointer called preceding
to hold the address of the node that will preceed the one we'll insert.
Assign it the result of calling a private method called getPrecedingNode
that takes the new value as its parameter.
This method is a lot like the search methods in the toolkit.
The method prototype should look like:
private NodeDouble getPrecedingNode(double value)
Its post-condition is that the returned value will be null if value
is smaller than every item in the list and should, therefore, be added at
the front (after the listHead).
Otherwise, the returned pointer will be to the node that will
be before the added node.
This function uses two node pointers to move through the list. It does not create any new nodes. The pointer called precursor points to the node that might be the one you'll put the new node after. When you get to the right place, you'll return its value. The one called cursor points to the node you're examining as possibly having a larger data value than the one you want to insert. Read carefully about how to walk down the list.
The algorithm is expressed very clearly here in English.
precursor starts out null suggesting you'll insert at the front
of the list unless you find a more appropriate place.
cursor starts out as listHead.
Now you need to find the correct value for precursor.
Write a loop that continues while there's still some list (non-null cursor) and the value you're trying to add is bigger than this node's data. Remember that you never, ever try to access the methods of the null reference. If you get into the loop, remember this node in precursor and update cursor to the following node. Eventually one of the two parts of the loop condition will be false. Then you can return precursor.
Insert the node. The getPrecedingNode function returned null if the new node goes at the front of the list. Use the same code you used in your original insert to do that. Otherwise, preceding points to the node to insert after. Use a somewhat longer one-line statement to set preceding's link to point to a new node that contains the value and a link to the node preceding used to point to. You're adding a node after preceding but shouldn't lose the rest of the list that preceding pointed to.
Don't make this harder that it is. Draw pictures. Understand what you're doing.
Test the program. Now, check out your program. Use big and small numbers, duplicates, and values that will go at the beginning and end.
Build JUnit tests to test the program. The TestSortedList.java file contains a single JUnit test - a_check42. Its purpose is to check that a single value (42) is inserted in the list. When the toString method is called, it returns a String containing 42.0.
The assertTrue takes two parameters - the message if the test fails and an expression that should be true.
Write at least four more JUnit methods for TestSortedList that attempt to reveal bugs in your SortedList class. Those test should include inserting at the beginning, end, and middle of the list. Note that even though you might type a number without a fractional part, Java will include a fractional part in its String representation.
Does your program pass your JUnit tests?
Submit
When you are satisfied that your program works as expected,
submit your directory as SortedList.
Both your SortedList.java and your TestSortedList.java files will be submitted.