为什么迭代List会比索引更快?

问题

阅读theJava documentation for the ADT Listit说:

List接口提供了四种对列表元素进行位置(索引)访问的方法。列表(如Java数组)基于零。注意,对于某些实现(例如,LinkedList类),这些操作可以与索引值成比例地执行。因此,如果调用者不知道实现,则迭代列表中的元素通常优选通过它进行索引。

这到底是什么意思?我不明白得出的结论。


#1 热门回答(208 赞)

在链表中,每个元素都有一个指向下一个元素的指针:

head -> item1 -> item2 -> item3 -> etc.

要访问item3,你可以清楚地看到,你需要从头部穿过每个节点,直到到达item3,因为你无法直接跳转。

因此,如果我想打印每个元素的值,如果我写这个:

for(int i = 0; i < 4; i++) {
    System.out.println(list.get(i));
}

会发生什么事:

head -> print head
head -> item1 -> print item1
head -> item1 -> item2 -> print item2
head -> item1 -> item2 -> item3 print item3

这是非常低效因为每次你编制索引时它会从列表的开头重新开始并遍历每个项目。这意味着你的复杂性实际上只能遍历列表!

如果相反我做了这个:

for(String s: list) {
    System.out.println(s);
}

然后会发生什么:

head -> print head -> item1 -> print item1 -> item2 -> print item2 etc.

所有在一次遍历中,即O(N)

现在,转到其他实现的List,即ArrayList,其中一个由简单数组支持。在这种情况下,上述两个遍历都是等效的,因为一个数组是连续的,所以它允许随机跳转到任意位置。


#2 热门回答(35 赞)

答案在这里暗示:

请注意,这些操作可能会与某些实现的索引值成比例地执行(例如,LinkedList类)

链表没有固有索引;调用.get(x)将需要列表实现来查找第一个条目并调用.next()x-1次(对于O(n)或线性时间访问),其中数组支持的列表只能在O(1)或常量时间内索引到backingarray[x]

如果你看看theJavaDoc forLinkedList,你会看到评论

所有操作都按照双链表的预期执行。索引到列表中的操作将从开头或结尾遍历列表,以较接近指定索引为准。

而JavaDoc forArrayList则相应

List接口的可调整大小的数组实现。实现所有可选列表操作,并允许所有元素,包括null。除了实现List接口之外,此类还提供了一些方法来操作内部用于存储列表的数组的大小。 (这个类大致相当于Vector,除了它是不同步的。)size,isEmpty,get,set,iterator和listIterator操作在恒定时间内运行。添加操作以分摊的常量时间运行,即添加n个元素需要O(n)时间。所有其他操作都以线性时间运行(粗略地说)。与LinkedList实现相比,常数因子较低。

Arelated question titled "Big-O Summary for Java Collections Framework"有一个答案指向这个资源,"Java Collections JDK6"你可能会觉得有帮助。


#3 热门回答(7 赞)

虽然接受的答案肯定是正确的,但我可以指出一个小缺陷。引用都铎王朝:

现在,转到List的另一个实现,即ArrayList,它由一个简单的数组支持。在这种情况下,上述两个遍历都是等效的,因为一个数组是连续的,所以它允许随机跳转到任意位置。

这不完全正确。事实是,那

使用ArrayList,手写计数循环的速度提高约3倍
source: Designing for Performance, Google's Android doc
请注意,手写循环是指索引迭代。我怀疑它是因为迭代器与增强的for循环一起使用。它在由连续数组支持的结构中产生较小的惩罚性能。我也怀疑Vector类可能也是如此。

我的规则是,尽可能使用增强的for循环,如果你真的关心性能,只对ArrayLists或Vectors使用索引迭代。在大多数情况下,你甚至可以忽略这一点 - 编译器可能会在后台对此进行优化。

我只是想指出,在Android的开发环境中,ArrayLists的遍历都是**,不一定等同于**.只是值得深思。