什么时候应用了处理随机访问列表的算法？

Question

在RandomAccess标记接口描述中写入:

 * <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.

在集合类synchronisedList方法中,检查RandomAccess&如果成功创建SynchronizedRandomAccessList对象,但它们也没有关于算法的细节.

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

该算法何时适用？何处(是本机代码)？

Answer 1

其中一个例子是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);
}

这里，不同的二分搜索算法实现用于随机访问和顺序访问列表。代码是实现细节，但在这里区分列表是合理的。

正如Collections.binarySearch 文档中所指定的：

此方法在 log(n) 时间内运行“随机访问”列表（提供接近恒定时间的位置访问）。如果指定的列表未实现 RandomAccess 接口并且很大，则此方法将执行基于迭代器的二分搜索，执行 O(n) 链接遍历和 O(log n) 元素比较。