Java集合框架之LinkedList及ListIterator实现源码分析

学过这么久的Java，还没有仔细的分析过集合框架的源码实现，刚好这几天看数据结构，所以一并分析分析，并记录于此，希望对大家有一点帮助。由于本人能力有限，错误肯定很多，也希望大家指正，我会改正的，其中的分析仅代表本人 观点 。最后也希望大家多多支持，等List分析后，有机会再打算分析分析Map与Set的实现。

1、 ArrayList中（实为AbstractList中）的ListIterator实现源码分析

ArrayList的实现源码比较简单，就是对一个数组的一系列操作，比如添加一个元素后如果容量满则扩容操作、删除一个元素后使数组后面的元素像前移操作、扩容时把原来数组里的所有元素拷贝到新创建的数组中，其中对数组的拷贝与移动大量使用了 System.arraycopy，由于它底层是使用数组实现的，一般的操作我们都能很好的理解，所以这里就不分析ArrayList的实现了，而是分析一下它的迭代器实现。

 

ArrayList没有重新定义迭代器，通过iterator()及listIterator()方法返回的迭代器其实是父类 AbstractList中实现的迭代器， AbstractList中是通过内部类的方式实现了 Iterator与 ListIterator迭代接口，声明方式如下：

private class Itr implements Iterator<E> {//...}
private class ListItr extends Itr implements ListIterator<E> {//...}

Itr实现了Iterator接口，而ListItr继承了Itr同时又实现了ListIterator接口。Itr中定义了cursor、与lastRet两个字段， cursor指向的元素就是next将要获取的元素，初始时为零，即指向第一个元素。 lastRet为最后一次next或previous操作返回的元素，初始时为-1，即不指向任何元素，如果刚创建的ListIterator还没有执行过next操作，则执行 previous操作会抛出异常。

• nextIndex ：取当前光标的位置，代码片断如下：

return cursor;//返回当前光标所在位置

• previousIndex ：操作是取当前光标的前一位置，代码片断如下：

return cursor-1; //返回当前光标所在位置的前一位置

• hasNext() :是否还有下一个元素

return cursor != size();//如果当前光标还没有指向最后一元素的后面时表示有下一元素，其实这里的下一元素就是指光标cursor现指向的元素，只是使用next取了后会使其后移一位

• hasPrevious() ：是否还有前一个元素

return cursor != 0;//如果当前光标cursor不是指向第一个元素时，表示前面还有元素

• next() ：是先取当前光标所在位置后面的元素，然后把最后一次操作所在光标设置成当前光标，最后把当前光标后移一。代码片断如下：

checkForComodification();//检查外部是否修改了集合结构，即modCount是否与expectedModCount相等
try {
	Object next = get(cursor);//先取当前光标所在位置后面的元素
	lastRet = cursor++;//然后把最后一次操作所在光标设置成当前光标位置，再把当前光标后移一 
	return next;
} catch (IndexOutOfBoundsException e) {
	checkForComodification();
	throw new NoSuchElementException();
} 

• previous() ：是先让光标向前移，再取光标所在位置的元素。最后一次操作所在光标与当前光标位置设置成一样，代码片断如下：

checkForComodification();//检查外部是否修改了集合结构，即modCount是否与expectedModCount相等
try {
	int i = cursor - 1;//使光标先前移一
	Object previous = get(i);//再取当前光标前一元素
	lastRet = cursor = i;//最后让最后一次光标与当前光标都指向当前光标前一元素
	return previous;
} catch (IndexOutOfBoundsException e) {
	checkForComodification();
	throw new NoSuchElementException();
} 

• add(Object o) : 在当前光标位置添加元素，其他元素后移，并且添加后光标后移。

checkForComodification();//检查外部是否修改了集合结构，即modCount是否与expectedModCount相等
try {
	AbstractList.this.add(cursor++, o);//在当前光标位置添加元素，添加后当前光标后移一位
	lastRet = -1;//最后让最近一次操作光标所在位置复原，即-1，固不能马上进行删除与修改操作
	//通过迭代器本身改变集合结构后要使modCount与expectedModCount相等，不然下次无法继续使用迭代器操作集合了
	expectedModCount = modCount;
} catch (IndexOutOfBoundsException e) {
	throw new ConcurrentModificationException();
}

• set(Object o) : 操作的是最后一次进行next或previous操作返回的元素，修改后光标不变。

//如果迭代器是刚创建的且还没有next迭代操作、或刚进行过add操作、或刚进行过remove操作时lastRet都会为-1，
//所以如果通过迭代器进行过添加与删除操作后，是不能马上进行修改操作的
if (lastRet == -1)
	throw new IllegalStateException();
checkForComodification();//检查外部是否修改了集合结构，即modCount是否与expectedModCount相等
try {
	//修改的是最后一次next或previous返回元素，并且修改后当前光标与最后一次操作的光标都不会改变
	AbstractList.this.set(lastRet, o);
	//通过迭代器本身改变集合结构后要使modCount与expectedModCount相等，不然下次无法继续使用迭代器操作集合了
	expectedModCount = modCount;
} catch (IndexOutOfBoundsException e) {
	throw new ConcurrentModificationException();
}

• remove()：删除的是最后一次进行next或previous操作返回的元素，删除后光标是否改变分两种情况：

第一种 ：如果在删除操作前以前所作的操作为next，则删除后当前光标前移，因为删除当前lastRet所指向的元素，如果最近一次是next操作，则删除后由于后面的元素会前移一个
，如果此时不让next也后移一位，则删除前next指向的元素就会发生变化（有可能指向的是删除下next指向的元素的下一个元素，也有可能不存在了）。

第二种 ：如果在删除操作前以前所作的操作为previous，则删除后当前光标不动，实际此时的当前光标cursor位置与最后一次操作所在的光标lastRet位置相同。
不管经过上面哪一种情况，最后当前光标所在位置与最后一次操作所在光标位置相同。代码片断如下：

//如果迭代器是刚创建的且还没有next迭代操作、或刚进行过add操作、或刚进行过remove操作时lastRet都会为-1，
//所以如果通过迭代器进行过添操作后，是不能马上进行删除操作的
if (lastRet == -1)
	throw new IllegalStateException();
checkForComodification();//检查外部是否修改了集合结构，即modCount是否与expectedModCount相等
try {
	//删除最后一次操作所在光标位置的元素
	AbstractList.this.remove(lastRet);
	//如果上次操作为next，则该条件满足，后使当前光标前移一位；如果上次操作为previous，则条件不满足，删除后当前光标不会移动
	if (lastRet < cursor)
		cursor--;
	//最后让最近一次操作光标所在位置复原，即-1，固不能马上进行删除与修改操作
	lastRet = -1;
	//通过迭代器本身改变集合结构后要使modCount与expectedModCount相等，不然下次无法继续使用迭代器操作集合了  
	expectedModCount = modCount;
} catch (IndexOutOfBoundsException e) {
	throw new ConcurrentModificationException();
}

2、LinkedList源码分析

LinkedList：以 双向循环链表 为底层数据结构，并且每个元素都有一个编号，即索引号，其中头节点的 next 域指向索引号为0的元素也即第一个元素，而 previous 域指向索引号为 size -1 的元素也即最末元素。还是看图直观：

注，头节点header不作为数据节点使用，也就是说它与第一个第二个节点是不同的，我们不能删除它，只能修改它的前后指向，它专门用来标示一个循环链中哪个是第一个元素，哪个是最后一个元素，因为要把链表以索引访问的方式来引用就得这么作。

 

类中定义了两个字段：

private transient Entry header = new Entry(null, null, null);//头节点（注，它不计入链表中的总个数，它只用来标记链中哪个是第一个节点，哪个是最末节点），其next域永远指向第一节点，previous永远指向最末节点
private transient int size = 0;//集合大小

Entry是一个具有指向前驱与后继节点的数据结构：

private static class Entry {
	/*
	 * 这个内部类定义字段时使用的默认修饰符，即包访问，而不是private，这样会不会有不安全的问题？
	 * 这里不会，因为这个内部类是私有的，所以外面不管是否是同包，都不会直接访问得到，但可以被外部
	 * 类直接访问，这样外部类访问时就不需要使用get、set访问来访问，这样设计更简洁
	 */
	Object element;
	Entry next;
	Entry previous;

	Entry(Object element, Entry next, Entry previous) {
		this.element = element;//数据域，刚创建时头节点的值为null
		this.next = next;//后驱节点，刚创建时头节点指向null 
		this.previous = previous; //前驱节点，刚创建时头节点指向null
	}
}

再来看看LinkedList的默认构造函数：

public LinkedList() {
	//我们可以看出刚创建时，头节点的next与previous域都指向自己
	header.next = header.previous = header;
}

从上面的构建过程我们可以得到以下刚创建时的链表结构图：

链表此时是空的，头节点虽然在物理上是链表中的一个节点，但在逻辑上我们不要把它当作链表中的一个元素，即我们不能删除它与修改它的数据域值 （element的值永远是null），这样就链表中就永远有一个元素不能用户直接使用到。以此种方式牺牲一个节点的用处就是，能在循环双向链中知道哪个 是第一个元素，哪个是最后一个元素，这样也就可以给链中的元素编号了，这样链式结构最终可以以索引顺序的方式来访问，之所以LinkedList能像 ArrayList那样以索引的方式来访问（当然最后还是 以链式操作链表的 ），也就是这个原因。

 

下面开始分析链表的各种操作:

• 添加元素 ：LinkedList使用add(Object o)接口向链表中加入元素

//带一个参数的单个元素添加方法
public boolean add(Object o) {
	/*
	 * 实质上去调用了能指定插入位置的添加元素方法，默认是在header节点
	 * 前（即使用header的previous前驱域指向该新加元素）插入元素，即
	 * 链表的末尾加入元素
	 */
	addBefore(o, header);
	return true;
}

   

在向链表中加入元素时，我们要始终记得 header 的 next 域是指向第一个元素的（即索引为0的元素），而 previous 域却是指向最后一个元素的（即索引为 size -1 的元素）。所以在添加元素时在 header 前就是在链的末尾插入元素，如果是在链的第一个位置插入元素就是在 header.next 的前面插入元素。

 

下面我们再看看addBefore方法：

/**
 * 在指定的节点前插入元素
 * 
 * @param o 加插入的节点的数据域值
 * @param e 要在哪个节点前插入
 * @return
 */
private Entry addBefore(Object o, Entry e) {
	/*
	 * Entry构造函数的第二个参数为新增元素的后驱节点，即新增节点的next域会指向e，
	 * 第二参数为新增元素的后驱屮，即新增节点的previous会指向e.previous
	 */
	Entry newEntry = new Entry(o, e, e.previous);
	//上面构造完节点后，使新增节点的前驱节点的next域指向新增节点
	newEntry.previous.next = newEntry;
	//使新增节点的后驱节点的previous域指向新增节点
	newEntry.next.previous = newEntry;
	size++;//链表节点数加一
	modCount++;//集合结构发生变化，需加一
	return newEntry;
}

 

从上面代码可以看出，添加节点时实质上就是在链表尾加入节点元素 。

 

下面看看在链表末尾添加第一个元素与第二个元素的图：

 

在链末使用add(Object o)方法添加第一个节点：

 

在链末使用add(Object o)方法添加第二个节点：

 

特别提醒 ，新加节点的数据域element的值在图中我直接写成了该节点的节点编号了，实际上数据域的值不是这个编号，而是我们在创建节点实体Entry时传进的element参数值，这里只是为了形象的说节点的位置，把它对应的索引编号给写在数据域上了。所以后面出现的图中也是这样画，请不是把它给直接理解成数据域值了。

• 插入元素 ：LinkedList使用add(int index, Object element) 接口在链表中某节点前插入元素

/**
 * 在指定的节点前插入节点
 * @param index 在哪个节点前插入节点
 * @param element 插入节点的数据域值
 */
public void add(int index, Object element) {
	/*
	 * 如果索引后为链表大小，则表示在链的末尾加入元素。如果不是在末尾，那么
	 * 我们要根据给定的 index 元素索引号调用 entry 方法找到指定的节点，然
	 * 后调用前面分析过的 addBefore 方法在该节点插入要新增的节点元素
	 */
	addBefore(element, (index == size ? header : entry(index)));
}

 

下面我们看看 entry 方法是怎样根据指定的索引号在链表中查找一个节点的：

/**
 * 根据给定的节点索引号查找节点
 * 
 * @param index 元素索引号
 * @return
 */
private Entry entry(int index) {
	//指定的索引号不能小于0，也不能大于或等于size，这与数组索引表示是一样的
	if (index < 0 || index >= size)
		throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
	Entry e = header;
	//如果给定的索引号小于总节点数的一半，则说明要查找的元素在链表的前半部分
	if (index < (size >> 1)) {
		/*
		 * 从链表头向尾找指定的节点元素，比如链表中有5个元素，现找索引为1的节点，则要走该
		 * 分支，查找时需循环 1 - 0 + 1 = 2 次，即从头节点的 next 开始迭代两次即可定位
		 * 到索引号为1的节点上
		 */
		for (int i = 0; i <= index; i++)
			e = e.next;//
	} else {//否则要查找的元素在链表的后半部分
		/*
		 * 从链表尾向前找指定的节点元素，比如链表中有5个元素，现找索引为2的节点(即中间节点)
		 * ，则要走该分支，查找时需循环 5 - 2 = 3 次，即从头节点的 previous 开始迭代三
		 * 次即可定位到索引号为2的节点上
		 */
		for (int i = size; i > index; i--)
			e = e.previous;
	}
	return e;
}

 
好了，从上面的插入代码实现来分析，可以看出在调用插入方法add(int index, Object element) 比调用添加方法add(Object o)只是多了一个index，即将要在哪个节点前插入节点。下面看看分别在三种不同的位置插入节点情况：

第一种插入位置 ，在链表末节点后与头节点前插入节点，由于插入实现也是调用addBefore(Object o, Entry e) 方法来实现的，所以只要找出在哪个节点前插入并传递给
addBefore方法的第二个参数即可。由于现在要在最末节点后与头节点前插入，又因插入的方法第二个参数所需要的是要在哪个节点前插入而不是哪个节点后插入，所以此时第二个参数为头节点，具体值就为header。实质上此时与调用LinkedList的addLast（即在末元素后加入）是一样的，请看addLast方法实现：

//在头节点前，最末节点后插入元素
public void addLast(Object o) {
    addBefore(o, header);
}

 

第二种插入位置 ，在链表头节点后与第一个节点前插入节点，所以此时传递给addBefore(Object o, Entry e) 方法的第二个参数为第一个节点即可，又头节点header的next域指向第一个节点，所以第二个参数的具体值就为 header.next。实质上此时与调用LinkedList的addFirst（即在第一个元素前加入）是一样的，请看addFirst方法实现：

//在头节点后，第一个节点前插入元素
public void addFirst(Object o) {
    //header.next为第一个节点元素
    addBefore(o, header.next);
}

 

第三种插入位置 ，在链表中非第一个元素前与非最末元素后插入元素（链的节点数要大于1），此时传递给addBefore(Object o, Entry e) 方法的第二个参数需调用entry(int index)方法来获得，其中index参数就是需在哪个节点前插入的那个节点的索引号，index需大于0小于size。下面看看第三种情况的插入过程图：

• 访问元素

经过对添加与插入元素的分析，访问元素就更简单了，因为上面在第三种插入元素时，需要调用entry(index)来查找到在哪个节点前插入的节点，看看get(int index)的实现：

//获取指定的节点元素
public Object get(int index) {
    return entry(index).element;
}

//获取第一个节点元素
public Object getFirst() {
    if (size == 0)
        throw new NoSuchElementException();
    //header.next指向第一个节点元素
    return header.next.element;
}

//获取最后元素
public Object getLast() {
    if (size == 0)
        throw new NoSuchElementException();
    //header.previous指向最末节点元素
    return header.previous.element;
}

• 删除元素

所有的删除接口最后都是调用私有方法remove(Entry e)来实现的，所以我们先看看这个方法的实现：

/**
 * 删除指定的节点实体
 * @param e
 */
private void remove(Entry e) {
    if (e == header)
        throw new NoSuchElementException();

    //让待删除节点的前驱节点的next域指向待删除节点的后驱节点
    e.previous.next = e.next;
    //让待删除节点的后驱节点的previous域指向待删除节点的前驱节点
    e.next.previous = e.previous;
    //---注，下面两行只有在jdk1.5中才有，这样可加快gc
    //然后使待删除节点的next与previous都指向null
    e.next = e.previous = null;
    e.element = null;//待删除节点的数据域也设置成null
    size--;//节点个数减一
    modCount++;//集合结构发生变化
}

我们还是 对着删除过程图看代码比较容易理解：

下面看看用户删除节点接口：

/**
 * 删除指定的索引号节点
 * @param index
 * @return Object
 */
public Object remove(int index) {
    //先根据索引号找到要删除的元素
    Entry e = entry(index);
    remove(e);//调用私有方法remove(Entry e)实现删除
    return e.element;
}

/**
 * 删除第一个节点
 * @return Object
 */
public Object removeFirst() {
    Object first = header.next.element;
    //header.next就是指向第一个元素的
    remove(header.next);
    return first;
}

/**
 * 删除链表最末节点
 * @return Object
 */
public Object removeLast() {
    Object last = header.previous.element;
    //header.previous就是指向最末元素的
    remove(header.previous);
    return last;
}

3、LinkedList中的ListIterator实现源码分析

LinkedList自己重新实现了ListIterator接口，它没有直接使用AbstractList中的现实，LinkedList中定义了一个内部类ListItr，它实现了ListIterator接口，用来对LinkedList进行专门迭代，因为LinkedList与ArrayList还不同，它是使用链表结构实现的，所以需专门的迭代器。但该迭代器与ArrayList生成的迭代器（即继承自AbstractList中的ListIterator实现）的功能与特点都是一样的，因此符合ArrayList迭代器的特点也适合于LinkedList迭代器。下面就简单地看一下LinkedList中的ListIterator接口实现，一切的分析就看代码吧：

private class ListItr implements ListIterator {
	//最近一次next或previous操作所返回的元素，初始时为头节点，它标示链表的开始与结尾
	private Entry lastReturned = header;
	//向着索引编号递增的方向迭代。next用来指向next操作返回的节点，在构造时初始化成迭代元素中的第一个
	private Entry next;
	//用来记录next操作已移到哪个元素上了，即next元素指向的索引，始终与next保持同步
	private int nextIndex;
	//与ArrayList中的list迭代器中的此字段功能相同，用来检查外界是否被改变了集合的结构
	private int expectedModCount = modCount;

	/**
	 * 从指定的索引编号开始迭代，调用父类的listIterator()实质上是调用了 new ListItr(0)
	 * 该构造函数主要用来初始化next 与 nextIndex
	 * @param index
	 */
	ListItr(int index) {
		//这里按理应该是index >= size，相等时也是有问题的
		if (index < 0 || index > size)
			throw new IndexOutOfBoundsException("Index: " + index
					+ ", Size: " + size);
		/*
		 * 下面的逻辑与LinkedList的私有方法entry(int index)是一样的，这样做为了加快
		 * 搜索的速度
		 */
		if (index < (size >> 1)) {//index小于size的一半，则在前半部分找
			next = header.next;//从头找时next初始化成第一个元素
			/*
			 * 因为next本向就初始化成第一个元素了，所以要想移到指定的索引上只需
			 * index - nextIndex次，比如有4个节点，要从第一个元素（索引为0）开始迭代，
			 * 则 0 < 2 走该分支，需 0 - 0 = 0 次循环，即无需循环，结果nextIndex还是
			 * 指向初始化的第一节点，而 nextIndex 为0；如果从第二个元素（索引为1）开始
			 * 迭代，则 1 < 2 ，还是走该分支需 1 - 0 = 1 次循环，结果一次循环后next
			 * 会指向第二个元素，而 nextIndex 也会自然递增到 1 
			 */
			for (nextIndex = 0; nextIndex < index; nextIndex++)
				next = next.next;
		}
		else {//否则在后半部分找
			next = header;
			//比上面要多一次循环，因为nextIndex是从size开始的
			for (nextIndex = size; nextIndex > index; nextIndex--)
				next = next.previous;
			/*
			 * ？为什么不使用下面逻辑？这样即能与上面保持一致，又容易理解，可能是因为当
			 * index为0，size与为0时，nextIndex就会为-1，但如果前面的出错误条件改为
			 * index >= size 应该是可以使用下面这个逻辑的
			 */
			//	next = header.previous;
			//	for (nextIndex = size - 1; nextIndex > index; nextIndex--)
			//		next = next.previous;
		}
	}

	public boolean hasNext() {
		//如果 nextIndex与节点个数size相等，则表示链表本身为空或已迭代到最末元素后了
		return nextIndex != size;
	}

	public Object next() {
		//检查外部是否修改了集合结构，即modCount是否与expectedModCount相等  
		checkForComodification();
		if (nextIndex == size)
			throw new NoSuchElementException();

		lastReturned = next;//先记录next所在位置，并把它赋给lastReturned
		next = next.next;//然后再把next指向下一个元素
		nextIndex++;//nextIndex与next操作需同步，所以也要增一
		return lastReturned.element;
	}

	public boolean hasPrevious() {
		//如果已是第一个元素表示前面则没有节点了，或链表为空
		return nextIndex != 0;
	}

	public Object previous() {
		if (nextIndex == 0)
			throw new NoSuchElementException();
		//使next前移，并赋给lastReturned，最终lastReturned与next同指向next前一节点
		lastReturned = next = next.previous;
		//前移一位后当然需同步nextIndex，所以需递减一
		nextIndex--;
		checkForComodification();
		return lastReturned.element;
	}

	public int nextIndex() {
		return nextIndex;//next所指向节点索引
	}

	public int previousIndex() {
		return nextIndex - 1;//next元素的前一元素索引
	}

	public void remove() {
		checkForComodification();
		try {
			/*
			 * 使用LinkedList的remove方法删除最近一次next或previous操作返回的节点
			 * 
			 * !! 注，刚实例化的迭代器如果还没有进行后移(next)操作、或者是刚刚进行过添加
			 * 操作、又或者是刚刚进行过一次删除操作 后不能再进行删除操作了，因为上面这些操
			 * 作都会使lastReturned 指向 header
			 */
			LinkedList.this.remove(lastReturned);
		}
		catch (NoSuchElementException e) {
			throw new IllegalStateException();
		}

		//如果上一次是previous操作，则next与lastReturned相等
		if (next == lastReturned)
			/*
			 * 因为是previous操作，next与lastReturned指向的是同一元素，删除了
			 * lastReturned指向的元素就是删除next指向的元素，所以在删除后next需指向
			 * 下一个节点
			 * 
			 * 至于为什么nextIndex不需减一，请看下面图就明白了，其中lastReturned与
			 * next都指向了索引为1的节点，因此将删除索引为1的节点，由于删除的节点也是
			 * next指向的节点，删除后后面的节点的逻辑索引号都要减一，因此删除后next指向
			 * 的2节点索引号会变成1，这与nextIndex是相等的，所以不必减一了
			 * 
			 *              lastReturned   next
			 *                        ↓     ↓
			 * ----------+----------+---------+---------+----------
			 * |   Head  |     0    |  1(del) |    2    |    3    |
			 * ----------+----------+---------+---------+----------
			 */
			next = lastReturned.next;
		else
			/*
			 * 由于删除的是lastReturned指向的节点，走该分支的条件是上次是进行了next操
			 * 作，所以此情况下next指向的元素根本就没有被删除，而是删除的它前面节点，又由
			 * 于删除了一个元素，next指向的元素的索引编号就会前移一个，所以这里需要减一，
			 * 因与上面不同的，next所指的物理位置没有发生变化，但他所指向的节点的逻辑编号
			 * 发生了变化，从2变成了1，参考下图
			 * 
			 *                     lastReturned   next
			 *                           ↓         ↓
			 * ----------+----------+---------+---------+----------
			 * |   Head  |     0    |  1(del) |    2    |    3    |
			 * ----------+----------+---------+---------+----------
			 */
			nextIndex--;

		//最后让最近一次操作指向复原，即指向header，固删除后不能马上进行删除与修改操作  
		lastReturned = header;
		expectedModCount++;
	}

	public void set(Object o) {
		/*
		 * !! 注，刚实例化的迭代器如果还没有进行后移(next)操作、或者是刚刚进行过添加操作
		 * 、又或者是刚刚进行过一次删除操作 后不能再进行修改操作了，因为上面这些操作都会使
		 * lastReturned 指向 header
		 */
		if (lastReturned == header)
			throw new IllegalStateException();
		checkForComodification();
		//修改也是修改最近一次next或previous操作返回的元素，即lastReturned指向的元素
		lastReturned.element = o;
	}

	public void add(Object o) {
		checkForComodification();
		//最后让最近一次操作指向lastReturned位置复原，即指向头，固添加后不能马上进行删除与修改操作 
		lastReturned = header;
		//在next所指节点前插入节点，插入节点后next指向还是不变
		addBefore(o, next);
		//在next节点前插入节点后虽然next还是指向原来节点，但因在前插入节点引起索引逻辑编号递增
		nextIndex++;
		expectedModCount++;
	}

	final void checkForComodification() {
		if (modCount != expectedModCount)
			throw new ConcurrentModificationException();
	}
}

 

4、迭代器操作集合限制小结

上面我们对ArrayList使用的迭代器与LinkedList使用的迭代器代码分析时，发现迭代串操作集合是有一些限制的，这些限制表现在以下几点：

• 刚实例化的迭代器如果还没有进行后移(next)操作是不能马上进行删除与修改操作的。
• 可以用迭代器对集合连续添加与修改，但不能连续删除。
• 进行添加操作后是不能立即进行删除与修改操作的。
• 进行删除操作后可以进行添加，但不能进行修改操作。
• 进行修改后是可以立即进行删除与添加操作的。

5、AbstractList中的modCount字段与其内部类Itr的expectedModCount字段作用分析

通过上面对AbstractList中的ListIterator实现与LinkedList中的ListIterator分析，我们发现它们的一些方法中使用到 expectedModCount这样一个字段，这个字段有什么作用，其实上面在分析代码时就已经简单的说明了，不过下面进一步看一看为什么？

ArrayList类继承了AbstractList类的modCount字段，每次ArrayList对象进行结构调整时（利用add方法或 remove方法增删元素），这个字段就会递增1。另外，每个迭代器实例都有一个expectedModCount字段，并初始化为modCount。当 我们用迭代器某些（next、remove、previous、set、add）方法时，这些方法都会先检查确认expectedModCount字段是 否仍然等于modCount，如果不是，说明ArrayList对象结构已经改变，这些方法会抛出 ConcurrentModificationException异常。
因为迭代器看作是集合的视图，如果集合的结构发生了变化，那么迭代器也就随之失效，就需要重建迭代器（或视图），就拿迭代器的remove方法来说，如果 在迭代通过使用next()方法已迭代出最后一元素时，此时如果调用remove操作，将会删除集合中的最后一个元素，但如果在删除之前，其他程序通过集 合本身把最后一个元素给删除了，这时如果不检测就操作会地址越界，而其他迭代操作也会有这样或那样的问题，所以当集合结构发生改变后，迭代器就应该失效， 这种失效正是使用检测AbstractList类的modCount字段与迭代器中的expectedModCount字段是否相等来实现的。

 

当然，我们通过查看AbstractList抽象类中的两个内部迭代器Itr与ListItr的 实现，可以看出通过迭代器某些方法（remove、set、add）改变集合结构后，都会把expectedModCount置为 modCount（？ListItr的set()方法expectedModCount = modCount赋值语句是多余的，因为迭代器的set方法根本没有改变集合结构？），因为这是通过迭代器相应方法来改变的集合结构，这种结构的改变是迭 代器自已可控制，所以下次再使用迭代器这些方法继续改变集合对象结构时，不会出现ConcurrentModificationException异常。

 

所以，一旦你开始对一个ArrayList对象进行迭代，就不能再修改这个ArrayList对 象结构（利用迭代器里进行修改本身除外），否则，可能损害迭代器的完整性，因此抛ConcurrentModificationException异常， 这样的迭代器是“即时错误”的：只要觉得迭代器可能出错，立即抛异常，如果等到确认迭代器出错再处理，实际上可能很难做出判断了。

评论

4 楼 tangyongzhe 2014-12-10  

请问LZ用的什么画图工具画出的链表结构

3 楼 junJZ_2008 2010-04-27  

diandian 写道

4、迭代器操作集合限制小结

上面我们对ArrayList使用的迭代器与LinkedList使用的迭代器代码分析时，发现迭代串操作集合是有一些限制的，这些限制表现在以下几点：

    * 刚实例化的迭代器如果还没有进行后移(next)操作是不能马上进行删除与修改操作的。
    * 可以用迭代器对集合连续添加与修改，但不能连续删除。
    * 进行添加操作后是不能立即进行删除与修改操作的。
    * 进行删除操作后可以进行添加，但不能进行修改操作。
    * 进行修改后是可以立即进行删除与添加操作的。
朋友-看你对API源码的剖析还不错，我看对迭代器操作这里应该还要补充一下：
就是在
　　　　　　　　while (lt.hasPrevious()) {
String str = (String) lt.previous();
lt.remove();//这里没起作用
System.out.println("pre: " + str);
}
对ListIterator进行倒序的时候是不能对迭代器中的元素进行修改、删除的，不知道你发现没有，至于为什么会这样暂时还不是很清楚（正向迭代的时候是可以的），如果朋友知道还望指教。

反向也是可以的，请看：

class Test {
	public static void main(String[] args) {

		LinkedList list = new LinkedList();
		list.add("1");
		list.add("2");
		list.add("3");
		list.add("4");
		
		ListIterator it = list.listIterator(4);
		
		System.out.println("删除前："+list);
		while (it.hasPrevious()) {
			String str = (String) it.previous();
			it.remove();//这里没起作用
			System.out.println("pre: " + str);
		}
		System.out.println("删除后："+list);

		
	}
}

输出如下：

删除前：[1, 2, 3, 4]
pre: 4
pre: 3
pre: 2
pre: 1
删除后：[]

你的不能删除原因可能是你没有将 nextIndex 移到链表的最后，采用 如 ListIterator it = list.listIterator(); 的形式得到的迭代器时 nextIndex本身就在链表的最前，所以你不能删除吧？

2 楼 xiangdefei 2010-04-27  

楼主，好强哦，佩服。

1 楼 diandian 2010-04-27  

4、迭代器操作集合限制小结

上面我们对ArrayList使用的迭代器与LinkedList使用的迭代器代码分析时，发现迭代串操作集合是有一些限制的，这些限制表现在以下几点：

    * 刚实例化的迭代器如果还没有进行后移(next)操作是不能马上进行删除与修改操作的。
    * 可以用迭代器对集合连续添加与修改，但不能连续删除。
    * 进行添加操作后是不能立即进行删除与修改操作的。
    * 进行删除操作后可以进行添加，但不能进行修改操作。
    * 进行修改后是可以立即进行删除与添加操作的。
朋友-看你对API源码的剖析还不错，我看对迭代器操作这里应该还要补充一下：
就是在
　　　　　　　　while (lt.hasPrevious()) {
String str = (String) lt.previous();
lt.remove();//这里没起作用
System.out.println("pre: " + str);
}
对ListIterator进行倒序的时候是不能对迭代器中的元素进行修改、删除的，不知道你发现没有，至于为什么会这样暂时还不是很清楚（正向迭代的时候是可以的），如果朋友知道还望指教。