为什么迭代List会比索引更快？ [英] Why would iterating over a List be faster than indexing through it?

问题描述

阅读 ADT列表的Java文档它说：

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

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.

究竟是什么这是否意味着？我不明白得出的结论。

What exactly does this mean? I don't understand the conclusion which is drawn.

推荐答案

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

In a linked list, each element has a pointer to the next element:

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

要访问 item3 ，你可以清楚地看到你需要从头部走过每个节点，直到你到达item3，因为你不能直接跳。

To access item3, you can see clearly that you need to walk from the head through every node until you reach item3, since you cannot jump directly.

因此，如果我想打印每个节点的值元素，如果我这样写：

Thus, if I wanted to print the value of each element, if I write this:

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）只是为了遍历列表！

This is horribly inefficient because every time you are indexing it restarts from the beginning of the list and goes through every item. This means that your complexity is effectively O(N^2) just to traverse the list!

如果相反我这样做：

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

然后会发生什么：

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

所有在一次遍历中， O（N ）。

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

Now, going to the other implementation of List which is ArrayList, that one is backed by a simple array. In that case both of the above traversals are equivalent, since an array is contiguous so it allows random jumps to arbitrary positions.

这篇关于为什么迭代List会比索引更快？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！