for循环和链表介绍
咱们都知道java中有个增强型for循环，这个for循环很方便，假如不需求知道当时遍历到第几个的话能够跟一般for循环替换运用，也有人知道这俩如同有那么一点点不一样，但为什么不一样就不知道了。
咱们还知道LinkedList是一个双向链表，这个调集应该是唯一一个既实现了List接口又实现了Queue接口的调集类。
链表这种数据结构，跟数组比较，优势在刺进，劣势在遍历，那假如要遍历一个链表，就要从头开端遍历，不然根本不知道下一个Node是什么。
增强for循环为什么遍历LinkedList那么快
其实这个标题不合适，应该是为什么一般for循环遍历LinkedList为什么那么慢。咱们写代码验证一下时刻：
public void test() {
LinkedList<Integer> list = new LinkedList<>();
for (int i = 0; i < 100000; i++) {//刺进100000条数据
list.add(i);
}
int index = 0;//记录最终一个元素
long time1 = System.currentTimeMillis();
for (int i = 0; i < list.size(); i++) {//一般for循环遍历
index = list.get(i);
}
long time2 = System.currentTimeMillis();
LogUtil.Companion.d("1:" + (time2 - time1) + " index->" + index);
for (int i : list) {//增强for循环遍历
index = i;
}
long time3 = System.currentTimeMillis();
LogUtil.Companion.d("2:" + (time3 - time2) + " index->" + index);
Iterator<Integer> iterator = list.listIterator();
while (iterator.hasNext()) {//iterator遍历
index = iterator.next();
}
long time4 = System.currentTimeMillis();
LogUtil.Companion.d("3:" + (time4 - time3) + " index->" + index);
}
运行结果：
1:5056 index->99999
2:12 index->99999
3:1 index->99999
其实增强型for循环底层便是用iterator实现的，能够剖析两者的字节码得出这个定论，这儿咱们不剖析，算作一致定论。来看上面的结果，发现一般for循环遍历的时刻跟增强for循环和iterator比较几乎令人发指。
为什么会这样呢？咱们看LinkedList的源码一探终究。
LinkedList是一个双向链表，用Head跟Tail两个Node记录了头尾节点。
LinkedList相关源码剖析
一般for循环
咱们看到其实一般for循环仅仅调用了LinkedList的 get(index) 办法：
//LinkedList.java
public E get(int index) {
checkElementIndex(index); //仅仅检测是否数组越界
return node(index).item; //调用了node(index)办法
/**
* Returns the (non-null) Node at the specified element index.
*/
Node<E> node(int index) {
// assert isElementIndex(index);
//判别index离头部近一点仍是离尾部近一点
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
}
get办法很简单，仅仅调用了node办法，node办法也很简单，仅仅判别了index是否是小于size/2，小于阐明离Head近一点，不然阐明离tail近，离哪个近就从哪一头开端暴力遍历，所以假如LinkedList有100000个Node，那最远的那个Node假如调用get办法就需求遍历50000次。
所以一般for循环遍历一次n个节点的LinkedList需求1+2+3+...+n/2+n/2+...+3+2+1次，时刻复杂度能够写作O(n^2^)。
增强for循环
能够看到最终是调用了LinkedList的内部类ListItr
//LinkedList.java
public ListIterator<E> listIterator(int index) {
checkPositionIndex(index);
return new ListItr(index);
}
private class ListItr implements ListIterator<E> {
private Node<E> lastReturned;
private 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;
}
...
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
这儿咱们疏忽一部分代码先只看for循环触及的办法，代码其实也很简单。假如 hasNext() 存在，就调用next() ，两个Node：lastReturned和next。
每次获取index的时分调用 ListItr(int index) 后next会指向当时index的Node。
调用next的时分lastReturned会指向next也便是当时index的Node，next指向next.next，所以每次遍历的时分只需赋值一次就能够得到next的节点，所以遍历一个n个节点的LinkedList便是需求n次。
所以用iterator遍历的话时刻复杂度便是O(n)。
这便是为什么两个for循环的方式这么差异这么大了~咱们也能够直观的看出来当n到达十万这个级别的时分O(n^2^)和O(n)差别有多大了。
不知道各位发现没有，Iterator里边每个操作都先调用了 checkForComodification() 办法，判别 (modCount != expectedModCount) 是否持平。
各位应该发现了ListItr有一个赋值，把modCount赋值给了expectedModCount，但每次调用遍历或许addsetget的时分都会判别这两个值是否持平。
modCount是父类AbstractList的特点，而每次调用add(),remove()办法的时分这个值都会变，也便是假如调集里边内容修改了modCount都会发生改动。
So，在运用Iterator的时分不能调用add()或许remove()这些会改动调集内容的办法。两种情况：
- 在增强型for循环里边不能有add或许remove操作，运用Iterator迭代的时分不能做add或许remove操作。
- 假如有其他线程操作调集，需求加锁防止改动调集，等待循环结束之后再修改。
不然都会报ConcurrentModificationException。
