为什么迭代列表要比索引遍历更快?

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (52)

List接口提供了四种方法,用于对List元素的位置(索引)访问。列表(如Java数组)是基于零的。请注意,对于某些实现(例如,LinkedList类),这些操作可能按时间与索引值成比例执行。因此,在调用者不知道实现的情况下,迭代列表中的元素通常比通过列表进行索引更可取。

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

提问于
用户回答回答于

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

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

进入item3,可以清楚地看到,需要从头到每个节点,直到到达第3项,因为不能直接跳下去。

因此,如果我想打印每个元素的值,如果我写了以下内容:

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

因为每次索引时,它都会从列表的开头重新开始,并遍历每一项。

如果我这么做了:

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

接下来发生的是:

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

所有这些都是在一个单独的遍历中完成的,这是O(N).

现在,转到另一个实现List那就是ArrayList,它由一个简单的数组支持。

用户回答回答于

答案隐含在这里:

注意,对于某些实现,这些操作可能会按照索引值的时间比例执行(例如LinkedList类)。

链接列表没有固有的索引;调用.get(x)将需要列表实现来查找第一个条目并调用.next()x-1次(对于O(N)或线性时间访问),其中数组支持的列表只需索引到backingarray[x]以O(1)或恒定时间表示。

所有这些操作的执行情况都与双链接列表的预期相同。索引到列表中的操作将从开始或结束遍历列表,以更接近指定索引的值为准。

列表接口的可调整大小数组实现。实现所有可选的列表操作,并允许所有元素,包括NULL。除了实现列表接口之外,该类还提供了操作内部用于存储列表的数组大小的方法。 大sizeisEmptygetsetiterator,和listIterator操作在固定时间内运行。Add操作以摊销的恒定时间运行,也就是说,添加n个元素需要O(N)时间。所有其他操作都以线性时间运行(粗略地说)。常数因子比LinkedList执行。

扫码关注云+社区