为什么Java中的LinkedList最好使用foreach进行遍历

为什么Java中的LinkedList最好使用foreach进行遍历

• 问题描述
• • 测试代码
  • 测试结果
• 造成效率差异的原因
• • LinkedList中的get()方法
  • LinkedList中的node()方法
  • LinkedList中的迭代器方法
• 结论

问题描述

在查阅Java中for和foreach两种循环方式时，发现有文章提到对LinkedList进行遍历时，foreach循环的效率远高于for循环，于是写了一小段代码进行测试，测试代码和结果如下。

测试代码

public static void forLinkedListTest(){
    List<Long> array = new LinkedList<>();
    for (int i=0; i<100000; i++){
        Random r = new Random();
        long temp = r.nextLong();
        array.add(temp);
    }
    long time1 = System.currentTimeMillis();
    for (int i=0; i<array.size(); i++){
        System.out.println(array.get(i));
    }
    long time2 = System.currentTimeMillis();
    for (long I: array){
        System.out.println(I);
    }
    long time3 = System.currentTimeMillis();
    System.out.println("for循环用时：" + (time2-time1));
    System.out.println("foreach循环用时：" + (time3-time2));
}

测试结果

造成效率差异的原因

虽然已经知道了使用foreach循环遍历LinkedList效率更高，但是为了弄明白原理，所以查看源码试图找到造成这两种循环方式效率差异的原因。

LinkedList中的get()方法

查看LinkedList中的get()方法具体实现，代码如下：

发现get方法返回的是对应index下标的node节点的值，继续往下查看node方法。

LinkedList中的node()方法

代码如下：

发现该方法使用了二分查找，当index小于LinkedList长度一半时，从头往后搜索，当index大于LinkedList长度一半时，从后向前搜索。

LinkedList中的迭代器方法

在LinkedList中，接口ListIterator继承了Iterator，而类ListItr实现了ListIterator类，我们都知道Java中迭代器的两个基本 *** 作hasNext()和next()。

方法名	作用
hasNext()	用于检测集合中是否还有元素
next()	返回迭代器的下一个元素，并且更新迭代器的状态

查看LinkedList中这两个方法的具体实现，代码如下：

发现next()方法每次取值之后都会让next后移一位，这样遍历到下个元素时就可以继续向后移动指针，充分发挥了链表的优点。

结论

使用for循环遍历LinkedList时，每当下标i自增（变化）一次时，get(i)方法都要进行一次搜索，没有利用到链表自身的优势。
而使用foreach循环LinkedList，由于foreach底层使用Iterator实现，迭代器中的next()方法每次取值之后都会让next后移一位，这样遍历到下个元素时就可以继续向后移动指针，充分发挥了链表的优点，因此使用foreach循环迭代LinkedList比for循环效率更高。