125

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

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

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

4

5 回答 5

210

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

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

于 2012-05-07T17:44:35.490 回答
35

答案隐含在这里：

请注意，对于某些实现（例如 LinkedList 类），这些操作的执行时间可能与索引值成正比

链表没有固有索引；调用.get(x)将要求列表实现找到第一个条目并调用.next()x-1 次（对于 O(n) 或线性时间访问），其中数组支持的列表只能backingarray[x]在 O(1) 或恒定时间内索引。

如果您查看JavaDoc forLinkedList，您会看到注释

所有操作都按照双向链表的预期执行。索引到列表中的操作将从开头或结尾遍历列表，以更接近指定索引的为准。

而JavaDoc forArrayList有相应的

List 接口的可调整大小的数组实现。实现所有可选列表操作，并允许所有元素，包括 null。除了实现 List 接口之外，该类还提供了一些方法来操作内部用于存储列表的数组的大小。（这个类大致相当于 Vector，只是它是不同步的。）

、size、isEmpty、get、set和操作在恒定时间内运行iterator。listIterator添加操作在摊销常数时间内运行，即添加 n 个元素需要 O(n) 时间。所有其他操作都以线性时间运行（粗略地说）。与实现的常数因子相比，常数因子较低LinkedList。

题为“Java Collections Framework 的 Big-O 摘要”的相关问题有一个指向此资源“Java Collections JDK6”的答案，您可能会发现它很有帮助。

于 2012-05-07T17:41:16.113 回答
8

迭代具有查找偏移量的列表，例如i，类似于Shlemiel thepainter's algorithm。

Shlemiel 找到了一份街头画家的工作，在路中间画出虚线。第一天，他把一罐油漆带到路上，完成了 300 码的路。“那还不错！” 他的老板说，“你是一个快速的工人！” 并付给他一个戈比。

第二天，Shlemiel 只完成了 150 码。“嗯，那不如昨天好，但你仍然是一个快速的工人。150码是体面的，”并付给他一个戈比。

第二天，Shlemiel 粉刷了 30 码的道路。“只有三十个！” 他的老板喊道。“这不可接受！第一天你做了十倍的工作！这是怎么回事？”

“我无能为力，”Shlemiel 说。“我每天都离油漆罐越来越远！”

来源。

这个小故事可能会让我们更容易理解内部发生的事情以及为什么它如此低效。

于 2012-05-09T03:26:16.230 回答
7

虽然公认的答案肯定是正确的，但我可以指出一个小缺陷。引用都铎语：

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

这并不完全正确。事实是，那

使用 ArrayList，手写的计数循环大约快 3 倍

来源：Designing for Performance，Google 的 Android 文档

请注意，手写循环是指索引迭代。我怀疑它是因为与增强的 for 循环一起使用的迭代器。它在由连续数组支持的结构中产生较小的惩罚性能。我也怀疑这可能适用于 Vector 类。

我的规则是，尽可能使用增强的 for 循环，如果您真的关心性能，请仅对 ArrayLists 或 Vectors 使用索引迭代。在大多数情况下，您甚至可以忽略这一点——编译器可能会在后台对此进行优化。

我只想指出，在Android开发的上下文中，ArrayLists的遍历并不一定是等价的。只是思考的食物。

于 2012-05-08T18:54:50.533 回答
4

要找到实现的第 i 个元素，需要LinkedList遍历所有元素，直到第 i 个。

所以

for(int i = 0; i < list.length ; i++ ) {
    Object something = list.get(i); //Slow for LinkedList
}
于 2012-05-07T17:41:55.723 回答