Run Selection Sort on LinkedList

In Chapters 1 and 2, we developed an ArrayUtils class that provides a few static methods for working with arrays, including the selectionSort method (re-written to be self-contained rather than calling indexOfMin and swap):

public static <T extends Comparable<T>> void selectionSort(DynamicArray<T> list) {
  for (int i = 0; i < list.size() - 1; i++) {
    // find the index of the minimum element in list[i..list.size()-1]
    int minIndex = i;
    for (int j = i + 1; j < list.size(); j++) {
      if (list.get(j).compareTo(list.get(minIndex)) < 0) {
        minIndex = j;
      }
    }
    // swap list[i] and list[minIndex]
    T temp = list.get(i);
    list.set(i, list.get(minIndex));
    list.set(minIndex, temp);
  }
}

This selectionSort works on our DynamicArray class. What does it take to adapt it for the LinkedList class?

The selection sort calls three operations on the list: size(), get(i), and set(i, x). The LinkedList class has all three of those methods, with the same signatures and the same meanings. So the body of the method does not have to change at all. The only thing that has to change is the type written in the parameter list:

public static <T extends Comparable<T>> void selectionSort(LinkedList<T> list) {
  // same implementation as before
}

So now we have two copies of selectionSort. The bodies are identical, line for line. That is a violation of the DRY principle: Don’t Repeat Yourself. It is the same kind of problem we had when we made DynamicArray generic. In that case the code across different versions of DynamicArray would differ only in the type of the element, and a generic type parameter fixed it. In this case the duplicates differ only in the type of the list.

There is a fix for this one too. It is called type substitution: using a value of a subtype where a value of a supertype is expected. Type substitution comes from interfaces and polymorphism. Those are the same tools that let unrelated classes share one contract. I assume you learned about interfaces and polymorphism in your first programming course. If you need a refresher, read my blog post An Employee Type Hierarchy in Java.