CSC148 - Lab 2
Sorted Lists
Download sortedlist.py and node.py. Currently, the class SortedList does not live up to its name. SortedList.insert inserts all elements to the end of a linked list.
Modify the insert method such that it inserts values in sorted order. That is for ever node x in the linked list, x.data <= x.next.data (assuming x.next is not None). Inserting a duplicate value into the list is fine; the list can contain duplicates.
Write some nose tests for this method that cover at least the following cases:
- Inserting into an empty list.
- Inserting into the front of a non-empty list.
- Inserting into the back of a non-empty list.
- Inserting into the middle of a list.
- Inserting a duplicate of the first, last, and middle elements.
Remember that when a test succeeds, it should print nothing (nose will take care of that). A successful test is one which does not raise eny exceptions. To cause a test to fail, you simply need to raise an exception without catching it with a try-except block. Using the assert statement is extremely useful. Most of your tests should be based around check the return value of a function is waht you expected. This can be accomplished using the following format:
assert function_call() == correct_return_value, 'function_call did not return correct_return_value'
For more examples of writing tests, take a look at the starter code from last weeks lab here.
Next, look at remove. Currently this searches the entire list for value, and removes the first one it finds. Modify remove so that all occurrences of value, and also stops searching for value once current.data > value.
Write some more tests for remove. You should cover at least the following cases:
- Removing the only value in a list of size 1.
- Remove the first and last elements.
- Both of the above cases, with the element you wish to remove duplicated.
- Removing an element not in the list (also decide what should remove do in this case?)