Stack Overflow 上的另一个主题“ Java 中的传统 for 循环与迭代器”讨论了使用索引和使用迭代器之间的性能差异。最佳答案指出，在处理诸如LinkedList.
我希望这与缓存有关。如果是这样，迭代器如何解决这个问题？如果它与缓存未命中无关，那么是什么让非连续容器的迭代器如此之快？
问问题
132 次
1 回答
2
链表的区别不是任何常数因素 - 它是“一步”采用 O(1) 或 O(N) 之间的区别。（所以列表越大，差异越大。）
迭代器保留“采取下一步”所需的任何状态。对于链表，采取下一步意味着只遵循从一个节点到下一个节点的引用......而通过索引访问元素意味着从头部开始并多次执行相同的“移动下一步”步骤。
与之ArrayList相比，迭代器只需要记住当前索引，然后“随机访问”和“顺序”访问都涉及直接访问数组的正确元素。
所以它并不是真正的缓存——它是保留状态。迭代器是否比按索引访问更快取决于按索引访问必须做什么。在 的情况下ArrayList，它很便宜。在 的情况下LinkedList，它不是。
于 2012-11-03T21:32:42.247 回答