- 问题描述
- 测试代码
- 测试结果
- 造成效率差异的原因
- LinkedList中的get()方法
- LinkedList中的node()方法
- LinkedList中的迭代器方法
- 结论
在查阅Java中for和foreach两种循环方式时，发现有文章提到对LinkedList进行遍历时，foreach循环的效率远高于for循环，于是写了一小段代码进行测试，测试代码和结果如下。
测试代码public static void forLinkedListTest(){
List 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
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中，接口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循环效率更高。
