为什么迭代List会比通过它索引更快？
阅读ADT列表的Java文档，它说：
List接口提供了四种位置（索引）访问列表元素的方法。 列表（如Java数组）基于零。 请注意，这些操作的执行时间可能与某些实现（例如LinkedList类）的索引值成比例。 因此，如果调用者不知道实现，遍历列表中的元素通常更适合通过索引。
这到底是什么意思？ 我不明白所得出的结论。
在链表中，每个元素都有一个指向下一个元素的指针：
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) 。
现在，转到ArrayList的其他实现，那是一个简单的数组支持。 在这种情况下，上述两个遍历都是等价的，因为数组是连续的，所以它允许随机跳转到任意位置。
答案暗示在这里：
请注意，这些操作的执行时间可能与某些实现的索引值成比例（例如LinkedList类）
链表不具有固有的索引; 调用.get(x)将需要列表实现来查找第一个条目并调用.next() x-1次（对于O（n）或线性时间访问），其中数组支持列表可以索引到backingarray[x] O（1）中的backingarray[x]或常量时间。
如果您查看LinkedList的JavaDoc ，您将看到注释
所有的操作都可以预期为双向链表。 索引到列表中的操作将从开始或结束遍历列表，以哪个更接近指定的索引为准。
而JavaDoc for ArrayList有相应的
List接口的可resize的实现。 实现所有可选的列表操作，并允许所有元素，包括null。 除了实现List接口之外，该类还提供了一些方法来处理内部用来存储列表的数组的大小。 （这个类大致相当于Vector，除了它是不同步的。）
size，isEmpty，get，set，iterator和listIterator操作在一定的时间内运行。 add操作以分摊的恒定时间运行，即添加n个元素需要O（n）个时间。 所有其他的操作都在线性时间内运行（粗略地说）。 与LinkedList实现相比，常数因子较低。
标题为“Java集合框架的Big-O总结”的相关问题有一个答案指向这个资源， “Java Collections JDK6” ，你可能会发现它有帮助。
虽然接受的答案肯定是正确的，但我可以指出一个小缺陷。 引用都铎王朝：
现在，转到ArrayList的其他实现，那是一个简单的数组支持。 在这种情况下，上述两个遍历都是等价的 ，因为数组是连续的，所以它允许随机跳转到任意位置。
这并不完全正确。 事实是，那
使用ArrayList，手写计数的循环速度约快3倍
来源：devise性能，谷歌的Android文档
请注意，手写循环是指索引迭代。 我怀疑它是因为用于增强for循环的迭代器。 它在一个连续arrays支持的结构中产生一个小的惩罚performance。 我也怀疑Vector类可能是这样的。
我的规则是，尽可能使用增强型for循环，如果您真的关心性能，请仅对ArrayLists或Vectors使用索引迭代。 在大多数情况下，你甚至可以忽略这个 – 编译器可能会在后台优化这个。
我只想指出，在Android的发展背景下，ArrayLists的遍历不一定是等价的 。 只是思考的食物。
迭代查找偏移量的列表，比如i ，类似于画家algorithm的Shlemiel 。
史莱米尔得到了一个街头画家的工作，在路中间画了点线。 第一天，他把一jar油漆涂在路上，完成了300码的路。 “这很好！” 他的老板说：“你是个快工人！” 并支付给他一个科比。
第二天什莱米尔只完成了150码。 “呃，那还不如昨天，但你还是一个快速的工人，150码是可敬的，”他付出了一个科比。
第二天什莱米尔画了30码的道路。 “只有三十！” 喊老板。 “这是不可接受的！第一天你做了十次这么多的工作，发生了什么事？
“我忍不住了，”史莱米尔说。 “每天我都离油漆jar越来越远！”
来源 。
这个小故事可能会让人更容易理解内部发生的事情，以及为什么这么低效。
为了查找LinkedList的第i个元素，实现遍历所有元素直到第i个元素。
所以
for(int i = 0; i < list.length ; i++ ) { Object something = list.get(i); //Slow for LinkedList }
