Sorted Lists

• A sorted list is a list in which the objects are stored in order. This means that if the client code iterates through the list, the items will be returned in order.
• The add and remove methods ensure that the objects are in order.
• Indexed operations cannot be supported if they could disrupt the list order. This includes the following methods:
  1. add(int index, T element)
  2. set(int index, T newElement)
• Sorted lists can be implemented with arrays or using links.
• The order of the items is determined by the class T which is in the list. There are two ways a class can provide a comparison operation to the add method; this will be discussed below.

List Interface

The sorted list methods keep the list items in order. Our list interface contains several methods that could disrupt the order of the list. One alternative is to use a different interface that doesn't include these operations. Another alternative is to use the same interface, which means these operations must be included in the class. This is the approach taken in our sorted list. These operations are written to throw an UnsupportedOperationException if the method is called.

SortedABList: Sorted Array Based List

The fields of the array based list are very similar to the fields of the ABList. There is no field for the original capacity because it is always the same; there is no option to set the original capacity.

  protected final int DEFCAP = 100; // default capacity
  protected T[] list;               // array to hold list’s elements
  protected int numElements = 0;    // number of elements in this list

List Representation Practice

Suppose we have

SortedABList<String> myStrings = new SortedABList();

Draw the list (the fields list and numElements) after each of the following, and show any return value or output:

myStrings.add("spring");
myStrings.add("bloom");
myStrings.add("red");
myStrings.add("flowers");
myStrings.add("yellow");
boolean ok = myStrings.remove("red");
ok = myStrings.remove("blue");

Find Method

The find method is called by add, remove, get, contains, and indexOf. In the unsorted list, the find method performs a linear search, because the items in the list are not ordered, so there is no alternative. However, now the items in the list are sorted, so a binary search can be used. This is the approach used in the find method in the SortedABList class.

Comparing Objects

Comparable

The sorted list classes need to compare the objects in the list so that they can be put in order. This means that the class T (the class of objects contained in the list) has to provide a method for comparison. This method is called by the add method of the sorted list.

We know how to create objects that can be compared by implementing the Comparable<T> interface. This requires the class to have a method int compareTo(T obj). The compareTo method returns

• a negative number if this is less than the parm
• zero if this equals the parm
• a positive number if this is greater than the parm

The compareTo method is called with two objects, ob1 and ob2, of type T:

     if (ob1.compareTo(ob2) < 0)

Each Comparable class contains its own compareTo method. The compareTo method in the String class uses lexicographic (dictionary) order. In a class like Person we might use social security number, or last name and first name. In our class exercise we used first and last name. There can only be one compareTo method. The order created by the compareTo method is called the "natural order".

Comparator

Sometimes we may want to put objects in a different order. This can be done with the Comparator<T> interface. The Comparator<T> interface specifies that the class has a compare method:

     if (compare(ob1, ob2) == 0)

The Comparator approach means that the class T creates and returns an object that implements the Comparator interface. Class T can have multiple methods that return Comparators to compare objects in different ways. This is similar to how the list class creates and returns an object that implements the Iterator interface. For example, suppose we want to create different ways to compare Student objects. If we want to evaluate students for the Dean's List, or for academic awards, we need to order them by gpa. If we want to evaluate students for graduation, we need to order them by the number of credits completed. For each of these we create a static method in the Student class that returns a Comparator object. Each of these methods creates and returns an object which is an instance of an anonymous inner class:

   public static Comparator<Student> gpaComparator() {
      return new Comparator<Student>() {
         public int compare(Student st1, Student st2) {
            if (st1.gpa > st2.gpa)
               return 1;
            else if (st1.gpa < st2.gpa)
               return -1;
            else return 0;
         }
      };
   }


   public static Comparator<Student> creditComparator() {
      return new Comparator<Student>() {
         public int compare(Student st1, Student st2) {
            return st1.credits - st2.credits;
         }
      };
   }

Why is the method static? It is a member of the Student class but it is not called with a Student object before the .; it is called to create a Comparator for the Student class.

Using the Comparator

Once we have created compare methods for a class, we need to specify which compare method should be used by the sorted list. This is done when creating the sorted list: the Comparator object is passed to the constructor when the list is created and is stored in a field of the sorted list:

   protected Comparator<T> comp;

Here is the constructor of the sorted list that accepts a Comparator:

  public SortedABList(Comparator<T> comp)
  {
    list = (T[]) new Object[DEFCAP];
    this.comp = comp;
  }

and here's how you call it:

   SortedABList<Student> students
             = new SortedABList<Student>(Student.gpaComparator());

This calls the static gpaComparator method. It returns a Comparator object that contains a compare method that compares two student objects based on the gpa field. This Comparator object is stored in the comp method of the sorted list. The comp object is used in the find method of the list, to compare the list objects:

   result = comp.compare(target, list[location]) > 0;

Classes with Comparable not Comparator

If a class is Comparable, but doesn't provide a Comparator, it can still be used in a sorted list. The sorted list uses the compareTo method to create a Comparator for the add method to use. This is done in the default constructor:

   public SortedABList() {
   // Precondition: T implements Comparable
      list = (T[]) new Object[DEFCAP];
      comp = new Comparator<T>() {
         public int compare(T element1, T element2) {
            return ((Comparable)element1).compareTo(element2);
         } // end of compare method
      }; // end of inner class and assign statement for comp
   }

Summary

• The find method of sorted list calls a compare method that compares two objects of type T. This compare method is called by the find method. The find method locates an element in the list, or finds the location where the element should be added to maintain the sorted order of the list.
• There are two ways for class T to provide this compare method.
• Class T has a method that creates and returns a Comparator object, which contains the compare method. The Comparator object is passed to the sorted list constructor and stored in a field of the list.
• Class T is Comparable, and thus has a compareTo method. The default constructor of the sorted list uses compareTo method to create a Comparator object and its compare method.

Complexity

Look at the code for the SortedABList methods. For each of the following methods, consider a SortedABList containing N elements. What is the best case and worst case? Count the number of times each statement executes as a function of N, then get the big O.

add(T element)

remove(int index)

remove (T target)

get(int index)

get(T target)

Email Me | Office Hours | My Home Page | Department Home | MCC Home Page

© Copyright Emmi Schatz 2017