Why isn't RandomAccess in the List hierarchy?

Question

RandomAccess is a marker interface in Java used by List implementations to indicate they have fast random access to their elements. Since it is designed specifically for List implementations, why is not in the List hierarchy? For example, consider the following method that requires a RandomAccess list as input and returns a random element:

public <E, L extends List<E> & RandomAccess> E getRandomElement(L list) {...}

I must pass this method either an anonymous list or a list with declared type ArrayList<E>, a concrete class, rather than a list declared with some interface like List<E>. However, if RandomAccess was parameterized and extended List<E>, then my method could look like:

public <E, L extends RandomAccess<E>> E getRandomElement(L list) {...}

and I could pass it a list with declared type RandomAccess<E>, which is an interface, rather than a concrete class. ArrayList<E> etc would just then implement RandomAccess<E>, rather than List<E>.

Answer 1

I think the answer might be in the documentation of RandomAccess (emphasis mine).

Marker interface used by List implementations to indicate that they support fast (generally constant time) random access. The primary purpose of this interface is to allow generic algorithms to alter their behavior to provide good performance when applied to either random or sequential access lists.

The best algorithms for manipulating random access lists (such as ArrayList) can produce quadratic behavior when applied to sequential access lists (such as LinkedList). Generic list algorithms are encouraged to check whether the given list is an instanceof this interface before applying an algorithm that would provide poor performance if it were applied to a sequential access list, and to alter their behavior if necessary to guarantee acceptable performance.

It seems that they did not intend to add additional complexity to the collections class hierarchy but only offer an optimization opportunity to algorithms.

This does make some sense to me. The user of an algorithm generally does not need to be concerned with implementation details. Every algorithm that works on a List implementing RandomAccess will also work on a List that does not do so. The only difference is performance.

Consider the following cases:

• There is no way to re-write an algorithm to be more efficient for Lists that do not provide efficient random access. (Or nobody felt like doing so yet.) In this case, it will probably still be better to have a slow algorithm than none at all. If the user needs the algorithm frequently, it should switch to a different List implementation.
• The algorithm can be re-written in two slightly different ways that each yield best performance for Lists that do and do not support efficient random access. Here, the user would generally prefer to simply put in the List and have the algorithm decide what version to use. If overload resolution were used instead of run-time type introspection, a user might accidentally miss the optimized version if dealing with an abstract List type. Having the caller check every time whether the List is an instanceof RandomAccess litters the code more than doing it once in the algorithm itself. Finally, if an algorithm is later improved to support two versions, we need not go and alter client code.

Therefore, I think they did it they way they did it to actively prevent the interface being used as you wish to use it. Of course, there will probably be legitimate uses that are negatively affected by this choice but it seems like a reasonable trade-off.