Why is there no RandomAccess in the list hierarchy?

Question

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

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

I need to pass this method either an anonymous list, or a list with the declared type ArrayList<E> , a specific class, and not a list declared using some interface, for example List<E> . However, if RandomAccess was parameterized and extended with List<E> , then my method might look like this:

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

and I could pass it a list with the declared type RandomAccess<E> , which is an interface, not a concrete class. ArrayList<E> etc. then it will implement RandomAccess<E> , not List<E> .

Answer 1

I think the answer may be in the RandomAccess documentation (my emphasis).

The token interface used by the List implementation to indicate that they support fast (usually constant) random access. The main purpose of this interface is to allow universal algorithms to change their behavior in order to provide good performance when applied to random or sequential access lists.

The best algorithms for manipulating random access lists (e.g. ArrayList ) can create quadratic behavior when applied to sequential access lists (e.g. LinkedList ). General list algorithms are recommended to check whether a given instanceof this list is an interface before applying an algorithm that would provide poor performance if it were applied to a sequential access list, and change their behavior if necessary to ensure acceptable performance.

It seems that they were not going to add the additional complexity of the hierarchy of collection classes, but offered the possibility of optimization for algorithms.

That makes sense to me. The user of the algorithm usually does not need implementation details. Each algorithm that works on a List implementation of RandomAccess will also work with a List that will not. The only difference is performance.

Consider the following cases:

• It is not possible to rewrite an algorithm that is more efficient for List , which does not provide efficient random access. (Or no one felt like doing it.) In this case, it would probably be better to have a slow algorithm than not at all. If the user needs the algorithm often, he should switch to another implementation of List .
• The algorithm can be rewritten in two different ways, each of which gives better performance for List , which do and do not support efficient random access. Here the user usually prefers to simply enter List and the algorithm determines which version to use. If overload resolution was used instead of checking the runtime, the user might accidentally skip the optimized version when dealing with the abstract type List . Checking that the caller checks each time whether the List is an instanceof RandomAccess , the code is placed more than once in the algorithm itself. Finally, if subsequently the algorithm improves to support two versions, we do not need to go and change the client code.

Therefore, I think that they did it the way they did to actively discourage the use of the interface, the way you want to use it. Of course, there will likely be legal uses that are negatively affected by this choice, but it seems like a reasonable compromise.

Answer 2

Because List precedes RandomAccess several versions.

The List interface was introduced in 1.2, and RandomAccess not added until 1.4 (when the Java Collections Framework was introduced). Instead of going back and changing all existing lists in the world, they simply added a marker interface.

For more information on design solutions, see the FAQ .

Answer 3

Since List can be a linked list, and a linked list does not provide fast random access. (Access to the kth element takes O (k) time, and “fast” means constant time.)