JDK源码分析-ArrayList分析

花了两个晚上的时间研究了一下ArrayList的源码, ArrayList 继承自AbstractList 并且实现了List, RandomAccess, Cloneable, Serializable 通过实现这三个接口 就具备了他们的功能 RandomAccess 用来表明其支持快速(通常是固定时间)随机访问 Cloneable可以克隆对象 Serializable 对象序列化就是把一个对象变为二进制的数据流的一种方法,通过对象序列化可以方便地实现对象的传输和存储,Serializable 接口里面什么都没有,只是用来标识的,只有实现了该接口 就表名可以被序列化

下面看看ArrayList 整体架构。

集合的顶层接口就是Collection,它继承Iterable(Iterator是一个接口,它是集合的迭代器。集合可以通过Iterator去遍历集合中的元素。Iterator提供的API接口,包括:是否存在下一个元素、获取下一个元素、删除当前元素。),Collection是高度抽象出来的集合,它包含了集合的基本操作和属性。定义了一些方法,见如下源码 看一下它的源码

package java.util;

public interface Collection<E> extends Iterable<E> {

    //返回此 collection 中的元素数
    int size();

    //如果此 collection 不包含元素,则返回 true
    boolean isEmpty();

    // 如果此 collection 包含指定的元素,则返回 true。
    boolean contains(Object o);

    //返回在此 collection 的元素上进行迭代的迭代器
    Iterator<E> iterator();

    //返回包含此 collection 中所有元素的数组
    Object[] toArray();

    //返回包含此 collection 中所有元素的数组;返回数组的运行时类型与指定数组的运行时类型相同
    <T> T[] toArray(T[] a);

    /**确保此 collection 包含指定的元素(可选操作)。
    *如果此 collection 由于调用而发生更改,则返回 true。
    */(如果此 collection 不允许有重复元素,并且已经包含了指定的元素,则返回 false。)
    boolean add(E e);

    //从此 collection 中移除指定元素的单个实例
    boolean remove(Object o);

    //如果此 collection 包含指定 collection 中的所有元素,则返回 true
    boolean containsAll(Collection<?> c);

    //将指定 collection 中的所有元素都添加到此 collection 中
    boolean addAll(Collection<? extends E> c);

    //移除此 collection 中那些也包含在指定 collection 中的所有元素
    boolean removeAll(Collection<?> c);

    //仅保留此 collection 中那些也包含在指定 collection 的元素
    boolean retainAll(Collection<?> c);

    //移除此 collection 中的所有元素
    void clear();

    //比较此 collection 与指定对象是否相等。 
    boolean equals(Object o); 

    //返回此 collection 的哈希码值
    int hashCode();
}

ArrayList 继承自AbstractList ,来看看AbstractList

AbstractList是一个继承于AbstractCollection,并且实现List接口的抽象类。它实现了List中除size()、get(int location)之外的函数。 AbstractList的主要作用:它实现了List接口中的大部分函数。从而方便其它类继承List。 另外,和AbstractCollection相比,AbstractList抽象类中,实现了iterator()接口。

AbstractList源码如下:

/*
 *此类提供 List 接口的骨干实现,以最大限度地减少实现“随机访问”数据存储(如数组)支持的该接口所需的工作。
 *AbstractList是一个继承于AbstractCollection,并且实现List接口的抽象类。它实现了List中除size()、get(int location)之外的函数。
 *AbstractList的主要作用:它实现了List接口中的大部分函数。从而方便其它类继承List。
 *另外,和AbstractCollection相比,AbstractList抽象类中,实现了iterator()接口。 
 */

package java.util;

public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {
    /**
     *唯一的构造方法。(由子类构造方法调用,通常是隐式的。) 
     */
    protected AbstractList() {
    }


    //将指定的元素添加到此列表的尾部
    public boolean add(E e) {
        add(size(), e);//调用了在指定位置添加元素的方法
        return true;
    }

    //返回列表中指定位置的元素。
    abstract public E get(int index);

    //用指定元素替换列表中指定位置的元素
    public E set(int index, E element) {
        throw new UnsupportedOperationException();
    }

   //在列表的指定位置插入指定元素
    public void add(int index, E element) {
        throw new UnsupportedOperationException();
    }

    //移除列表中指定位置的元素
    public E remove(int index) {
        throw new UnsupportedOperationException();
    }


   //返回此列表中第一次出现的指定元素的索引;如果此列表不包含该元素,则返回 -1。
    public int indexOf(Object o) {
        ListIterator<E> it = listIterator();
        if (o==null) {
            while (it.hasNext())
                if (it.next()==null)
                    return it.previousIndex();
        } else {
            while (it.hasNext())
                if (o.equals(it.next()))
                    return it.previousIndex();
        }
        return -1;
    }

    //返回此列表中最后出现的指定元素的索引;如果列表不包含此元素,则返回 -1
    public int lastIndexOf(Object o) {
        ListIterator<E> it = listIterator(size());
        if (o==null) {
            while (it.hasPrevious())
                if (it.previous()==null)
                    return it.nextIndex();
        } else {
            while (it.hasPrevious())
                if (o.equals(it.previous()))
                    return it.nextIndex();
        }
        return -1;
    }


   //从此列表中移除所有元素
    public void clear() {
        removeRange(0, size());
    }

   //将指定 collection 中的所有元素都插入到列表中的指定位置
    public boolean addAll(int index, Collection<? extends E> c) {
        rangeCheckForAdd(index);
        boolean modified = false;
        for (E e : c) {
            add(index++, e);
            modified = true;
        }
        return modified;
    }


    //返回在此列表的元素上进行迭代的迭代器
    public Iterator<E> iterator() {
        return new Itr();
    }

    //返回此列表元素的列表迭代器
    public ListIterator<E> listIterator() {
        return listIterator(0);
    }

    //返回列表中元素的列表迭代器(按适当顺序),从列表的指定位置开始
    public ListIterator<E> listIterator(final int index) {
        rangeCheckForAdd(index);

        return new ListItr(index);
    }
    //内部类
    private class Itr implements Iterator<E> {
        /**
         * Index of element to be returned by subsequent call to next.
         */
        int cursor = 0;

        /**
         * Index of element returned by most recent call to next or
         * previous.  Reset to -1 if this element is deleted by a call
         * to remove.
         */
        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();
        }
    }
    //内部类
    private class ListItr extends Itr implements ListIterator<E> {
        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();
            }
        }
    }

    //返回列表中指定的 fromIndex(包括 )和 toIndex(不包括)之间的部分视图。(
    public List<E> subList(int fromIndex, int toIndex) {
        return (this instanceof RandomAccess ?
                new RandomAccessSubList<>(this, fromIndex, toIndex) :
                new SubList<>(this, fromIndex, toIndex));
    }

    //将指定的对象与此列表进行相等性比较。
    public boolean equals(Object o) {
        if (o == this)
            return true;
        if (!(o instanceof List))
            return false;

        ListIterator<E> e1 = listIterator();
        ListIterator e2 = ((List) o).listIterator();
        while (e1.hasNext() && e2.hasNext()) {
            E o1 = e1.next();
            Object o2 = e2.next();
            if (!(o1==null ? o2==null : o1.equals(o2)))
                return false;
        }
        return !(e1.hasNext() || e2.hasNext());
    }

    //返回此列表的哈希码值
    public int hashCode() {
        int hashCode = 1;
        for (E e : this)
            hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());
        return hashCode;
    }

    //从此列表中移除索引在 fromIndex(包括)和 toIndex(不包括)之间的所有元素
    protected void removeRange(int fromIndex, int toIndex) {
        ListIterator<E> it = listIterator(fromIndex);
        for (int i=0, n=toIndex-fromIndex; i<n; i++) {
            it.next();
            it.remove();
        }
    }


    protected transient int modCount = 0;

    private void rangeCheckForAdd(int index) {
        if (index < 0 || index > size())
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    private String outOfBoundsMsg(int index) {
        return "Index: "+index+", Size: "+size();
    }
}

class SubList<E> extends AbstractList<E> {
    private final AbstractList<E> l;
    private final int offset;
    private int size;

    SubList(AbstractList<E> list, int fromIndex, int toIndex) {
        if (fromIndex < 0)
            throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
        if (toIndex > list.size())
            throw new IndexOutOfBoundsException("toIndex = " + toIndex);
        if (fromIndex > toIndex)
            throw new IllegalArgumentException("fromIndex(" + fromIndex +
                                               ") > toIndex(" + toIndex + ")");
        l = list;
        offset = fromIndex;
        size = toIndex - fromIndex;
        this.modCount = l.modCount;
    }

    public E set(int index, E element) {
        rangeCheck(index);
        checkForComodification();
        return l.set(index+offset, element);
    }

    public E get(int index) {
        rangeCheck(index);
        checkForComodification();
        return l.get(index+offset);
    }

    public int size() {
        checkForComodification();
        return size;
    }

    public void add(int index, E element) {
        rangeCheckForAdd(index);
        checkForComodification();
        l.add(index+offset, element);
        this.modCount = l.modCount;
        size++;
    }

    public E remove(int index) {
        rangeCheck(index);
        checkForComodification();
        E result = l.remove(index+offset);
        this.modCount = l.modCount;
        size--;
        return result;
    }

    protected void removeRange(int fromIndex, int toIndex) {
        checkForComodification();
        l.removeRange(fromIndex+offset, toIndex+offset);
        this.modCount = l.modCount;
        size -= (toIndex-fromIndex);
    }

    public boolean addAll(Collection<? extends E> c) {
        return addAll(size, c);
    }

    public boolean addAll(int index, Collection<? extends E> c) {
        rangeCheckForAdd(index);
        int cSize = c.size();
        if (cSize==0)
            return false;

        checkForComodification();
        l.addAll(offset+index, c);
        this.modCount = l.modCount;
        size += cSize;
        return true;
    }

    public Iterator<E> iterator() {
        return listIterator();
    }

    public ListIterator<E> listIterator(final int index) {
        checkForComodification();
        rangeCheckForAdd(index);

        return new ListIterator<E>() {
            private final ListIterator<E> i = l.listIterator(index+offset);

            public boolean hasNext() {
                return nextIndex() < size;
            }

            public E next() {
                if (hasNext())
                    return i.next();
                else
                    throw new NoSuchElementException();
            }

            public boolean hasPrevious() {
                return previousIndex() >= 0;
            }

            public E previous() {
                if (hasPrevious())
                    return i.previous();
                else
                    throw new NoSuchElementException();
            }

            public int nextIndex() {
                return i.nextIndex() - offset;
            }

            public int previousIndex() {
                return i.previousIndex() - offset;
            }

            public void remove() {
                i.remove();
                SubList.this.modCount = l.modCount;
                size--;
            }

            public void set(E e) {
                i.set(e);
            }

            public void add(E e) {
                i.add(e);
                SubList.this.modCount = l.modCount;
                size++;
            }
        };
    }

    public List<E> subList(int fromIndex, int toIndex) {
        return new SubList<>(this, fromIndex, toIndex);
    }

    private void rangeCheck(int index) {
        if (index < 0 || index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    private void rangeCheckForAdd(int index) {
        if (index < 0 || index > size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    private String outOfBoundsMsg(int index) {
        return "Index: "+index+", Size: "+size;
    }

    private void checkForComodification() {
        if (this.modCount != l.modCount)
            throw new ConcurrentModificationException();
    }
}

class RandomAccessSubList<E> extends SubList<E> implements RandomAccess {
    RandomAccessSubList(AbstractList<E> list, int fromIndex, int toIndex) {
        super(list, fromIndex, toIndex);
    }

    public List<E> subList(int fromIndex, int toIndex) {
        return new RandomAccessSubList<>(this, fromIndex, toIndex);
    }
}

AbstractList继承自AbstractCollection,来看看AbstractCollection吧 此类提供 Collection 接口的骨干实现,以最大限度地减少了实现此接口所需的工作

package java.util;


//此类提供 Collection 接口的骨干实现,以最大限度地减少了实现此接口所需的工作
public abstract class AbstractCollection<E> implements Collection<E> {

    protected AbstractCollection() {
    }

    //返回在此 collection 中的元素上进行迭代的迭代器。
    public abstract Iterator<E> iterator();
    //返回此 collection 中的元素数
    public abstract int size();
    //如果此 collection 不包含元素,则返回 true。 
    public boolean isEmpty() {
        return size() == 0;
    }
    /**
    *
    *如果此 collection 包含指定的元素,则返回 true。
    *更确切地讲,当且仅当此 collection 至少包含一个满足 (o==null ? e==null : o.equals(e)) 的元素 e 时,返回 true。 
    *此实现在 collection 中的元素上进行迭代,并依次检查每个元素以确定其是否与指定的元素相等。 
    */
    public boolean contains(Object o) {
        Iterator<E> it = iterator();
        if (o==null) {
            while (it.hasNext())
                if (it.next()==null)
                    return true;
        } else {
            while (it.hasNext())
                if (o.equals(it.next()))
                    return true;
        }
        return false;
    }
    //返回包含此 collection 中所有元素的数组
    public Object[] toArray() {
        Object[] r = new Object[size()];//创建一个长度为size(集合元素的个数)的数组  存集合中的所有元素
        Iterator<E> it = iterator();
        for (int i = 0; i < r.length; i++) {
            if (! it.hasNext()) // 原始数组的元素比指定的长度小 
            // copyOf(T[] original, int newLength) 复制指定的数组,以使副本具有指定的长度。
                return Arrays.copyOf(r, i); 
            r[i] = it.next();//把集合中的元素赋值给临时数组
        }
        return it.hasNext() ? finishToArray(r, it) : r; //返回临时数组
    }
    //返回包含此 collection 中所有元素的数组;类型与指定数组的运行时类型相同
    public <T> T[] toArray(T[] a) {
        int size = size();
        T[] r = a.length >= size ? a :
                  (T[])java.lang.reflect.Array
                  .newInstance(a.getClass().getComponentType(), size);
        Iterator<E> it = iterator();

        for (int i = 0; i < r.length; i++) {
            if (! it.hasNext()) { // fewer elements than expected
                if (a != r)
                    return Arrays.copyOf(r, i);
                r[i] = null; // null-terminate
                return r;
            }
            r[i] = (T)it.next();
        }
        return it.hasNext() ? finishToArray(r, it) : r;
    }

    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;


    private static <T> T[] finishToArray(T[] r, Iterator<?> it) {
        int i = r.length;
        while (it.hasNext()) {
            int cap = r.length;
            if (i == cap) {
                int newCap = cap + (cap >> 1) + 1;
                // overflow-conscious code
                if (newCap - MAX_ARRAY_SIZE > 0)
                    newCap = hugeCapacity(cap + 1);
                r = Arrays.copyOf(r, newCap);
            }
            r[i++] = (T)it.next();
        }
        // trim if overallocated
        return (i == r.length) ? r : Arrays.copyOf(r, i);
    }

    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError
                ("Required array size too large");
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

   //确保此 collection 包含指定的元素
    public boolean add(E e) {
        throw new UnsupportedOperationException();
    }

   //从此 collection 中移除指定元素的单个实例
    public boolean remove(Object o) {
        Iterator<E> it = iterator();
        if (o==null) {
            while (it.hasNext()) {
                if (it.next()==null) {
                    it.remove();
                    return true;
                }
            }
        } else {
            while (it.hasNext()) {
                if (o.equals(it.next())) {
                    it.remove();
                    return true;
                }
            }
        }
        return false;
    }


   //如果此 collection 包含指定 collection 中的所有元素,则返回 true。
    public boolean containsAll(Collection<?> c) {
        for (Object e : c)
            if (!contains(e))
                return false;
        return true;
    }

   //将指定 collection 中的所有元素都添加到此 collection 中
    public boolean addAll(Collection<? extends E> c) {
        boolean modified = false;
        for (E e : c)
            if (add(e))
                modified = true;
        return modified;
    }

   //移除此 collection 中那些也包含在指定 collection 中的所有元素
    public boolean removeAll(Collection<?> c) {
        boolean modified = false;
        Iterator<?> it = iterator();
        while (it.hasNext()) {
            if (c.contains(it.next())) {
                it.remove();
                modified = true;
            }
        }
        return modified;
    }

   //仅保留此 collection 中那些也包含在指定 collection 的元素
    public boolean retainAll(Collection<?> c) {
        boolean modified = false;
        Iterator<E> it = iterator();
        while (it.hasNext()) {
            if (!c.contains(it.next())) {
                it.remove();
                modified = true;
            }
        }
        return modified;
    }

    //移除此 collection 中的所有元素
    public void clear() {
        Iterator<E> it = iterator();
        while (it.hasNext()) {
            it.next();
            it.remove();
        }
    }


   //返回此 collection 的字符串表示形式
    public String toString() {
        Iterator<E> it = iterator();
        if (! it.hasNext())
            return "[]";

        StringBuilder sb = new StringBuilder();
        sb.append('[');
        for (;;) {
            E e = it.next();
            sb.append(e == this ? "(this Collection)" : e);
            if (! it.hasNext())
                return sb.append(']').toString();
            sb.append(',').append(' ');
        }
    }

}

ArrayList和AbstractList都实现了List接口,List继承自Collection ,它自然就包含了Collection中的全部函数接口;由于List是有序队列,它也额外的有自己的API接口。主要有“添加、删除、获取、修改指定位置的元素”、“获取List中的子队列”等。

下面看源码

//List继承自Collection    而Collection又继承自 Iterable
package java.util;  
public interface List<E> extends Collection<E> {

    //返回列表中的元素数。
    int size();

    //判断列表是否为空 如果列表不包含元素,则返回 true。
    boolean isEmpty();

   //判断列表中是否包含某个元素  如果列表包含指定的元素,则返回 true。
    boolean contains(Object o);

    //返元素迭代的迭代器。
    Iterator<E> iterator();

   //  返回列表中的所有元素的数组
    Object[] toArray();

    //  返回列表中的所有元素的数组,返回数组的运行时类型是指定数组的运行时类型。
    <T> T[] toArray(T[] a);

    //向列表的尾部添加指定的元素
    boolean add(E e);

    //从此列表中移除第一次出现的指定元素(如果存在)
    boolean remove(Object o);

    //如果列表包含指定 collection 的所有元素,则返回 true。
    boolean containsAll(Collection<?> c);

    //添加指定 collection 中的所有元素到此列表的结尾,
    boolean addAll(Collection<? extends E> c);

    //将指定 collection 中的所有元素都插入到列表中的指定位置
    boolean addAll(int index, Collection<? extends E> c);

    //从列表中移除指定 collection 中包含的其所有元素
    boolean removeAll(Collection<?> c);

    //仅在列表中保留指定 collection 中所包含的元素
    boolean retainAll(Collection<?> c);

    //从列表中移除所有元素
    void clear();

    //比较指定的对象与列表是否相等
    boolean equals(Object o);

    //返回列表的哈希码值
    int hashCode();

    //返回列表中指定位置的元素。 
    E get(int index);

    //用指定元素替换列表中指定位置的元素
    E set(int index, E element);

   //在列表的指定位置插入指定元素
    void add(int index, E element);

    //移除列表中指定位置的元素
    E remove(int index);

    //返回此列表中第一次出现的指定元素的索引
    int indexOf(Object o);

    //返回此列表中最后出现的指定元素的索引;如果列表不包含此元素,则返回 -1。
    int lastIndexOf(Object o);

    //返回此列表元素的列表迭代器
    ListIterator<E> listIterator(int index);

    //返回列表中指定的 fromIndex(包括 )和 toIndex(不包括)之间的部分视图。
    List<E> subList(int fromIndex, int toIndex);
}

绕了这么久,还没有到正题ArrayList,下面马上分析ArrayList,没办法,要分析他,自然得分析他的前因后果,得知道他从哪来,所有介绍了一下他的父类以及和他的父类有关的接口和类 ArrayList包含了两个重要的对象:elementData 和 size。

(01) elementData 是”Object[] 类型的数组”,它保存了添加到ArrayList中的元素。实际上,elementData是个动态数组,我们能通过构造函数 ArrayList(int initialCapacity)来执行它的初始容量为initialCapacity;如果通过不含参数的构造函数ArrayList()来创建 ArrayList,则elementData的容量默认是10。elementData数组的大小会根据ArrayList容量的增长而动态的增长,具 体的增长方式,请参考源码分析中的ensureCapacity()函数。

(02) size 则是动态数组的实际大小。 protected transient int modCount表示已从结构上修改 此列表的次数。从结构上修改是指更改列表的大小,或者打乱列表,从而使正在进行的迭代产生错误的结果。 此字段由 iterator 和 listIterator 方法返回的迭代器和列表迭代器实现使用。如果意外更改了此字段中的值,则迭代器(或列表迭代器)将抛出 ConcurrentModificationException 来响应next、remove、previous、set 或 add 操作。在迭代期间面临并发修改时,它提供了快速失败 行为,而不是非确定性行为

还有一个从父类继承的属性需要注意一下 protected transient int modCount 从父类AbstractList继承而来 已从结构上修改 此列表的次数。从结构上修改是指更改列表的大小,或者打乱列表,从而使正在进行的迭代产生错误的结果。此字段由 iterator 和 listIterator 方法返回的迭代器和列表迭代器实现使用。 如果意外更改了此字段中的值,则迭代器(或列表迭代器)将抛出 ConcurrentModificationException 来响应 next、remove、previous、set 或 add 操作。在迭代期间面临并发修改时,它提供了快速失败 行为,而不是非确定性行为。

下面直接看源码,所有分析都在源码的注释中

//RandomAccess 用来表明其支持快速(通常是固定时间)随机访问
//Cloneable可以克隆对象
//Serializable 对象序列化就是把一个对象变为二进制的数据流的一种方法,通过对象序列化可以方便地实现对象的传输和存储
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {

    // protected transient int modCount 从父类AbstractList继承而来 已从结构上修改 此列表的次数。从结构上修改是指更改列表的大小,或者打乱列表,
    // 从而使正在进行的迭代产生错误的结果。
    // 此字段由 iterator 和 listIterator 方法返回的迭代器和列表迭代器实现使用。
    // 如果意外更改了此字段中的值,则迭代器(或列表迭代器)将抛出 ConcurrentModificationException 来响应
    // next、remove、previous、set 或 add 操作。在迭代期间面临并发修改时,它提供了快速失败 行为,而不是非确定性行为。
    private static final long serialVersionUID = 8683452581122892189L;

    /**
     * transient的作用 一个对象只要实现了Serilizable接口,这个对象就可以被序列化,
     * java的这种序列化模式为开发者提供了很多便利,可以不必关系具体序列化的过程,
     * 只要这个类实现了Serilizable接口,这个的所有属性和方法都会自动序列化。 但是有种情况是有些属性是不需要序列号的,所以就用到这个关键字。
     * 只需要实现Serilizable接口, 将不需要序列化的属性前添加关键字transient,序列化对象的时候,
     * 这个属性就不会序列化到指定的目的地中。 The capacity of the ArrayList is the length of this
     * array buffer.
     */
    private transient Object[] elementData; // Object[]类型的数组,保存了添加到ArrayList中的元素。ArrayList的容量是该Object[]类型数组的长度

    /**
     * The size of the ArrayList (the number of elements it contains).
     *
     * @serial
     */
    private int size;// 数组实际长度的大小 小于elementData.length

    /**
     * 构造一个具有指定初始容量的空列表。 参数:initialCapacity - 列表的初始容量
     */
    public ArrayList(int initialCapacity) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
        this.elementData = new Object[initialCapacity];
    }

    /**
     * 构造一个初始容量为 10 的空列表
     */
    public ArrayList() {
        this(10);
    }

    /**
     * 构造一个包含指定 collection 的元素的列表
     */
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        size = elementData.length;
        // c.toArray 可能不是返回一个 Object[]
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    }

    /**
     * 将底层数组的容量调整为当前实际元素的大小,来释放空间
     */
    public void trimToSize() {
        modCount++;
        //当前数组的容量
        int oldCapacity = elementData.length;
         // 如果当前实际元素大小 小于 当前数组的容量,则进行缩容
        if (size < oldCapacity) {
            elementData = Arrays.copyOf(elementData, size);
        }
    }

    /**
     * 拓容 
     * 如有必要,增加此 ArrayList 实例的容量,以确保它至少能够容纳最小容量参数所指定的元素数。
     * 
     * @param minCapacity
     *            minCapacity - 所需的最小容量
     */
    public void ensureCapacity(int minCapacity) {
        if (minCapacity > 0)
            ensureCapacityInternal(minCapacity);
    }
    //数组容量检查,不够时则进行扩容
    private void ensureCapacityInternal(int minCapacity) {
        modCount++;
        // overflow-conscious code
        // 最小需要的容量大于当前数组的长度则进行扩容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

    /**
     * The maximum size of array to allocate. Some VMs reserve some header words
     * in an array. Attempts to allocate larger arrays may result in
     * OutOfMemoryError: Requested array size exceeds VM limit
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    /**
     * 数组拓容  
     * minCapacity 最小需要的容量
     */
    private void grow(int minCapacity) {
        // overflow-conscious code
        //当前数组的容量
        int oldCapacity = elementData.length;
        //拓容数组容量
        int newCapacity = oldCapacity + (oldCapacity >> 1);
       // 如果新扩容的数组长度还是比最小需要的容量小,则以最小需要的容量为长度进行扩容
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        //如果最小需要的容量比数组定义好的最大长度还大,则进行紧急拓容
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
          // 进行数据拷贝,Arrays.copyOf底层实现是System.arrayCopy()
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
    //紧急拓容 直接把数组容量拓展到Integer.MAX_VALUE
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
    }

    /**
     * Returns the number of elements in this list.
     *
     * @return the number of elements in this list
     */
    public int size() {
        return size;
    }

    /**
     * Returns <tt>true</tt> if this list contains no elements.
     *
     * @return <tt>true</tt> if this list contains no elements
     */
    public boolean isEmpty() {
        return size == 0;
    }

    // 如果此列表中包含指定的元素,则返回 true。
    public boolean contains(Object o) {
        return indexOf(o) >= 0;
    }

    // 返回此列表中首次出现的指定元素的索引,或如果此列表不包含元素,则返回 -1
    public int indexOf(Object o) {
        if (o == null) {
            for (int i = 0; i < size; i++)
                if (elementData[i] == null)
                    return i;
        } else {
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

    // 返回此列表中最后一次出现的指定元素的索引,或如果此列表不包含索引,则返回 -1
    public int lastIndexOf(Object o) {
        if (o == null) {
            for (int i = size - 1; i >= 0; i--)
                if (elementData[i] == null)
                    return i;
        } else {
            for (int i = size - 1; i >= 0; i--)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

    /**
     * 返回此 ArrayList 实例的浅表副本
     */
    public Object clone() {
        try {
            @SuppressWarnings("unchecked")
            ArrayList<E> v = (ArrayList<E>) super.clone();
            v.elementData = Arrays.copyOf(elementData, size);
            v.modCount = 0;
            return v;
        } catch (CloneNotSupportedException e) {
            // this shouldn't happen, since we are Cloneable
            throw new InternalError();
        }
    }

    /**
     * 返回包含此列表中所有元素的数组
     */
    public Object[] toArray() {
        return Arrays.copyOf(elementData, size);
    }

    /**
     * 返回包含此列表中所有元素的数组;返回数组的运行时类型是指定数组的运行时类型
     */
    @SuppressWarnings("unchecked")
    public <T> T[] toArray(T[] a) {
        if (a.length < size)
            // Make a new array of a's runtime type, but my contents:
            return (T[]) Arrays.copyOf(elementData, size, a.getClass());
        System.arraycopy(elementData, 0, a, 0, size);
        if (a.length > size)// 数组的长度比列表的元素数量多
            a[size] = null;// 多余的用null填充
        return a;
    }

    // Positional Access Operations取出elementData数组的下标为index的element

    @SuppressWarnings("unchecked")
    //返回index所在位置的元素的函数
    E elementData(int index) {
        return (E) elementData[index];
    }

    /**
     * 返回此列表中指定位置上的元素
     */
    public E get(int index) {
        //数组越界检查
        rangeCheck(index);
        //返回index所在位置的元素
        return elementData(index);
    }

    /**
     * 用指定的元素替代此列表中指定位置上的元素。
     */
    public E set(int index, E element) {
        //数组越界检查
        rangeCheck(index);
        //  取出要更新位置的元素,供返回使用
        E oldValue = elementData(index);
        // 将e赋值到该位置
        elementData[index] = element;
        //返回旧元素
        return oldValue;
    }

    /**
     * 将指定的元素添加到此列表的尾部。
     */
    public boolean add(E e) {
        // 数组拓容
        ensureCapacityInternal(size + 1); // Increments modCount!!
        // 将e放到列表尾部 容量加1
        elementData[size++] = e;
        return true;
    }

    /**
     * 将指定的元素插入此列表中的指定位置。
     */
    public void add(int index, E element) {
        //// 判断索引是否越界。
        rangeCheckForAdd(index);
        // 数组拓容
        ensureCapacityInternal(size + 1); // Increments modCount!!
        // 对数组进行复制处理,目的就是空出index的位置插入element,并将index后的元素位移一个位置
        System.arraycopy(elementData, index, elementData, index + 1, size - index);
        // 将指定的index位置赋值为element
        elementData[index] = element;
        // 容量加1
        size++;
    }

    /**
     * 移除此列表中指定位置上的元素。向左移动所有后续元素(将其索引减 1)。
     */
    public E remove(int index) {
        // 数组越界检查
        rangeCheck(index);
        //修改次数加1
        modCount++;
        // 取出要删除位置的元素,供返回使用
        E oldValue = elementData(index);
        //  计算数组要复制的数量
        int numMoved = size - index - 1;
        if (numMoved > 0)
             // 数组复制,就是将index之后的元素往前移动一个位置
            System.arraycopy(elementData, index + 1, elementData, index, numMoved);
         // 将数组最后一个元素置空
         // 因为删除了一个元素,然后index后面的元素都向前移动了,所以最后一个就没用了
        elementData[--size] = null; // size减一  让gc尽快回收 Let gc do its work
        return oldValue;
    }

    /**
     * 移除此列表中首次出现的指定元素(如果存在)。如果列表不包含此元素,则列表不做改动
     */
    public boolean remove(Object o) {
        // 对要删除的元素进行null判断
        // 对数据元素进行遍历查找,直到找到第一个要删除的元素,删除后进行返回,
        //如果要删除的元素正好是最后一个 ,时间复杂度可达O(n)
        if (o == null) {
            for (int index = 0; index < size; index++)
                //null值不能用equals比较  要用==比较
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true;
                }
        } else {
            for (int index = 0; index < size; index++)
                //比较对象是否相等
                if (o.equals(elementData[index])) {
                    //快速删除 skips bounds checking and does not return the value removed.
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }

    /*
     * Private remove method that skips bounds checking and does not return the
     * value removed.
     */
    private void fastRemove(int index) {
        modCount++;
        int numMoved = size - index - 1;
        if (numMoved > 0)
            //进行数组复制,将index后的元素向前移动一个位置 
            System.arraycopy(elementData, index + 1, elementData, index, numMoved);
        elementData[--size] = null; // Let gc do its work
    }

    /**
     * 移除此列表中的所有元素。此调用返回后,列表将为空。
     */
    public void clear() {
        //修改次数加1
        modCount++;
        // 遍历赋空  让垃圾回收机制回收 Let gc do its work
        for (int i = 0; i < size; i++)
            elementData[i] = null;
        //size变为0
        size = 0;
    }

    /**增加一个集合元素
     * 将该 collection 中的所有元素添加到此列表的尾部
     */
    public boolean addAll(Collection<? extends E> c) {
        //将集合c转化为Object[]
        Object[] a = c.toArray();
        //得到c集合的元素的数量
        int numNew = a.length;
        //数组拓容
        ensureCapacityInternal(size + numNew); // Increments modCount
        //数组复制
        System.arraycopy(a, 0, elementData, size, numNew);
        //更新当前容器大小 ->容量变为size+numNew(添加的集合的元素的数量)
        size += numNew;
        return numNew != 0;
    }

    /**
     * 从指定的位置开始,增加一个集合的元素
     * 
     */
    public boolean addAll(int index, Collection<? extends E> c) {
        // 判断索引是否越界。
        rangeCheckForAdd(index);

        Object[] a = c.toArray();
        int numNew = a.length;
        //数组拓容
        ensureCapacityInternal(size + numNew); // Increments modCount
         // 计算需要移动的长度
        int numMoved = size - index;
        if (numMoved > 0)
            // 数组复制,空出第index到index+numNum的位置,即将数组index后的元素向右移动numNum个位置
            System.arraycopy(elementData, index, elementData, index + numNew, numMoved);
        // 将要插入的集合元素复制到数组空出的位置中
        System.arraycopy(a, 0, elementData, index, numNew);
        size += numNew;
        return numNew != 0;
    }

    /**
     * 移除列表中索引在 fromIndex(包括)和 toIndex(不包括)之间的所有元素
     */
    protected void removeRange(int fromIndex, int toIndex) {
        //修改次数加1
        modCount++;
        //复制长度
        int numMoved = size - toIndex;
        //数组复制  原理就是移动  根之前的add ,remove一样理解
        System.arraycopy(elementData, toIndex, elementData, fromIndex, numMoved);
        // Let gc do its work
        //新容量
        int newSize = size - (toIndex - fromIndex);
        //移除位置(后面一截的 比如移除了2-3的位置的 ,则4-5的元素就会前移,所以后面的不需要了)的全部赋空 让Gc回收
        while (size != newSize)
            elementData[--size] = null;
    }

    /**
     * 数组越界检查
     */
    private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    /**
     * 数组越界检查 针对 add and addAll.
     */
    private void rangeCheckForAdd(int index) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    /**
     *越界错误信息.
     */
    private String outOfBoundsMsg(int index) {
        return "Index: " + index + ", Size: " + size;
    }

    /**
     * Removes from this list all of its elements that are contained in the
     * specified collection.
     *
     * @param c
     *            collection containing elements to be removed from this list
     * @return {@code true} if this list changed as a result of the call
     * @throws ClassCastException
     *             if the class of an element of this list is incompatible with
     *             the specified collection (
     *             <a href="Collection.html#optional-restrictions">optional</a>)
     * @throws NullPointerException
     *             if this list contains a null element and the specified
     *             collection does not permit null elements (
     *             <a href="Collection.html#optional-restrictions">optional</a>
     *             ), or if the specified collection is null
     * @see Collection#contains(Object)
     */
    public boolean removeAll(Collection<?> c) {
        return batchRemove(c, false);
    }

    /**
     * 移除包含c集合中的所有元素
     */
    public boolean retainAll(Collection<?> c) {
        return batchRemove(c, true);
    }

    private boolean batchRemove(Collection<?> c, boolean complement) {
        final Object[] elementData = this.elementData;
        int r = 0, w = 0;
        boolean modified = false;
        try {
            for (; r < size; r++)
                if (c.contains(elementData[r]) == complement)
                    elementData[w++] = elementData[r];
        } finally {
            // Preserve behavioral compatibility with AbstractCollection,
            // even if c.contains() throws.
            if (r != size) {
                System.arraycopy(elementData, r, elementData, w, size - r);
                w += size - r;
            }
            if (w != size) {
                for (int i = w; i < size; i++)
                    elementData[i] = null;
                modCount += size - w;
                size = w;
                modified = true;
            }
        }
        return modified;
    }

    /**
     * elementData数组是使用 transient 修饰的,关于 transient 关键字的作用简单说就是 java自带默认机制进行序列化
     * 的时候,被其修饰的属性不需要维持。
     * 如果elementData不需要维持,那么怎么进行反序列化,又怎么保证序列化和反序列化数据的正确性?
     * 难道不需要存储?用大腿想一下那当然是不可以的嘛,既然需要存储,它是怎么实现的呢? 
     * ArrayList一定是使用了自定义的序列化方式,到底是不是这样的呢?看下面两个方法: elementData
     * 是一个数据存储数组,而数组是定长的,它会初始化一个容量, 等容量不足时再扩充容量(扩容方式为数据拷贝,后面会详细解释), 再通俗一点说就是比如
     */
    private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException {
        // Write out element count, and any hidden stuff
        int expectedModCount = modCount;
        s.defaultWriteObject();

        // Write out array length
        s.writeInt(elementData.length);

        // Write out all elements in the proper order.
        for (int i = 0; i < size; i++)
            s.writeObject(elementData[i]);

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

    }

    /**
     * Reconstitute the <tt>ArrayList</tt> instance from a stream (that is,
     * deserialize it).
     */
    private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException {
        // Read in size, and any hidden stuff
        s.defaultReadObject();

        // Read in array length and allocate array
        int arrayLength = s.readInt();
        Object[] a = elementData = new Object[arrayLength];

        // Read in all elements in the proper order.
        for (int i = 0; i < size; i++)
            a[i] = s.readObject();
    }

    /**
     * Returns a list iterator over the elements in this list (in proper
     * sequence), starting at the specified position in the list. The specified
     * index indicates the first element that would be returned by an initial
     * call to {@link ListIterator#next next}. An initial call to
     * {@link ListIterator#previous previous} would return the element with the
     * specified index minus one.
     *
     * <p>
     * The returned list iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
     *
     * @throws IndexOutOfBoundsException
     *             {@inheritDoc}
     */
    public ListIterator<E> listIterator(int index) {
        if (index < 0 || index > size)
            throw new IndexOutOfBoundsException("Index: " + index);
        return new ListItr(index);
    }

    /**
     * Returns a list iterator over the elements in this list (in proper
     * sequence).
     *
     * <p>
     * The returned list iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
     *
     * @see #listIterator(int)
     */
    public ListIterator<E> listIterator() {
        return new ListItr(0);
    }

    /**
     * Returns an iterator over the elements in this list in proper sequence.
     *
     * <p>
     * The returned iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
     *
     * @return an iterator over the elements in this list in proper sequence
     */
    public Iterator<E> iterator() {
        return new Itr();
    }

    /**
     * An optimized version of AbstractList.Itr
     */
    private class Itr implements Iterator<E> {
        int cursor; // index of next element to return
        int lastRet = -1; // index of last element returned; -1 if no such
        int expectedModCount = modCount;

        public boolean hasNext() {
            return cursor != size;
        }

        @SuppressWarnings("unchecked")
        public E next() {
            checkForComodification();
            int i = cursor;
            if (i >= size)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i + 1;
            return (E) elementData[lastRet = i];
        }

        public void remove() {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
                ArrayList.this.remove(lastRet);
                cursor = lastRet;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

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

    /**
     * An optimized version of AbstractList.ListItr
     */
    private class ListItr extends Itr implements ListIterator<E> {
        ListItr(int index) {
            super();
            cursor = index;
        }

        public boolean hasPrevious() {
            return cursor != 0;
        }

        public int nextIndex() {
            return cursor;
        }

        public int previousIndex() {
            return cursor - 1;
        }

        @SuppressWarnings("unchecked")
        public E previous() {
            checkForComodification();
            int i = cursor - 1;
            if (i < 0)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i;
            return (E) elementData[lastRet = i];
        }

        public void set(E e) {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
                ArrayList.this.set(lastRet, e);
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

        public void add(E e) {
            checkForComodification();

            try {
                int i = cursor;
                ArrayList.this.add(i, e);
                cursor = i + 1;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }
    }

    //截取 fromIndex到 fromIndex之间的元素
    public List<E> subList(int fromIndex, int  fromIndex) {
        //位置检查
        subListRangeCheck(fromIndex, toIndex, size);
        //内部类 继承父类并实现了方法
        return new SubList(this, 0, fromIndex, toIndex);
    }
    //位置检查
    static void subListRangeCheck(int fromIndex, int toIndex, int size) {
        if (fromIndex < 0)
            throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
        if (toIndex > size)
            throw new IndexOutOfBoundsException("toIndex = " + toIndex);
        if (fromIndex > toIndex)
            throw new IllegalArgumentException("fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
    }

    private class SubList extends AbstractList<E> implements RandomAccess {
        private final AbstractList<E> parent;
        private final int parentOffset;
        private final int offset;
        int size;

        SubList(AbstractList<E> parent, int offset, int fromIndex, int toIndex) {
            this.parent = parent;
            this.parentOffset = fromIndex;
            this.offset = offset + fromIndex;
            this.size = toIndex - fromIndex;
            this.modCount = ArrayList.this.modCount;
        }

        public E set(int index, E e) {
            rangeCheck(index);
            checkForComodification();
            E oldValue = ArrayList.this.elementData(offset + index);
            ArrayList.this.elementData[offset + index] = e;
            return oldValue;
        }

        public E get(int index) {
            rangeCheck(index);
            checkForComodification();
            return ArrayList.this.elementData(offset + index);
        }

        public int size() {
            checkForComodification();
            return this.size;
        }

        public void add(int index, E e) {
            rangeCheckForAdd(index);
            checkForComodification();
            parent.add(parentOffset + index, e);
            this.modCount = parent.modCount;
            this.size++;
        }

        public E remove(int index) {
            rangeCheck(index);
            checkForComodification();
            E result = parent.remove(parentOffset + index);
            this.modCount = parent.modCount;
            this.size--;
            return result;
        }

        protected void removeRange(int fromIndex, int toIndex) {
            checkForComodification();
            parent.removeRange(parentOffset + fromIndex, parentOffset + toIndex);
            this.modCount = parent.modCount;
            this.size -= toIndex - fromIndex;
        }

        public boolean addAll(Collection<? extends E> c) {
            return addAll(this.size, c);
        }

        public boolean addAll(int index, Collection<? extends E> c) {
            rangeCheckForAdd(index);
            int cSize = c.size();
            if (cSize == 0)
                return false;

            checkForComodification();
            parent.addAll(parentOffset + index, c);
            this.modCount = parent.modCount;
            this.size += cSize;
            return true;
        }

        public Iterator<E> iterator() {
            return listIterator();
        }

        public ListIterator<E> listIterator(final int index) {
            checkForComodification();
            rangeCheckForAdd(index);
            final int offset = this.offset;

            return new ListIterator<E>() {
                int cursor = index;
                int lastRet = -1;
                int expectedModCount = ArrayList.this.modCount;

                public boolean hasNext() {
                    return cursor != SubList.this.size;
                }

                @SuppressWarnings("unchecked")
                public E next() {
                    checkForComodification();
                    int i = cursor;
                    if (i >= SubList.this.size)
                        throw new NoSuchElementException();
                    Object[] elementData = ArrayList.this.elementData;
                    if (offset + i >= elementData.length)
                        throw new ConcurrentModificationException();
                    cursor = i + 1;
                    return (E) elementData[offset + (lastRet = i)];
                }

                public boolean hasPrevious() {
                    return cursor != 0;
                }

                @SuppressWarnings("unchecked")
                public E previous() {
                    checkForComodification();
                    int i = cursor - 1;
                    if (i < 0)
                        throw new NoSuchElementException();
                    Object[] elementData = ArrayList.this.elementData;
                    if (offset + i >= elementData.length)
                        throw new ConcurrentModificationException();
                    cursor = i;
                    return (E) elementData[offset + (lastRet = i)];
                }

                public int nextIndex() {
                    return cursor;
                }

                public int previousIndex() {
                    return cursor - 1;
                }

                public void remove() {
                    if (lastRet < 0)
                        throw new IllegalStateException();
                    checkForComodification();

                    try {
                        SubList.this.remove(lastRet);
                        cursor = lastRet;
                        lastRet = -1;
                        expectedModCount = ArrayList.this.modCount;
                    } catch (IndexOutOfBoundsException ex) {
                        throw new ConcurrentModificationException();
                    }
                }

                public void set(E e) {
                    if (lastRet < 0)
                        throw new IllegalStateException();
                    checkForComodification();

                    try {
                        ArrayList.this.set(offset + lastRet, e);
                    } catch (IndexOutOfBoundsException ex) {
                        throw new ConcurrentModificationException();
                    }
                }

                public void add(E e) {
                    checkForComodification();

                    try {
                        int i = cursor;
                        SubList.this.add(i, e);
                        cursor = i + 1;
                        lastRet = -1;
                        expectedModCount = ArrayList.this.modCount;
                    } catch (IndexOutOfBoundsException ex) {
                        throw new ConcurrentModificationException();
                    }
                }

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

        public List<E> subList(int fromIndex, int toIndex) {
            subListRangeCheck(fromIndex, toIndex, size);
            return new SubList(this, offset, fromIndex, toIndex);
        }

        private void rangeCheck(int index) {
            if (index < 0 || index >= this.size)
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }

        private void rangeCheckForAdd(int index) {
            if (index < 0 || index > this.size)
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }

        private String outOfBoundsMsg(int index) {
            return "Index: " + index + ", Size: " + this.size;
        }

        private void checkForComodification() {
            if (ArrayList.this.modCount != this.modCount)
                throw new ConcurrentModificationException();
        }
    }
}

对于迭代器Iterable的实现没有做分析,看了一下,内容比较多,以后有时间再去看看,当中涉及到了设计模式,可以看一下我以前的 Java设计模式(十六)—-迭代子模式

分析源码真的耗时间,耗了两个大晚上加一上午的时间,如果大家觉得我的理解哪里不恰当,欢迎大家提出意见,我们一起进步。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Bingo的深度学习杂货店

Q108 Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a hei...

3223
来自专栏机器学习和数学

[算法与数据结构] 《算法导论》堆排序笔记

堆排序的实现是靠叫做“堆”的数据结构来实现的。所以学习堆排序,首先要了解什么是堆 堆 堆是一个数组,每个结点表示数组中的一个元素,堆可以看做是一个近似的完全二叉...

3109
来自专栏java小白

ArrayList源码详解

1735
来自专栏JavaEdge

二叉树的常用算法递归2 非递归3 小结4 实战coding5序列化和反序列化判断一棵二叉树是否是平衡二叉树判断一棵树是否是搜索二叉树、判断一棵树是否是完全二叉树

5599
来自专栏用户画像

6.3.1 B树及其基本操作

B树,又称多路平衡查找树,B树中所有节点的孩子结点数的最大值成为B树的阶,通常用m表示。一棵m阶B树或为空树,或为满足如下特性的m叉树:

911
来自专栏java技术学习之道

Java进阶--深入理解ArrayList实现原理

1203
来自专栏Hongten

ArrayList, LinkedList, Vector - dudu:史上最详解

ArrayList, LinkedList, Vector - dudu:史上最详解

933
来自专栏Java后端技术

一道面试题引发的思考

为什么呢?那么我们怎么来发现它背后的秘密呢?答案只有一个:那就是通过源码来解惑(ArrayList部分源码)。

690
来自专栏前端说吧

JS - 二叉树算法实现与遍历 (更新中...)

3958
来自专栏俞其荣的博客

ArrayList内部原理解析Header源码分析Footer

2698

扫码关注云+社区

领取腾讯云代金券