其实很久以前就想做这个系列了，因为深感数据结构的重要性，只是之前作业一直很多，没怎么有时间去弄这个，现在虽然也很忙，但还是抽出了时间来学习。
首先Java中集合框架有两大类，分别是Collection和Map，先来看Collection的父接口——Iterable
Iterable
Iterable接口很简单，主要是下面两个方法，这些方法也没什么好研究的，这个类主要是为了生成一个Iterator对象，下面的Iterator才是重头戏
Iterator
Iterator就是C/C++中大家很常见的迭代器了，只是个接口，有下面几个方法根据文档所说，它是用来代替原来Enumeration类，有两个优点。一是函数名比较短23333,二是调用者可以在迭代的途中删除元素，也就是说Enumeration在迭代过程中是不能删除元素的，会抛出错误。
- void remove() 删除上一次next操作所返回的对象，如果没有执行过next会抛出错误
值得注意的是这个方法并不是抽象方法，而是有默认实现的：
default void remove() {
throw new UnsupportedOperationException("remove");
}
也就是说子类可以不实现这个方法，让这个迭代器不可在中途删除元素，例如如果是只读集合的话就可以不实现这个方法
ListIterator
ListIterator也是个接口，按照官方文档所说，它与Iterator不同之处有下面三点：
1.它是双向的，即既可以向前遍历也可以向后遍历
2.可以获得当前迭代器当前位置的索引
3.可以在迭代过程中修改列表的值
初始时它在第 0 个元素之前，调用 next() 游标后移一位：
也就是说长度为 N 的集合会有 N+1 个游标的位置。
ListIterator是由Iterator继承而来的，新增加了6个方法，- boolean hasPrevious() 和hasNext()基本差不多，只不过返回前面是否有元素
- E previous() 返回游标的前一个元素，同时向前进一步，如果没有前面元素则会抛出NoSuchElementException
- int nextIndex() 返回调用next时会返回的元素的索引，也就是游标后面元素的索引
- int previouxIndex() 与上面方法类似
- void set(E) 设置上一次next()或previous()返回的元素为E，如果没有进行过next或previous操作则会抛出错误
- void add(E) 在游标前面插入一个元素
ListIterator的具体实现
可以追踪到AbstractList里的listIterator方法，里面创建了个ListItr的实例，于是我们来看看ListItr
public ListIterator<E> listIterator(final int index) {
rangeCheckForAdd(index);
return new ListItr(index);
}
ListItr继承自Itr，Itr实现了Iterator接口
private class Itr implements Iterator<E> {
重点看一下next和remove方法
public E next() {
checkForComodification();
try {
int i = cursor;
E next = get(i);
lastRet = i;
cursor = i + 1;
return next;
} catch (IndexOutOfBoundsException e) {
checkForComodification();
throw new NoSuchElementException();
}
}
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
AbstractList.this.remove(lastRet);
if (lastRet < cursor)
cursor--;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException e) {
throw new ConcurrentModificationException();
}
}
你会发现里面在开始都有一个checkForComodification的方法，这个方法是为了以防你在遍历的时候偷偷修改或删除元素的值的，让我们看看它的源码：
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
当expectedModCount和不相等时便会抛出错误，这里的modCount是AbstractList的成员变量，而expectedModCount是Itr的成员变量，它初始化为modCount
/**
* The modCount value that the iterator believes that the backing
* List should have. If this expectation is violated, the iterator
* has detected concurrent modification.
*/
int expectedModCount = modCount;
以ArrayList为例，调用add，clear和remove的时候，modCount都会修改，
public boolean add(E object) {
//...
modCount++;
return true;
}
public void clear() {
if (size != 0) {
//...
modCount++;
}
}
public boolean remove(Object object) {
Object[] a = array;
int s = size;
if (object != null) {
for (int i = 0; i < s; i++) {
if (object.equals(a[i])) {
//...
modCount++;
return true;
}
}
} else {
for (int i = 0; i < s; i++) {
if (a[i] == null) {
//...
modCount++;
return true;
}
}
}
return false;
}
这样就实现了检测遍历途中是否发生了元素的添加以及修改
但如果确实要在遍历的时候添加元素、修改元素该怎么办呢？
还记得之前的ListIterator的特点吗？其中有一条就是可以在遍历中途修改元素
An iterator for lists that allows the programmer to traverse the list in either direction, modify the list during iteration, and obtain the iterator's current position in the list.
那么是如何实现的呢？
public void set(E e) {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
AbstractList.this.set(lastRet, e);
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
public void add(E e) {
checkForComodification();
try {
int i = cursor;
AbstractList.this.add(i, e);
lastRet = -1;
cursor = i + 1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
可以看到在修改和添加之后都会强制让expectedMod等于modCount
而且要注意的是不能调用AbstractList中的remove和add方法进行元素的添加和删除，而是要调用ListIterator中的remove和add方法
其他的代码都比较简单，就不在这里赘述了。
