为什么迭代 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);
}

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

then what happens is this:

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

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

all in a single traversal, which is 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屋！