为什么迭代列表比索引列表更快？

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

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)

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

答案就在这里暗示：

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

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

如果你看一下JavaDoc for LinkedList，你会看到评论。

所有操作的执行方式都与双链表的预期一样。索引到列表中的操作将从开始或结束遍历列表，以更接近指定索引者为准。

而 JavaDoc for ArrayList 具有相应的

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

、 、 、 和 操作以恒定时间运行。添加操作在摊销常量时间内运行，即添加 n 个元素需要 O（n） 时间。所有其他操作都在线性时间中运行（粗略地说）。与实现相比，常数因子较低。sizeisEmptygetsetiteratorlistIteratorLinkedList

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