Due: Tuesday October 24, 2017 @ 8:00PM
Handout Code is available HERE
This includes an implementation of DoubleNode and an empty implementation of SortedList.
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.
A DoubleNode class is provided in the "DoubleNode.java" file. It is similar to the Node class that we discussed in class, holding double's rather than int's.
Copy all of the files for this assignment from the handout zipfile. SortNumbers.java reads in numbers typed by the user and asks to have them inserted into the SortedList object you will build. SortedList.java contains the method headers for the class you will be implementing. There are NO JUnit tests here — YOU will be writing those.
This class will have two fields:
head, that is a pointer to the front of the list of DoubleNode type nodes. If 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 DoubleNode nodes.length, an integer, that keeps track of how many values are currently stored in the list.Write a class invariant. Write a constructor that initializes the instance variables and ensures the class invariant is met. Hint: setting "head" to null is appropriate. Realize that the empty list is, by default, sorted. So your empty constructed list meets the class invariant.
Start simply. Write an "insert" method that takes in a value as its only parameter and adds it after the head — it doesn't return anything. 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.
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? Does it work with one value? Three values? No values? Negative values? Characters like commas (it should stop with the last good value before the things that aren't double's)? Do NOT change "SortNumbers.java".
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 whose link will be changed — that is, the node that will precede 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 "getPredecessor" that takes the new value as its parameter. This method is similar to the one we wrote in class. The method prototype should be as follows:
private DoubleNode getPredecessor (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 head). Otherwise, the returned pointer will be to the node that will be before the added node. Don't make this harder than it is. DRAW pictures. Understand what you're doing.
public void insert (double value)
private DoubleNode getPredecessor (double value)
// Return the position of "value" in the list,
// -1 if it's not found. Assume the first element in the list has
// index 0.
public int find (double value)
// Remove the value at position "index", if possible.
// Return false for an invalid index, true otherwise.
public boolean removeAt (int index)
// Return the number of values in the list.
public int size ()Be sure to include DESCRIPTIVE comments on your methods! You should include both comments for each method (description, parameters, pre- and post-conditions, return's, and exceptions as you've seen in previous labs) and inline comments on what your code is doing.
Your next task is to test your SortedList class. First add JUnit to your project as you did in a previous assignment. Now you need to create a JUnit test class. Select File -> New -> JUnit Test Case. Ensure "New JUnit 4 Test" is selected at the top. Select the same source folder as your project source code. In the "Name" field, type "SortedListTest". For "Class Under Test", enter "SortedList" — this will allow you to select the methods for which you want to write test cases.
As you are writing your tests, it will help you to refer back to the JUnit tests you have used in prior labs, such as Statistician and Sequence. Two of the primary methods you will use are assertTrue and assertEquals.
// Checks that the boolean condition is true
assertTrue (String message, boolean condition)
// Test that two values are the same.
// Note that for arrays the references are compared, not the
// contents of the arrays.
assertEquals (String message, T expectedValue, T actualValue)For example, if you just created an empty list, you might check that the list is actually empty by using the statement:
assertTrue ("List is not empty", 0, myList.size ());There are JUnit resources and tutorials linked on the course page if you are looking for more guidance.
You should thoroughly test the functionality of your SortedList class. Are lists created properly, are values added and kept in sorted order? Does find work? Remove? Test boundary conditions (empty lists, adding at the beginning and end of lists). Be sure to comment your JUnit code so that I know what you are intending to test.
Submit this as the SortedList lab on Autolab.
SortedList.java should be submitted to Lab 4.SortedListTest, should be submitted to Lab 4: JUnit.100 points total