Java 7源码分析第8篇 - List集合基于数组的实现 - JAVA

List可能是我们在项目开发中用的最多的集合了，List集合的特性是集合中的元素有序（保持添加元素的顺序）、内部的数据可以重复（但是null值至多只有一个）。

查找集合框架图后可知，具体的List实现类继承了AbstractCollection抽象类并且实现了List接口。

1、具体实现类的直接抽象类 AbstractList

在AbstractList中有两个重要的内部类，由这两个内部类来完成元素的遍历。其类的框架图如下所示。

Itr实现了IteratZ http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcr3Tv9qjrLKittS907/a1tC2qNLltcS3vbeovfjQ0MHLyrXP1qOsvt/M5bT6wuvI58/Co7oKPHA+PC9wPgo8cHJlIGNsYXNzPQ=="brush:java;">private class Itr implements Iterator { int cursor = 0; int lastRet = -1; /** * 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; public boolean hasNext() { return cursor != size(); } 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(); } } final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); } }//end class这个类中主要实现了Iterator接口中定义的三个方法，如果一个AbstractList抽象类的具体实现类集合只是想要遍历其中的元素，则可以通过方法获取到这个私有类的实例，然后调用相应方法遍历即可。获取的方法如下：

    // Iterators
    public Iterator
   
     iterator() {
        return new Itr();
    }
    public ListIterator
    
      listIterator() { return listIterator(0); } public ListIterator
     
       listIterator(final int index) { rangeCheckForAdd(index); return new ListItr(index); }

还有一个私有的内部类ListIterator，源代码如下：

 private class ListItr extends Itr implements ListIterator
   
     {
        ListItr(int index) {
            cursor = index;
        }
        public boolean hasPrevious() {
            return cursor != 0;
        }
        public E previous() {
            checkForComodification();
            try {
                int i = cursor - 1;
                E previous = get(i);
                lastRet = cursor = i;
                return previous;
            } catch (IndexOutOfBoundsException e) {
                checkForComodification();
                throw new NoSuchElementException();
            }
        }
        public int nextIndex() {
            return cursor;
        }
        public int previousIndex() {
            return cursor-1;
        }
        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();
            }
        }
    }//end class

可以看到，这个集合添加了一些新的方法，包括操作游标的nextIndex()和previousIndex()方法，也支持当前元素向前向后查找元素。但是同时又一次定义了set()和add()方法，AbstractList类中已经提供了这两个方法，为什么在这里还要提供这两个方法呢？细心的读者可以发现，每次在执行这些方法执行前，都要调用checkForComodificaton()，这个方法在Itr类中实现，主要功能就是检查expectedModCount变量和modCount变量是否相等，不相等就抛出ConcurrentModificationException异常。

什么意思呢？举个例子：

ArrayList
   
      aList=new ArrayList
    
     (); aList.add("a"); aList.add("b"); aList.add("d"); ListIterator
     
       it=aList.listIterator();// 下面要获取到Iterator对象后添加元素，所以生成的必须是ListIterator对象 //aList.add("x"); // 抛出异常ConcurrentModificationException aList.remove(2); // 抛出异常ConcurrentModificationException it.add("x"); // 正常 while(it.hasNext()){ System.out.println(it.next()); }

可以看到，在获取了ListIterator实例后，aList就不可改变。当ArrayList使用了iterator()方法产生自身对应的Iterator后，只能使用Iterator自身的remove和add方法来修改ArrayList的结构，其它的修改都会引起ConcurrentModificationException异常。
ArrayList使用AbstractList.modCount(初始的默认值为0)作为结构改变的标识。在ArrayList中，凡是会引起ArrayList结构变化的方法，都会修改modCount(modCount++)，以区别是否修改了ArrayList的结构。
如果是对ArrayList的Iterator做修改，在Iterator中会重置expectedModCount=modCount，如上面ListIterator类中的set()和add()方法。这样就可以保证在生成Iterator后，只能由Iterator来修改对应的ArrayList的结构。如果此时，ArrayList修改了自身的结构，那么expectedModCoun==modCount将会返回false，从而Iterator会抛出ConcurrentModificationException异常。

再举一个例子：

public class test03 {
   public static void main(String args[]){
	   ArrayList
   
      aList=new ArrayList
    
     (); test03.test(aList); aList.add("dd"); System.out.println(aList.size());//4

Java 7源码分析第8篇 - List集合基于数组的实现(一)