1.概述

转载：http://www.javastack.cn/article/2019/why-arraylist-impl-randomaccess-interface/

在我们的开发中，List接口是最常见不过，而且我们几乎每天都在用ArrayList或者LinkedList，但是细心的同学有没有发现，ArrayList中实现了RandomAccess接口，而LinkedList却没有实现

RandomAccess接口，这是为什么呢？

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable { private static final long serialVersionUID = 8683452581122892189L;

RandomAccess接口中是空的，RandomAccess接口又是什么呢？

public interface RandomAccess { }

RandomAccess接口

RandomAccess是一个标记接口，官方解释是只要List实现这个接口，就能支持快速随机访问。而什么是随机访问呢？

接下来我们来举例说明。

Collections是集合的一个工具类，我们看一下Collections源码中的二分搜索方法。

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的实例，如果是，则执行indexedBinarySearch方法，如果不是，则执行iteratorBinarySearch方法。接下来看一下这两个方法。

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 }

iteratorBinarySearch 方法

private static <T> int iteratorBinarySearch(List<? extends Comparable<? super T>> list, T key) { int low = 0; int high = list.size()-1; ListIterator<? extends Comparable<? super T>> i = list.listIterator(); while (low <= high) { int mid = (low + high) >>> 1; Comparable<? super T> midVal = get(i, 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 }

上述两个方法的源码表示，实现了RandomAccess接口的List使用索引遍历，而未实现RandomAccess接口的List使用迭代器遍历。

那么为什么要这么设计呢？

既然涉及到二分搜索的遍历操作，那么现在我们来分析一下ArrayList和LinkedList遍历元素的性能如何？

测试结果如下测试ArrayList通过for遍历所消耗时间：1

测试ArrayList通过iterator遍历所消耗时间：2

测试LinkedList通过for遍历所消耗时间：47

测试LinkedList通过iterator遍历所消耗时间：1

我们来分析一下测试结果：ArrayList通过for遍历比通过iterator遍历要稍快，LinkedList通过iterator遍历比通过for遍历要快。

所以说在我们的应用中，要考虑使用List接口的哪种实现类，可以更好更高效的满足实际场景需求。所以在这里通过实现RandomAccess接口来区分List的哪种实现类。

总结

最后总结一句话：实现RandomAccess接口的List可以通过for循环来遍历数据比使用iterator遍历数据更高效，未实现RandomAccess接口的List可以通过iterator遍历数据比使用for循环来遍历数据更高效。