问为什么遍历列表会比索引更快呢？

EN

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

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

答案隐含在这里：

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

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

如果您查看JavaDoc for LinkedList，您将看到以下注释

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

而JavaDoc for ArrayList具有对应的

Resizable- List接口的数组实现。实现所有可选的列表操作，并允许所有元素，包括null。除了实现list接口之外，该类还提供了一些方法来操作内部用于存储列表的数组的大小。(这个类大体上等同于Vector，只是它是不同步的。)

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

一个related question titled "Big-O Summary for Java Collections Framework"有一个指向这个资源"Java Collections JDK6"的答案，你可能会发现它对你有帮助。

使用偏移量遍历列表以进行查找，例如i，类似于画家Shlemiel的算法。

Shlemiel找到了一份街道油漆工的工作，他在路中间画虚线。第一天，他带着一罐油漆上路，完成了300码的路程。“这真是太好了！”他的老板说：“你干得真快！”然后付给他一个科比。

第二天，施莱米尔只完成了150码。“嗯，这远没有昨天那么好，但你仍然是一个速度很快的工人。150码是值得尊敬的，”他付给他一个科比。

第二天，施莱米尔画了30码的路。“只有30个！”他的老板喊道。“这是不能接受的！第一天你就做了十倍的工作！这是怎么回事？”

“我忍不住，”施莱米尔说。“我一天比一天离油漆罐越来越远！”

Source。

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