java 为什么遍历LinkedList要使用迭代器/foreach?

在之前的文章中我们研究了一下LinkedList的数据结构,提到不应该使用for,而应该使用迭代器/foreach去遍历。为什么要这样做?原理是什么?

有这样一种说法:“foreach循环的原理就是迭代器”。是如何实现的?

参考:http://www.cnblogs.com/chenssy/p/3821328.html

 

一、为什么不应该使用for遍历LinkedList

(1)LinkedList的get方法效率低

这种做法存在问题,在上篇文章中也有提及:

java ArrayList和LinkedList的区别

LinkedList的get方法效率低是由链表的数据结构决定的。在查找指定位置的元素时,get方法会正序遍历/倒序遍历链表,依次把前面的数据获取一遍,所以速度比较慢。

如果使用for循环遍历链表获取元素,会放大这个问题,应该避免。

(2)为什么ArrayList不会遇到这个问题?

还记得ArrayList和LinkedList的数据结构吗?

LinkedList基于链表,不需要使用连续的内存空间(注意这里是“不需要”,实际上连续的内存空间也可以),其每个节点都保存上一个和下一个节点的地址,我们无法计算某个元素的准确位置,只能在查找的时候一个节点一个节点去找。

但是,ArrayList基于数组,使用的是“连续”(不是有序)的内存空间。因为内存空间是“连续”的,所以可以直接计算元素所在的位置,从而直接获取该位置的元素。

这就是为什么ArrayList不会遇到这个问题。

二、使用迭代器遍历LinkedList

Iterator接口也是Java集合框架的成员,但它与Collection系列、Map系列的集合不一样:Collection系列集合、Map系列集合主要用于装载其他对象,而Iterator则主要用于遍历(即迭代访问)Collection集合中的元素,Iterator对象也被称为迭代器。

这样使得对容器的遍历操作与其具体的底层实现相隔离,达到解耦的效果。

(1)怎么做?

Test.java

很常见的实现。

(2)迭代器如何实现遍历?

查看iterator方法的源码,发现一系列调用:

最后发现,具体逻辑是在Itr类中实现的。

主要看next方法:

可以发现,迭代器通过移动光标位置、读取所在位置的元素的方式对集合进行遍历。

重点为get方法:java.util.AbstractList.get(int index):

这里只是一个抽象方法(没有看到具体实现,感觉有点奇怪),作用是:Returns the element at the specified position in this list,返回所给位置的元素对象。

所以,使用迭代器遍历LinkedList时,使用next方法会直接获取指定位置的元素,而使用for方法则需要遍历链表中的元素,比前者效率更低。

(3)性能对比

Test.java

运行结果为:

在这个测试中差距比较明显,但是依然在可接受范围内。

三、foreach的实现

参考:http://blog.csdn.net/cq1982/article/details/49121879

之前看到这样一种说法:“foreach循环的原理就是迭代器”。很明显,从代码角度是看不出来什么,需要分析一下class文件,才能看出具体的实现。

foreach.java

javap一下:

666

可以发现,foreach的语法被编译器转换为Iterator的实现。

所以,我们使用foreach遍历LinkedList也是可行的,效率比for循环要好

四、总结

解决了之前的疑惑。

发表评论

电子邮件地址不会被公开。 必填项已用*标注