ArrayList 和 LinkList 的区别

ArrayList 的相关知识

public class ArrayList<E> extends AbstractList<E>implements List<E>, RandomAccess, Cloneable, java.io.Serializable

 由上面源码可知，Arraylist继承自AbstractList 实现了List ,Cloneable,Serializable，RandomAccess接口.其中Cloneable是克隆接口，Serializable是实现序列化操作的接口，便于对象的传输。而今天重点要描述一下这个RandomAccess。

 RandomAccess接口是一个标记接口，实现了它的list集合支持随机访问，目的是是算法在随机和随机访问时显得更灵活。在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);
}

我们可以看到，他首先会判断这个list是否实现了RandomAccess接口，如果这个条件和list.size()<BINARYSEARCH_THRESHOLD(其中: BINARYSEARCH_THRESHOLD Collections的一个常量（5000），它是二分查找的阀值。)满足其中任何一个则使用Collections的indexedBinarySearch(list,key)方法。否则会调用Collections.iteratorBinarySearch(list,key)方法。

  这两者的代码实现分别如下：

indexedBinarySearch 方法:

 

private static <T>
    int indexedBinarySearch(List<? extends Comparable<? super T>> list, T key) {
        int low = 0;
        int high = list.size()-1;

        while (low <= high) {
            int mid = (low + high) >>> 1;
            Comparable<? super T> midVal = list.get(mid);
            int cmp = midVal.compareTo(key);

            if (cmp < 0)
                low = mid + 1;
            else if (cmp > 0)
                high = mid - 1;
            else
                return mid; // key found
        }
        return -(low + 1);  // key not found
    }