Geek asks and answers

When are algorithms used to manage random access lists?

The description of the RandomAccess marker interface says:

 * <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 the synchronizedList method of the collection class, there is a check for RandomAccess, and if success creates a SynchronizedRandomAccessList object, but also does not contain details about the algorithm.

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

When is this algorithm applied and where (is this native code)?

+5
source share
1 answer

One example 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 various implementations of the binary search algorithm are used for access lists and sequential access. Code is an implementation detail, but it makes sense to distinguish between lists.

As stated in the documenation for Collections.binarySearch :

log (n) " " ( ). RandomAccess , , O (n) O (log n).

+4

More articles:


All Articles