Why methods like sort in Collections class are not in List interface?

Question

Class Collections has some static methods as utilities to manipulate collections like List. For example the sort method (Collections.sort(list)). I do not understand why Java specs made another class to host the sort method (and all the others like binarySearch) and not to List interface and concrete subclasses like ArrayList and LinkedList implement these methods.

UPDATED

As I made a global research and read the answers from this post I have to say that (bird's eye view): Some people (I mention @dan,@WJS,@cdalxndr) said in this post, using the sort method as example, that because the sort of ArrayList and LinkedList can be done with the same way then we can implemented writing only one time. So (I say) we could put the code in the List interface but until Java 7 we couldn't put any implementation in interface's body and the only way to write it one time was to implemented in utility class. But since Java 8 interfaces has the feature of "default" method. And Java team took advantage of this feature to have sort method implementation in interface level and that method can be used by ArrayList and LinkedList (as default if the classes do not override it)

Answer 1

Sorting is an algorithm, and List is a container.

The developers wanted to separate list algorithms (sort, binary search, etc) from container logic (add, remove, etc) so they put the algorithms to the utility class Collections.

Answer 2

Before Java 8, interfaces could not have default nor static methods, hence, every method added to the interface needed to be implemented by all classes implementing the interface. Even when you provided a helpful implementation in a support class, the implementing class needed at least a delegating method.

So, unless you wanted to force all implementations to inherit from some abstract base class providing those methods, you had to be careful with what you add to the interface.

Even with the default methods, you have to be careful, to avoid polluting the name space of an implementing class with too many methods. This might also be the reason why not every operation has been retrofitted to default methods in Java 8:

While adding a default method to an interface is less intrusive, as it does not create the need to implement it in already existing implementation classes, it may still cause a clash with a concrete method of the implementation class that didn’t implement an interface method in the previous version.

Just imagine a custom List implementation in pre-Java 8 times that provided a helpful void sort(Comparator c) instance method just delegating to Collections.sort(this, c);. That worked before Java 8, not improving the performance, but allowing to write list.sort(c);. Nowadays, this method would unintentionally happen to override the default method with the same name and type, to which Collections.sort will delegate, producing an infinite loop (or rather, recursion).

Still, the sort method has been added to the List interface, because of the immediate benefits. Unlike the static methods in the Collections utility class, the default method can be overridden. This has been done for the most commonly used list types, ArrayList, Vector, and the implementation returned by Array.asList(…). Since all those implementations are backed by an array, the overriding method can delegate to Arrays.sort using the backing array directly, whereas the default implementation will work with a temporary copy of the list contents.

It’s also worth noting that those methods in Collections seem to be originally based on the assumption that those algorithms were suitable to all kind of implementations, which didn’t hold. Two releases after the introduction of the Collection API, the RandomAccess marker interface was introduced, to tell two fundamentally different list implementation categories apart, so the static method could branch to two alternative algorithms based on it.

Whenever we have to branch based on the class we’re operating on, we could question the abstraction and say that we might be better off with overridable methods on the type itself, but as explained above, there are historical reasons for the design and there still are reasons to be careful with adding methods to the interface.

Answer 3

There is sort of an option since Java 8, just requires you to define (or use predefined comparator).

Dummy example below:

    List<Integer> list = new ArrayList();
    list.addAll(List.of(1,5,4,3,6,8,9,2));

    list.sort(Comparator.naturalOrder());

But obviously it is not done the same way to you as an user as it is in Collections util (although I do believe that Collections implementation also wraps around using such comparator or something like it).

Answer 4

Because it isn't necessary. All the following extend Collection

BeanContext, BeanContextServices, BlockingDeque<E>, BlockingQueue<E>,<br>
Deque<E>, EventSet, List<E>, NavigableSet<E>, Queue<E>, Set<E>,<br>
SortedSet<E>, TransferQueue<E>

So what you are advocating is that each interface provide the exact same implementation or perhaps a convenience method to each method in Collections. That would be, imho, a form of code bloat. In the former case, it would require changing multiple implementations if improvements were discovered.

I know they added sort to the List interface, perhaps because it is such a common requirement. But I never had a problem using Collections.sort to do sorting. There may be other reasons of which I am unaware.

But I tend to think of Collections as very similar to the Math class. Double and Integer don't have duplicate math functions. Similar to Math, Collections is a utility that offers a variety of static methods that are usable by related classes. Granted, the Math class is not in the Double or Integer, etc hierarchy, but its use is very similar.

Answer 5

The designers of the Collections Framework (primarily Josh Bloch while working at Sun Microsystems), as with many other sections of the Java API, had an eye to the longevity of the language. Java incorporates the notion of sustainment and evolution of APIs directly into the syntax supported by the documentation with the @deprecated tag. Specifically, they anticipated additional sorting and searching algorithms would likely be developed over the years long before additional "container" operations would be discovered to add to the Collection, and List interfaces.

They knew very well changes to the interfaces would impose upgrade requirements on development teams to deal with. Upgrade requirements slows the adoption of fixes and improvements that Sun Microsystems wanted teams to be able to absorb with ease. Incorporating new methods for sorting and searching into the interface would greatly impede that goal; placing an unnecessary burden on teams choosing to upgrade to the latest version of the Java language. Instead, they wisely chose to shunt these utility methods to a static utility class.

As with Java 8's List.sort(..), I can only guess Oracle felt the pressures of the industry and other languages incorporating these common operations right into their collection itself. However, keeping these utilities separate from the collection minimizes adoption requirements they would impose on those who directly implement their interfaces.