我们使用容器经常会用到遍历，而之前几篇文章都没有提到这一点。所以，今天把这块内容补一下。
public class ArrayList<E> extends AbstractList<E>
implements List<E>,
RandomAccess,
Cloneable,
java.io.Serializable
ArrayList 集成 AbstractList 抽象类。AbstractList 中提供了两个迭代器的实现类，默认实现了迭代器接口，实现了对元素的遍历，它们就是Itr 和其子类 ListItr。
ArrayList 实现 List 接口，能对它进行队列操作。
ArrayList 实现 RandomAccess 接口，
ArrayList 实现了 Cloneable 接口，即覆盖了函数clone()，能克隆。
ArrayList 实现 java.io.Serializable 接口，这意味着 LinkedList 支持序列化，能通过序列化去传输。
先看看 ArrayList 的三种遍历
// 先创建一个100w元素的ArrayList
for (int i=0; i < 1000000; i++){
arrayList.add(i);
}
long start, end;
// foreach循环
start = System.currentTimeMillis();
for (Integer item : arrayList) {
//System.out.println(item);
}
end = System.currentTimeMillis();
System.out.println("foreach cost time = " + (end-start) + "ms");
// 普通for循环，通过get函数获取元素
start = System.currentTimeMillis();
for (int i=0; i < arrayList.size(); i++) {
arrayList.get(i);
}
end = System.currentTimeMillis();
System.out.println("for cost time = " + (end-start) + "ms");
// 迭代器循环
start = System.currentTimeMillis();
Iterator<Integer> it = arrayList.iterator();
while (it.hasNext()) {
it.next();
}
end = System.currentTimeMillis();
System.out.println("Iterator cost time = " + (end-start) + "ms");
foreach cost time = 15ms
for cost time = 7ms
Iterator cost time = 29ms
对同一个100w元素的ArrayList进行三种不同的循环，我们发现，最快的居然是通过get函数读取元素。
那么，foreach循环是什么东西，怎么会比迭代器快的呢？
使用foreach结构的类对象必须实现了Iterable接口，Java的Collection继承自此接口，List实现了Collection，Collection 这个接口仅包含一个函数，源码如下：
public interface Iterable<T> {
/**
* Returns an iterator over a set of elements of type T.
*
* @return an Iterator.
*/
Iterator<T> iterator();
}
iterator()用于返回一个Iterator，原来，JAVA中的增强for循环底层是通过迭代器模式来实现的。
那为什么遍历ArrayList使用迭代器就这么慢呢？
我们看下public interface Iterator<E>接口的实现：
public Iterator<E> iterator() {
return new Itr();
}
/**
* An optimized version of AbstractList.Itr // 这还是优化过的版本呢
*/
private class Itr implements Iterator<E> {
// 数组的游标
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount;
// prevent creating a synthetic constructor
Itr() {}
public boolean hasNext() {
return cursor != size;
}
@SuppressWarnings("unchecked")
public E next() {
checkForComodification();
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
// 临时引用指向数组
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
// 通过数组索引访问元素
cursor = i + 1;
return (E) elementData[lastRet = i];
}
原来，ArrayList的迭代器的next()函数也是通过索引快速访问到元素的。如果数组比较小，那么不管用哪种遍历性能都差不多。如果数组比较大，那么，我们现在知道，用普通循环+get读取元素来遍历ArrayList，会比迭代器快一倍。这是因为get做了内联优化处理，节省大量的函数调用进出时间。
所以，如果有面试官问你，ArrayLsit哪种遍历最快？为什么？你会回答了吗？
接下来，我们来看看LinedList的定义。
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>,
Deque<E>,
Cloneable,
java.io.Serializable
LinkedList 集成AbstractSequentialList抽象类，内部使用listIterator迭代器来实现重要的方法
LinkedList 实现 List 接口，能对它进行队列操作。
LinkedList 实现 Deque 接口，即能将LinkedList当作双端队列使用。
LinkedList 实现了Cloneable接口，即覆盖了函数clone()，能克隆。
LinkedList 实现java.io.Serializable接口，这意味着LinkedList支持序列化，能通过序列化去传输。
先看 LinkedList 的遍历。先插入100w个元素，然后用foreach、迭代器、removeFirst 这三种方法遍历（循环get不需要测试了，简直慢到难以忍受）。
LinkedList linkedList = new LinkedList();
for (int i=0; i<1000000; i++) {
linkedList.add(i);
}
long start, end;
start = System.currentTimeMillis();
for (Object item : linkedList) {
//System.out.println(item);
}
end = System.currentTimeMillis();
System.out.println("foreach cost time = " + (end-start) + "ms");
start = System.currentTimeMillis();
Iterator<Integer> it = linkedList.iterator();
while (it.hasNext()) {
it.next();
}
end = System.currentTimeMillis();
System.out.println("Iterator cost time = " + (end-start) + "ms");
start = System.currentTimeMillis();
while (linkedList.size() != 0) {
linkedList.removeFirst();
}
end = System.currentTimeMillis();
System.out.println("removeFirst cost time = " + (end-start) + "ms");
运行代码得到结果如下：
foreach cost time = 12ms
Iterator cost time = 11ms
removeFirst cost time = 24ms
印证了之前我们分析的结论，foreach就是Iterator，所以它们的效率都差不多。不过从代码精简方面来看，当然是foreach更简单。
而某些文章提到用removeFirst会遍历更快，但是在笔者的环境下不成立。
为什么呢？我们先看看next()的实现：
private class ListItr implements ListIterator<E> {
private Node<E> lastReturned;
private Node<E> next;
private int nextIndex;
private int expectedModCount = modCount;
public E next() {
checkForComodification();
if (!hasNext())
throw new NoSuchElementException();
lastReturned = next;
next = next.next;
nextIndex++;
return lastReturned.item;
}
真相大白！原来LinkedList为了用迭代器顺序遍历，用了lastReturned保存最近一次返回的节点，next下一次返回的节点，nextIndex保存下一个节点的索引。
再将元素增大一倍，就是200万个元素。
foreach cost time = 20ms
Iterator cost time = 21ms
removeFirst cost time = 37ms
而removeFirst还是比迭代器多10多毫秒。证明这个多10ms应该是多了节点删除操作的开销。
ok，那么今天我们的结论就是
- ArrayList推荐用for循环get元素遍历最快，不仅是连续内存读取，而且还有内联优化节省函数调用开销。
- LinkedList推荐用foreach遍历元素最快，因为内部实现是迭代器。
- 相同的数据量，ArrayList最快的遍历比LinkedList最快遍历快一倍。
