java的List、ArrayList源码详解

java的List、ArrayList源码详解

List类的定义

public interface List extends Collection {
    // Query Operations
    int size();

    boolean isEmpty();

    boolean contains(Object o);

    Iterator iterator();

    Object[] toArray();

     T[] toArray(T[] a);


    // Modification Operations

    boolean add(E e);

    boolean remove(Object o);


    // Bulk Modification Operations
    boolean containsAll(Collection c);

    boolean addAll(Collection c);

    boolean retainAll(Collection c);

    default void replaceAll(UnaryOperator operator) {
        Objects.requireNonNull(operator);
        final ListIterator li = this.listIterator();
        while (li.hasNext()) {
            li.set(operator.apply(li.next()));
        }
    }

    @SuppressWarnings({"unchecked", "rawtypes"})
    default void sort(Comparator) 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(e);
        }
    }

    public Object[] toArray() {
        return Arrays.copyOf(elementData, size);
    }

    @SuppressWarnings("unchecked")
    public  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;
        return a;
    }

    // Positional Access Operations

    @SuppressWarnings("unchecked")
    E elementData(int index) {
        return (E) elementData[index];
    }

    public E get(int index) {
        rangeCheck(index);

        return elementData(index);
    }

    public E set(int index, E element) {
        rangeCheck(index);//判断索引合法性

        E oldValue = elementData(index);//获得原数组指定索引的元素
        elementData[index] = element;//将指定所引处的元素替换为 element
        return oldValue;//返回原数组索引元素
    }

    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

    public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

     public E remove(int index) {
         rangeCheck(index);//判断给定索引的范围，超过集合大小则抛出异常
 
         modCount++;
         E oldValue = elementData(index);//得到索引处的删除元素
 
         int numMoved = size - index - 1;
         if (numMoved > 0)//size-index-1 > 0 表示 0 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work
    }

    public void clear() {
        modCount++;

        // clear to let GC do its work
        for (int i = 0; i < size; i++)
            elementData[i] = null;

        size = 0;
    }

    public boolean addAll(Collection c) {
        Objects.requireNonNull(c);
        return batchRemove(c, false);
    }

    public boolean retainAll(Collection c) {
        Objects.requireNonNull(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) {
                // clear to let GC do its work
                for (int i = w; i < size; i++)
                    elementData[i] = null;
                modCount += size - w;
                size = w;
                modified = true;
            }
        }
        return modified;
    }

    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 size as capacity for behavioural compatibility with clone()
        s.writeInt(size);

        // Write out all elements in the proper order.
        for (int i=0; i 0) {
            // be like clone(), allocate array based upon size not capacity
            int capacity = calculateCapacity(elementData, size);
            SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);
            ensureCapacityInternal(size);

            Object[] a = elementData;
            // Read in all elements in the proper order.
            for (int i=0; i size)
            throw new IndexOutOfBoundsException("Index: "+index);
        return new ListItr(index);
    }

    public ListIterator listIterator() {
        return new ListItr(0);
    }

    public Iterator iterator() {
        return new Itr();
    }

     private class Itr implements Iterator {
         int cursor;       //游标， 下一个要返回的元素的索引
         int lastRet = -1; // 返回最后一个元素的索引; 如果没有这样的话返回-1.
         int expectedModCount = modCount;
 
         //通过 cursor ！= size 判断是否还有下一个元素
         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];//返回索引为i处的元素，并将 lastRet赋值为i
         }
 
         public void remove() {
             if (lastRet < 0)
                 throw new IllegalStateException();
             checkForComodification();
 
             try {
                 ArrayList.this.remove(lastRet);//调用ArrayList的remove方法删除元素
                 cursor = lastRet;//游标指向删除元素的位置，本来是lastRet+1的，这里删除一个元素，然后游标就不变了
                 lastRet = -1;//lastRet恢复默认值-1
                 expectedModCount = modCount;//expectedModCount值和modCount同步，因为进行add和remove操作，modCount会加1
             } catch (IndexOutOfBoundsException ex) {
                 throw new ConcurrentModificationException();
             }
         }
 
         @Override
         @SuppressWarnings("unchecked")
         public void forEachRemaining(Consumer