Homework #1 - ordered linked list

You are to modify the linked list code from class to ensure the list is always in ascending order. You do not need to sort the data. You must make sure the data is in sorted order at all times by modifying any of the methods which modify the list.

In order to keep the items in order, the first thing you need to change is the ListNode class' element field type from Object to Comparable. This change will ensure that all the objects which can be legally stored in the list can be compared using the compareTo() method.

You should also change certain methods like find() to take advantage of the fact that the list is in sorted order. In other words, you do not need to search the entire list anymore to figure out if an element is in the list.

Also, add a method called public int findPosition (Comparable o) which will return object o's position in the list. If the object is not found in the list, you should return -1. Again, take advantage of the list's order when thinking about the moment we know the object is not in the list. The first non-header item in the list should be considered item #1.

Include in your submission the new Big-Oh for insertion, deletion, find and findPosition.

Note: This list will be a regular linked list. You do NOT need to make a doubly linked list.