The best algorithms for manipulating random access lists (such as ArrayList)
can produce quadratic behavior when applied to sequential access lists (such
as LinkedList). For example, there are two algorithms for rotating a list.
One, based on swaps, runs very quickly on random access lists, but degenerates
to quadratic behavior on sequential access lists. An alternative algorithm,
based of reversals, runs in linear time for random or sequential access lists,
but is seven times slower than the swap algorithm on ArrayList. Many other
generic algorithms (include binary search and shuffle) have similar problems.

A marker interface would allow List implementations to indicate
that they support fast (generally constant time) random access. This would
allow generic algorithms to alter their behavior to provide good performance
when applied to either random or sequential access lists.