java集合-ArrayList

package java.util;

import java.util.function.Consumer;
import java.util.function.Predicate;
import java.util.function.UnaryOperator;
import sun.misc.SharedSecrets;

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    private static final long serialVersionUID = 8683452581122892189L;

    /**
     * 默认初始化容量.
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * 空数组
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

		//用于默认大小空实例的共享空数组实例。
      //我们把它从EMPTY_ELEMENTDATA数组中区分出来，以知道在添加第一个元素时容量需要增加多少。
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

	  //用于保存ArrayList数据的数组
     //这里用了transient关键字来表示该数组不被序列化，在这里是为了避免java自带的序列化操作，并定义了两个方法，实现自定的序列化操作。
      
    transient Object[] elementData; // non-private to simplify nested class access

    /**
     * The size of the ArrayList (the number of elements it contains).
     * 当前元素个数
     * @serial
     */
    private int size;

   /**
    * 带初始化容量的构造方法
    * 
    * @param  initialCapacity  the initial capacity of the list
    * @throws IllegalArgumentException if the specified initial capacity
    *         is negative
    */
   public ArrayList(int initialCapacity) {
       if (initialCapacity > 0) {
           this.elementData = new Object[initialCapacity];
       } else if (initialCapacity == 0) {
       //创建空数组
           this.elementData = EMPTY_ELEMENTDATA;
       } else {
           throw new IllegalArgumentException("Illegal Capacity: "+
                                              initialCapacity);
       }
   }

   /**
    * 默认构造函数，DEFAULTCAPACITY_EMPTY_ELEMENTDATA 为0.初始化为10，也就是说初始其实是空数组 当添加第一个元素的时候数组容量才变成10.
    */
   public ArrayList() {
       this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
   }

   /**
    * 按照指定集合的迭代器返回的顺序创建数组元素
    *
    * @param c the collection whose elements are to be placed into this list
    * @throws NullPointerException if the specified collection is null
    */
   public ArrayList(Collection<? extends E> c) {
       elementData = c.toArray();
       if ((size = elementData.length) != 0) {
           // c.toArray might (incorrectly) not return Object[] (see 6260652)
           if (elementData.getClass() != Object[].class)
               elementData = Arrays.copyOf(elementData, size, Object[].class);
       } else {
           // replace with empty array.
           this.elementData = EMPTY_ELEMENTDATA;
       }
   }

   /**
    * 修改这个ArrayList实例的容量是列表的当前大小。 应用程序可以使用此操作来最小化ArrayList实例的存储。
    * the storage of an <tt>ArrayList</tt> instance.
    */
   public void trimToSize() {
       modCount++;
       if (size < elementData.length) {
           elementData = (size == 0)
             ? EMPTY_ELEMENTDATA
             : Arrays.copyOf(elementData, size);
       }
   }

   /**
    * 不懂这做啥的。。。
    * @param   minCapacity   the desired minimum capacity
    */
   public void ensureCapacity(int minCapacity) {
       int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
           // any size if not default element table
           ? 0
           // larger than default for default empty table. It's already
           // supposed to be at default size.
           : DEFAULT_CAPACITY;

       if (minCapacity > minExpand) {
           ensureExplicitCapacity(minCapacity);
       }
   }
   //计算扩容的大小
   private static int calculateCapacity(Object[] elementData, int minCapacity) {
   //如果数组元素是空数组就返回最大值
       if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
           return Math.max(DEFAULT_CAPACITY, minCapacity);
       }
       return minCapacity;
   }
   
   private void ensureCapacityInternal(int minCapacity) {
       ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
   }
   //扩容主要的方法
   private void ensureExplicitCapacity(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;
   /**
    * 扩容的核心办法
    * @param minCapacity the desired minimum capacity
    */
    
   private void grow(int minCapacity) {
       // overflow-conscious code
       //获得旧数组大小
       int oldCapacity = elementData.length;
       //获得旧数组大小1.5倍
       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:
       elementData = Arrays.copyOf(elementData, newCapacity);
   }

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

   /**
    * 返回数组元素个数
    *
    * @return the number of elements in this list
    */
   public int size() {
       return size;
   }

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

   /**
    * 判断指定元素是否存在数组元素中
    * @param o element whose presence in this list is to be tested
    * @return <tt>true</tt> if this list contains the specified element
    */
   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;
   }

   /**
    * 返回v本身，不会影响该数组本身（我理解是为深拷贝）
    * @return a clone of this <tt>ArrayList</tt> instance
    */
   public Object clone() {
       try {
           ArrayList<?> v = (ArrayList<?>) 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);
       }
   }

   /**
    * 返回包含该数组元素的新数组（深拷贝）
    * @return an array containing all of the elements in this list in
    *         proper sequence
    */
   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;
       return a;
   }

   // Positional Access Operations

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

   /**
    * 返回指定索引的元素
    * @param  index index of the element to return
    * @return the element at the specified position in this list
    * @throws IndexOutOfBoundsException {@inheritDoc}
    */
   public E get(int index) {
       rangeCheck(index);

       return elementData(index);
   }

   /**
    * 设置指定索引位置的元素
    * @param index index of the element to replace
    * @param element element to be stored at the specified position
    * @return the element previously at the specified position
    * @throws IndexOutOfBoundsException {@inheritDoc}
    */
   public E set(int index, E element) {
       rangeCheck(index);

       E oldValue = elementData(index);
       elementData[index] = element;
       return oldValue;
   }

   /**
    * 添加元素
    * @param e element to be appended to this list
    * @return <tt>true</tt> (as specified by {@link Collection#add})
    */
   public boolean add(E e) {
       ensureCapacityInternal(size + 1);  // Increments modCount!!
       elementData[size++] = e;
       return true;
   }

   /**
    * 在指定位置插入元素
    * @param index index at which the specified element is to be inserted
    * @param element element to be inserted
    * @throws IndexOutOfBoundsException {@inheritDoc}
    */
   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++;
   }

   /**
    * 删除索引指定元素，索引后的元素整体往左移动一个元素
    * @param index the index of the element to be removed
    * @return the element that was removed from the list
    * @throws IndexOutOfBoundsException {@inheritDoc}
    */
   public E remove(int index) {
       rangeCheck(index);

       modCount++;
       E oldValue = elementData(index);

       int numMoved = size - index - 1;
       if (numMoved > 0)
           System.arraycopy(elementData, index+1, elementData, index,
                            numMoved);
       elementData[--size] = null; // clear to let GC do its work

       return oldValue;
   }

   /**
    * 删除指定元素，被删除元素后的整体往左移动一个元素
    *
    * @param o element to be removed from this list, if present
    * @return <tt>true</tt> if this list contained the specified element
    */
   public boolean remove(Object o) {
       if (o == null) {
           for (int index = 0; index < size; index++)
               if (elementData[index] == null) {
                   fastRemove(index);
                   return true;
               }
       } else {
           for (int index = 0; index < size; index++)
               if (o.equals(elementData[index])) {
                   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)
           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;
   }

   /**
    * 从尾部开始将指定集合插入进列表
    *
    * @param c collection containing elements to be added to this list
    * @return <tt>true</tt> if this list changed as a result of the call
    * @throws NullPointerException if the specified collection is null
    */
   public boolean addAll(Collection<? extends E> c) {
       Object[] a = c.toArray();
       int numNew = a.length;
       ensureCapacityInternal(size + numNew);  // Increments modCount
       System.arraycopy(a, 0, elementData, size, numNew);
       size += numNew;
       return numNew != 0;
   }

   /**
    * 从指定索引开始将指定集合插入进列表
    * @param index index at which to insert the first element from the
    *              specified collection
    * @param c collection containing elements to be added to this list
    * @return <tt>true</tt> if this list changed as a result of the call
    * @throws IndexOutOfBoundsException {@inheritDoc}
    * @throws NullPointerException if the specified collection is null
    */
   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)
           System.arraycopy(elementData, index, elementData, index + numNew,
                            numMoved);

       System.arraycopy(a, 0, elementData, index, numNew);
       size += numNew;
       return numNew != 0;
   }

。。。

public static void arraycopy(Object src,int srcPos,Object dest,int destPos,int length)

public static <T> T[] copyOf(T[] original, int newLength)