Implementing a List Interface

We can now create a type hierarchy for our list classes.

                   ┌──────────────────┐
                   │     List<T>      │
                   └──────────────────┘
                     △             △
                     │             │
           ┌─────────┘             └─────────┐
           │                                 │
  ┌──────────────────┐              ┌──────────────────┐
  │ DynamicArray<T>  │              │   LinkedList<T>  │
  └──────────────────┘              └──────────────────┘

This is essentially inheritance, but it is not the same as class inheritance. DynamicArray and LinkedList are not subclasses of List, because List is not a class. Instead, they implement the List interface, which means they promise to provide a body for every method in the interface. To do that, we make two changes to each class:

1. Update the class declaration to say implements List<T>.

   public class DynamicArray<T> implements List<T> { ... }
   public class LinkedList<T> implements List<T> { ... }
   

2. Add @Override to each method that implements a method from the interface.

   @Override
   public void add(T element) { ... }
   

Now we can update our selectionSort method to take a List<T> parameter instead of a DynamicArray<T> parameter. The body of the method does not change, because it only uses the operations in the interface.

public static <T extends Comparable<T>> void selectionSort(List<T> list) {
  for (int i = 0; i < list.size() - 1; i++) {
    int minIndex = i;
    for (int j = i + 1; j < list.size(); j++) {
      if (list.get(j).compareTo(list.get(minIndex)) < 0) {
        minIndex = j;
      }
    }
    T temp = list.get(i);
    list.set(i, list.get(minIndex));
    list.set(minIndex, temp);
  }
}

Because the parameter is a List<T>, this one method now sorts either kind of list:

List<Integer> a = new DynamicArray<>();
List<Integer> b = new LinkedList<>();
// ... fill both ...

selectionSort(a);  // sorts a DynamicArray
selectionSort(b);  // sorts a LinkedList

This works because of type substitution. Anywhere our code expects a List<T>, we should be able to pass it a DynamicArray or a LinkedList. This works for any type hierarchy: you can substitute a subtype for a supertype.

At runtime, the selectionSort method does not check whether it is sorting a DynamicArray or a LinkedList. It calls the methods in the interface, and each call runs the implementation in the class of the object it is called on. This is called dynamic dispatch: the program chooses which implementation to run based on the instantiated type of the object.