2）LinkedList
遍历 LinkedList 找到某个元素的话，通常也有两种形式：
get(int)，找指定位置上的元素 public E get(int index) { checkElementIndex(index); return node(index).item; }
既然需要调用 node(int) 方法，就意味着需要前后半段遍历了。
indexOf(Object)，找元素所在的位置 public int indexOf(Object o) { int index = 0; if (o == null) { for (LinkedList.Node<E> x = first; x != null; x = x.next) { if (x.item == null) return index; index++; } } else { for (LinkedList.Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) return index; index++; } } return -1; }
需要遍历整个链表，和 ArrayList 的 indexOf() 类似。
那在我们对集合遍历的时候，通常有两种做法，一种是使用 for 循环，一种是使用迭代器（Iterator）。
如果使用的是 for 循环，可想而知 LinkedList 在 get 的时候性能会非常差，因为每一次外层的 for 循环，都要执行一次 node(int) 方法进行前后半段的遍历。
LinkedList.Node<E> node(int index) { // assert isElementIndex(index); if (index < (size >> 1)) { LinkedList.Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { LinkedList.Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } }
那如果使用的是迭代器呢？
LinkedList<String> list = new LinkedList<String>();
for (Iterator<String> it = list.iterator(); it.hasNext();) {
it.next();
}
迭代器只会调用一次 node(int) 方法，在执行 list.iterator() 的时候：先调用 AbstractSequentialList 类的 iterator() 方法，再调用 AbstractList 类的 listIterator() 方法，再调用 LinkedList 类的 listIterator(int) 方法，如下图所示。
最后返回的是 LinkedList 类的内部私有类 ListItr 对象：
public ListIterator<E> listIterator(int index) { checkPositionIndex(index); return new LinkedList.ListItr(index); } private class ListItr implements ListIterator<E> { private LinkedList.Node<E> lastReturned; private LinkedList.Node<E> next; private int nextIndex; private int expectedModCount = modCount; ListItr(int index) { // assert isPositionIndex(index); next = (index == size) ? null : node(index); nextIndex = index; } public boolean hasNext() { return nextIndex < size; } public E next() { checkForComodification(); if (!hasNext()) throw new NoSuchElementException(); lastReturned = next; next = next.next; nextIndex++; return lastReturned.item; } }
执行 ListItr 的构造方法时调用了一次 node(int) 方法，返回第一个节点。在此之后，迭代器就执行 hasNext() 判断有没有下一个，执行 next() 方法下一个节点。
由此，可以得出这样的结论：遍历 LinkedList 的时候，千万不要使用 for 循环，要使用迭代器。
也就是说，for 循环遍历的时候，ArrayList 花费的时间远小于 LinkedList；迭代器遍历的时候，两者性能差不多。
06、总结
花了两天时间，终于肝完了！相信看完这篇文章后，再有面试官问你 ArrayList 和 LinkedList 有什么区别的话，你一定会胸有成竹地和他扯上半小时了。
这是《Java 程序员进阶之路》专栏的第 61 篇。Java 程序员进阶之路，风趣幽默、通俗易懂，对 Java 初学者极度友好和舒适😘，内容包括但不限于 Java 语法、Java 集合框架、Java IO、Java 并发编程、Java 虚拟机等核心知识点。
https://github.com/itwanger/toBeBetterJavaer
目前已更新或计划更新的内容，绿色✅的是已经更新的。
这么硬核的开源教程，还不赶紧 star 下？
