【java容器的刻意练习】【八】ArrayList与LinkedList的遍历【java容器的刻意练习】【八】

我们使用容器经常会用到遍历，而之前几篇文章都没有提到这一点。所以，今天把这块内容补一下。

public class ArrayList extends AbstractList implements List, 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 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 { /** * Returns an iterator over a set of elements of type T. * * @return an Iterator. */ Iterator iterator(); }

iterator()用于返回一个Iterator，原来，JAVA中的增强for循环底层是通过迭代器模式来实现的。
那为什么遍历ArrayList使用迭代器就这么慢呢？
我们看下public interface Iterator接口的实现：

public Iterator iterator() { return new Itr(); }/** * An optimized version of AbstractList.Itr // 这还是优化过的版本呢 */ private class Itr implements Iterator { // 数组的游标 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 = https://www.it610.com/article/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 extends AbstractSequentialList implements List, Deque, 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 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 {private Node lastReturned; private Node 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万个元素。