When does algorithms for manipulating random access lists is applied?

Question

In RandomAccess marker interface description it is written :

 * <p>The best algorithms for manipulating random access lists (such as
 * <tt>ArrayList</tt>) can produce quadratic behavior when applied to
 * sequential access lists (such as <tt>LinkedList</tt>).  Generic list
 * algorithms are encouraged to check whether the given list is an
 * <tt>instanceof</tt> 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.

In collection class synchronisedList method there is a check for RandomAccess & if success create SynchronizedRandomAccessList object but their also no details regarding algorithm.

public static <T> List<T> synchronizedList(List<T> list) {
    return (list instanceof RandomAccess ?
                new SynchronizedRandomAccessList<T>(list) :
                new SynchronizedList<T>(list));
    }

When does this algorithm apply and where(is it a native code) ?

Answer 1

One of the examples is Collections.binarySearch:

public static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key) {
    if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
        return Collections.indexedBinarySearch(list, key);
    else
        return Collections.iteratorBinarySearch(list, key);
}

Here different binary search algorithm implementations are used for random access and sequential access lists. Code is an implementation detail, but it's reasonable to differentiate lists here.

As specified in documenation for Collections.binarySearch:

This method runs in log(n) time for a "random access" list (which provides near-constant-time positional access). If the specified list does not implement the RandomAccess interface and is large, this method will do an iterator-based binary search that performs O(n) link traversals and O(log n) element comparisons.