JAVA 中 LinkedList 使用 iterator 遍历的效率问题

看视频中介绍 java.util.LinkedList 提到使用 iterator 对LinkedList 进行遍历时效率高。一开始没想通,毕竟 LinkedList 本质上就是一个链表,那么无论如何,想取在位置 i 上的链表元素,肯定要从头遍历过去,那么 for 从 1 到 i 和使用 iterator 从 1 到 i 应该并没有什么效率上的差别才对。一开始总以为是 iterator 用了什么黑科技,跑去看了 iterator 的源码,就是一个cursor 从头开始的遍历,理论上应该是一样才对。然而结果确实是 iterator 的效率要高很多。最后试着从 for 循环遍历的角度去看,发现了问题所在。

在 for 循环的遍历中,取到具体某个元素要调用 LinkedList 的 get() 方法,而在 get() 实现时,其实又利用 index 去做了一次 for 循环。相当于 for 循环的时间复杂度为

(1)   \begin{equation*}O(n^2)\end{equation*}

,而 iterator 的时间复杂度是

(2)   \begin{equation*}O(n)\end{equation*}

,因此说 iterator 对 LinkedList 的遍历有着更高的效率。

发表评论

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

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>