CPSC 170 Lab 11: Sorted Lists

It is possible to enhance the efficiency of find operations on a list by using binary search. However, this requires restricting access to the location of data in the structure in order to maintain a sorted order.

Implementing a Sorted List

The file SortedArray.java contains the outline of an array based implementation of a sorted list. Notice that the generic type for the class extends Comparable. This means that only classes that implements Comparable can be used as the generic type for the SortedList class. This is necessary because it is not possible to sort objects unless they can be compared. There is also an ArrayList.java instance variable that stores the objects in the list in ascending order. The constructors and the toString methods are already completed, however, you must complete each of the following methods:

  1. The binarySearch method should return the index of the first occurrence of the specified object. If the object is not in the list, it should return where it would be added to the list. You can use the constructor that takes an array list of objects to test this method. Test thoroughly before proceeding. The following three methods should all use the binarySearch method.
  2. The add method should add the specified object to the sorted list, such that the list maintains its ascending order. If the object is null, it should throw an exception. Test thoroughly before proceeding.
  3. The get method should return the first object in the sorted list that is equivalent (according to the compareTo method) to the specified object. If there is no equivalent object in the list, it should return null. Thoroughly test before proceeding.
  4. The iterator method should return a new SortedListIterator that begins iterating over the sorted list at the first occurrence of an object equivalent to or greater than the specified object. Test thoroughly before submitting.

Submission

Submit a zip file of your code on the course Inquire site that uses your last names as the file name.