对于ArrayList遍历

我们平时对ArrayList的遍历通常采用两种方式，增强的for循环，和for i，但是哪种方式最适合ArrayList的遍历呢？

增强for 循环

现在对800w条数据进行循环遍历，求集合中的总和，这个算法还是比较简单的，现在看一下用增强for循环的耗时

        int count = 800_0000;
        List<Integer> list1 = new ArrayList<>(count);
        for (int i = 0; i <count; i++) {
            list1.add(new Random().nextInt(100));
        }

        int sum = 0;
        long start = System.currentTimeMillis();
        //采用增强for循环的形式
        for (Integer object : list1) {
            sum += object;
        }
        long cost = System.currentTimeMillis() - start;
        System.out.printf("使用for循环耗时：%d%n",cost);
1
2
3
4
5
6
7
8
9
10
11
12
13
14

通过上图可以看到，使用增强for循环的方式耗时是554毫秒。

for i 的循环方式

下面再使用for i的形式来进行遍历。

        int count = 800_0000;
        List<Integer> list1 = new ArrayList<>(count);
        for (int i = 0; i <count; i++) {
            list1.add(new Random().nextInt(100));
        }
        
        long l2 = System.currentTimeMillis();
        int sum2 = 0;
        //采用for i的形式
        for (int i = 0; i < count; i++) {
            sum2 += list1.get(i);
        }

        long cost2 = System.currentTimeMillis() - l2;
        System.out.println(System.out.printf("使用for i循环耗时：%d%n",cost2));
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

同样的数据，使用for i的形式才耗费399毫秒

原因分析

使用 for i 的形式为什么会比for循环的形式要快？
我们看一下ArrayList的源码，发现它实现了RandomAccess接口

我们可以看一下RandomAccess接口的说明，它是一个标记性的接口
注释上面也描述了使用for i 的效率要优于for循环。其意义就是为了告诉开发人员尽量使用下标的方式进行遍历。for i的形式是直接根据索引来取值，每个元素之间是没有任何关系的。而for循环则是使用了迭代器，也就是23个设计模式中的迭代器模式，它提供了hasNext、next等方法，也就是说每个元素并不是完全独立的，遍历的时候还需要知道下一个元素是否存在，所以就会有额外的开销。

对于LinkedList的遍历

对于ArrayList，for i的效率要优于增强for循环。而对于LinkedList来说是反过来的。LinkedList是一个双向列表，每一个数据结构有三部分组成：前节点的引用、本节点元素和后继节点的引用。也就是说在LinkedList中相邻的元素是知道彼此的存在的，所以使用for循环可以提高效率。而如果使用for i来get的话，则需要进行很多的计算，效率很低，下面是LinkedList和ArrayList的get方法的源码，大家可进行对比查看：

LinkedList的get方法中获取节点的源码：

    Node<E> node(int index) {
      
		//当前下标小于中间值，则从首开始遍历
        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
        //当前下标小于中间值，则从尾开始遍历
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

ArrayList中get方法的源码：

    E elementData(int index) {
    //直接返回数组的下标的元素
        return (E) elementData[index];
    }
1
2
3
4