java - 为什么迭代 List 比通过它索引更快？

Question

阅读Java documentation for the ADT List它说:

The List interface provides four methods for positional (indexed) access to list elements. Lists (like Java arrays) are zero based. Note that these operations may execute in time proportional to the index value for some implementations (the LinkedList class, for example). Thus, iterating over the elements in a list is typically preferable to indexing through it if the caller does not know the implementation.

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

Answer 1

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

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

这效率极低，因为每次您编制索引时，它都会从列表的开头重新开始并遍历每个项目。这意味着您的复杂性实际上是 O(N^2) 只是为了遍历列表!

如果我这样做:

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

然后发生的事情是这样的:

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

全部在一次遍历中，即O(N)。

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