为什么遍历列表比索引索引快？

Question

阅读有关ADT列表的Java文档时，它说：

List接口提供了四种位置（索引）访问列表元素的方法。列表（如Java数组）从零开始。请注意，对于某些实现（例如，LinkedList类），这些操作可能在时间上与索引值成比例执行。因此，如果调用者不知道实现，则遍历列表中的元素通常比对其进行索引更可取。

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

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由一个简单数组支持。在这种情况下，上述两个遍历都是等效的，因为数组是连续的，因此它允许随机跳转到任意位置。