java – 为什么迭代一个列表比索引更快?

阅读 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.

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

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

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

相关文章
相关标签/搜索