ArrayList与LinkedList的循环效率对比

问题来源

for循环遍历存在这两种方式，如下所示：

for (int i = 0; i < objects.length; i++);
for (Object object: objects);

ArrayList与LinkedList两种集合在两种方式的遍历存在着较大的性能差距，下面将以以下测试代码作为范例解释：

public class ForTest {
    private static final int NUM_SIZE = 2000000;

    public static void testList(List<Integer> list) {
        long start = System.currentTimeMillis();
        for (int i = 0; i < list.size(); i++) {
            list.get(i);
        }
        System.out.println(list.getClass().getSimpleName() + "-普通for-花费时间: " + (System.currentTimeMillis() - start) + "ms");

        start = System.currentTimeMillis();
        for (Integer num: list) {

        }
        System.out.println(list.getClass().getSimpleName() + "-foreach-花费时间: " + (System.currentTimeMillis() - start) + "ms");
    }

    public static void main(String[] args) {
        List<Integer> arrayNums = new ArrayList<>();
        List<Integer> linkNums = new LinkedList<>();

        for (int i = 0; i < NUM_SIZE; i++) {
            arrayNums.add(i);
            linkNums.add(i);
        }

        testList(arrayNums);
        testList(linkNums);
    }
}

测试运行结果可得：

ArrayList-普通for-花费时间: 5ms
ArrayList-foreach-花费时间: 7ms
LinkedList-普通for-花费时间: 32459ms
LinkedList-foreach-花费时间: 9ms

从上述的结果中，可以看出ArrayList在普通for循环上更胜一筹，而在LinkedList在foreach上效率极高。倘若数据量不断上升，那么这个差距只会不断加大。

那么为什么会造成上述情况发生呢？

问题解释

问题可以从两者的结构体系上分析。

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

在两者对比中，我们可以发现ArrayList中实现了RandomAccess接口，而LinkedList没有实现。仔细查看RandomAccess的注释解释，如果实现该接口的List，在普通for循环遍历的效率上会快于foreach循环。

/**
 * Marker interface used by <tt>List</tt> implementations to indicate that
 * they support fast (generally constant time) random access.  The primary
 * purpose of this interface is to allow generic algorithms to alter their
 * behavior to provide good performance when applied to either random or
 * sequential access lists.
 * List实现所使用的标记接口，用来表明实现了这个接口的list支持快速随机访问(通常在常数时
 * 间内)。这个接口主要目的在于允许一般的算法更改它们的行为，以便在随机或者顺序访问list
 * 时有更好的性能。
 *
 * <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.
 * 操作随机访问列表(如ArrayList)的最佳算法在顺序访问列表(如LinkedList)上应用，会产
 * 生歧义行为。泛型列表的算法鼓励在将某个算法应用于顺序访问列表可能产生较差的性能之前，
 * 检查给定的列表是不是这个接口的实现，并在有必要的时候修改它们的行为，以保证提供可接受
 * 的性能。
 *
 * <p>It is recognized that the distinction between random and sequential
 * access is often fuzzy.  For example, some <tt>List</tt> implementations
 * provide asymptotically linear access times if they get huge, but constant
 * access times in practice.  Such a <tt>List</tt> implementation
 * should generally implement this interface.  As a rule of thumb, a
 * <tt>List</tt> implementation should implement this interface if,
 * for typical instances of the class, this loop:
 * 在界定随机访问与顺序访问的界限一般都是模糊不清的。例如，某些列表在它们拥有大量的数据
 * 时提供非线性访问时间，但实际上是常量级别的访问时间。这样的接口应该实现该接口。
 * <pre>
 *     for (int i=0, n=list.size(); i &lt; n; i++)
 *         list.get(i);
 * </pre>
 * runs faster than this loop:
 * 比下面的循环运行速度更快。
 * <pre>
 *     for (Iterator i=list.iterator(); i.hasNext(); )
 *         i.next();
 * </pre>
 */
public interface RandomAccess {
}

---

参考资料

Java集合干货系列-（二）LinkedList源码解析