ArrayList 分析以及相关方法介绍

public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable{

}

public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E>{}

public abstract class AbstractCollection<E> implements Collection<E>{}

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

public interface List<E> extends Collection<E>{}

List list = new ArrayList();
List list2 = new LinkedList();

import java.util.*;

/**
* 详述ArrayList 基本用法
*/
public class ArrayListTest{

   private static class SortList implements Comparator<String>{

       @Override
       public int compare(String o1, String o2) {
           Integeri1 = Integer.valueOf(o1);
           Integeri2 = Integer.valueOf(o2);
           if(i1 < i2){
               return -1;
          }elseif(i1 == i2){
               return 0;
          }
           return 1;
      }
  }

   // 使用可变参数，能够接受任意个参数
   public Set<String> putSet(String...args){
       Set<String> sets = new HashSet<>();
       for(String str: args){
           sets.add(str);
      }
       return sets;
  }

   public static void main(String[] args) {
       ArrayList<String> list = new ArrayList<>();
       list.add("111");
       list.add("222");

       // 在指定位置添加元素
       list.add(0,"333");
       System.out.println(list);

       // 进行外部排序
       list.sort(new SortList());
       System.out.println(list);

       list.clear();
       System.out.println(list.size());

       // 使用addAll添加元素
       ArrayList Testat = new ArrayListTest();
       list.addAll(at.putSet("1","2","3"));

       Iterator<String> it = list.iterator();
       while(it.hasNext()){
           System.out.println(it.next());
           // 移除所有元素
           it.remove();
      }

       System.out.println("list是否为空 ? "+list.isEmpty());

       list.add("111");
       // 在指定位置添加一个set集合
       list.addAll(0,at.putSet("1","2","3"));
       System.out.println(list);

       // 是否包含指定元素
       if(list.contains("111")) {
           list.remove("111");
      }
       System.out.println(list);

       System.out.println(list.indexOf("1"));
       // 注意subList()这个方法是左开右闭区间，Java 中很多都是类似的
       System.out.println(list.subList(0,3));

       // 扩大list的容量
       list.ensureCapacity(10);
       // 去掉list空闲的容量
       list.trimToSize();

       // 获取某个特定的元素
       System.out.println(list.get(1));

       // 创建一个list的双向链表
       ListIterator<String> listIterator = list.listIterator();
       while(listIterator.hasNext()){
           // 移到list的末端
           System.out.println(listIterator.next());
      }
       System.out.println("--------------------------");
       while(listIterator.hasPrevious()){
           // 移到list的首端
           System.out.println(listIterator.previous());
      }

       // 把list转换为数组
       Object[] objects = list.toArray();
       System.out.println("objects = "+objects);

  }
}

/**
    * Appends the specified element to the end of this list.
    * 添加指定的元素在list的末尾
    * @param e element to be appended to this list
    * @return <tt>true</tt> (as specified by {@link Collection#add})
    */

// 假设第一次添加的是 "111"
   public boolean add(E e) {
       // size是0，所以size + 1 传的是1
       ensureCapacityInternal(size+1);  // Increments modCount!!
       // elementData[0] = 111 , size++ = 1
       elementData[size++] =e;
       return true;
  }

// 此方法用来进行list 扩容
private void ensureCapacityInternal(int minCapacity) {
       // 此时elementData 并没有存储元素，为0
       if(elementData==DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
           // 则minCapacity 取默认初始容量和minCapacity 的最大值 (取1 和 10的最大值)
           minCapacity=Math.max(DEFAULT_CAPACITY, minCapacity);
      }
       // 确保清晰的容量(最小容量与List元素的比较)
       ensureExplicitCapacity(minCapacity);
  }

// 在list中添加了一个元素，所以会导致结构化的修改，"结构化的修改"见下面解释
// 此时minCapacity 为 10
private void ensureExplicitCapacity(int minCapacity) {
       // 次数 + 1 
       // 这个列表被修改结构的次数(比如添加和删除元素)会用modCount表示. 结构化修改是指的是能够
       // 改变列表容量的操作，或者其他方式改变它，导致遍历的过程会产生错误的结果。
       modCount++;

       // overflow-conscious code
       // 10 - 0 > 0 走grow 方法
       if(minCapacity-elementData.length>0)
           grow(minCapacity);
  }

/**
    * Increases the capacity to ensure that it can hold at least the
    * number of elements specified by the minimum capacity argument.
    * 增加容量确保容纳足够的元素
    *
    * @param minCapacity the desired minimum capacity
    * 参数传过来的是10
    */
   private void grow(int minCapacity) {
       // overflow-conscious code
       // oldCapacity = 0
       int oldCapacity=elementData.length;
// newCapacity = 0
       int newCapacity=oldCapacity+(oldCapacity>>1);
  // newCapacity - minCapacity = -10
       if(newCapacity-minCapacity<0)
           // newCapacity = 10
           newCapacity=minCapacity;
       
       // MAX_ARRAY_SIZE = 数组分配的最大空间 = 2147483639
       // 一般情况下不会比 MAX_ARRAY_SIZE 还要大
       if(newCapacity-MAX_ARRAY_SIZE>0)
           newCapacity=hugeCapacity(minCapacity);
       // minCapacity is usually close to size, so this is a win:
       // 底层还是用的System.arraycopy(), 关于System.arrayCopy() 读者可以参考我的另一篇博客
       elementData=Arrays.copyOf(elementData, newCapacity);
  }

/**
    * Inserts the specified element at the specified position in this
    * list. Shifts the element currently at that position (if any) and
    * any subsequent elements to the right (adds one to their indices).
    * 在list中指定位置插入指定的元素，如果当前位置有元素，就移动当前位置的元素
    * 要插入的位置的后面所有元素的位置向前 + 1
    *
    * @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) {
       // 检查 0 这个位置是否越界
       rangeCheckForAdd(index);

       // 不再赘述，读者可以自行debug
       ensureCapacityInternal(size+1);  // Increments modCount!!
       // 因为从当前位置插入元素，所以当前位置及后面的元素都会向后移动
       // 使用System.arraycopy 进行数组复制
       System.arraycopy(elementData, index, elementData, index+1,
                        size-index);
       // 为当前元素赋值
       elementData[index] =element;
       size++;
  }

/**
    * A version of rangeCheck used by add and addAll.
    * 为add 和 addall 提供的范围检查, 不符合条件，抛出IndexOutOfBoundsException 异常
    *
    */
   private void rangeCheckForAdd(int index) {
       if(index>size||index<0)
           throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
  }

/**
    * Removes all of the elements from this list. The list will
    * be empty after this call returns.
    * 移除list列表中所有的元素，列表会变为空列表在调用此方法后
    *
    */
   public void clear() {
       // 修改次数 + 1
       modCount++;

       // clear to let GC do its work
       // 把每个变量置空，GC进行回收
       for(int i=0; i<size; i++)
           elementData[i] =null;

       // 列表的长度变为0
       size=0;
  }

/**
    * Appends all of the elements in the specified collection to the end of
    * this list, in the order that they are returned by the
    * specified collection's Iterator. The behavior of this operation is
    * undefined if the specified collection is modified while the operation
    * is in progress. (This implies that the behavior of this call is
    * undefined if the specified collection is this list, and this
    * list is nonempty.)
    * 把一个Collection集合(实现了此接口的类)添加到list的末尾，按着迭代的顺序返回。
    * 此操作的行为是如果在此方法调用的过程中修改了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 NullPointerException if the specified collection is null
    */
   public boolean addAll(Collection<?extendsE>c) {
       // 把Collection 转换为 Object[] 数组
       Object[] a=c.toArray();
       // 数组中有三个元素
       int numNew=a.length;
       // 因为上面的操作调用了一次list.clear()方法，所以list.size = 0
       ensureCapacityInternal(size+numNew);  // Increments modCount
       // 一句话解释： 把a 数组中0个位置的元素 复制到 elementData数组中 第size个位置的元素，
       // 复制的长度为 numNew
       System.arraycopy(a, 0, elementData, size, numNew);
       size+=numNew;
       return numNew!=0;
  }

// toArray()方法：

/**
    * Returns an array containing all of the elements in this list
    * in proper sequence (from first to last element).
    * 返回一个数组，包含了所有的元素(从第一个元素到最后一个元素)
    *
    * <p>The returned array will be "safe" in that no references to it are
    * maintained by this list. (In other words, this method must allocate
    * a new array). The caller is thus free to modify the returned array.
    * 返回的数组是很"安全的"因为列表没有引用可以维持(换句话说，这个方法必须分配一个新数组)
    * 调用者因此可以任意修改返回的数组
    *
    * <p>This method acts as bridge between array-based and collection-based
    * APIs.
    * 这个方法是数组 和 集合之间的桥梁
    *
    * @return an array containing all of the elements in this list in
    *         proper sequence
    */
   public Object[] toArray() {
       return Arrays.copyOf(elementData, size);
  }

/**
    * 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>.
    * 返回的iterator 支持fail-fast 机制
    *
    * @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
    * Itr 是一个内部类，实现了Iterator接口，可支持快速遍历
    */
   private class Itr implements Iterator<E>{
       // 下一个元素返回的下标
       int cursor;       // index of next element to return
       // 最后一个元素返回的下标， 如果没有返回-1
       int lastRet=-1; // index of last element returned; -1 if no such
       // expectedModCount 期望的修改次数，默认是和modCount(修改次数相同，用于iterator判断fail-fast机制)
       int expectedModCount=modCount;

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

       @SuppressWarnings("unchecked")
       public E next() {
           // 判断遍历的过程中是否触发fail-fast机制
           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() {
           // 如果lastRet < 0，说明 lastRet 没有被改变，
           // 所以应该是没有调用next()就调用了remove()
           if(lastRet<0)
               throw new IllegalStateException();
           checkForComodification();

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

       @Override
       @SuppressWarnings("unchecked")
       public void forEachRemaining(Consumer<?superE> consumer) {
           Objects.requireNonNull(consumer);
           fina lint size=ArrayList.this.size;
           int i=cursor;
           if(i>=size) {
               return;
          }
           final Object[] elementData=ArrayList.this.elementData;
           if(i>=elementData.length) {
               thrownewConcurrentModificationException();
          }
           while(i!=size&&modCount==expectedModCount) {
               consumer.accept((E) elementData[i++]);
          }
           // update once at end of iteration to reduce heap write traffic
           cursor=i;
           lastRet=i-1;
           checkForComodification();
      }

       // 如果修改次数不满足预期修改次数的话，抛出异常
       final void checkForComodification() {
           if(modCount!=expectedModCount)
               throw new ConcurrentModificationException();
      }
  }

/**
    * Inserts all of the elements in the specified collection into this
    * list, starting at the specified position. Shifts the element
    * currently at that position (if any) and any subsequent elements to
    * the right (increases their indices). The new elements will appear
    * in the list in the order that they are returned by the
    * specified collection's iterator.
    * 在指定的位置下标插入一个Collection集合
    *
    * @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<?extendsE> c) {
       rangeCheckForAdd(index);

       Object[] a=c.toArray();
       int numNew=a.length;
       ensureCapacityInternal(size+numNew);  // Increments modCount

       // 需要移动的元素个数
       int numMoved=size-index;
       if(numMoved>0)
           // 第一次数组复制，从elementData中的index位置开始，复制到index + numNew位置上，复制numMoved个元素
           System.arraycopy(elementData, index, elementData, index+numNew,
                            numMoved);

       // 第二次数组复制,从a 数组中的第0个位置开始，复制到elementData第index位置上你，复制numNew个元素
       System.arraycopy(a, 0, elementData, index, numNew);
       size+=numNew;
       return numNew!=0;
  }

/**
    * Returns <tt>true</tt> if this list contains the specified element.
    * More formally, returns <tt>true</tt> if and only if this list contains
    * at least one element <tt>e</tt> such that
    * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>.
    * 返回true，如果这个列表包含指定的元素
    * 更进一步来说，当且仅当list包含至少一个元素的情况下，返回true
    *
    * @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;
  }

/**
    * Returns the index of the first occurrence of the specified element
    * in this list, or -1 if this list does not contain the element.
    * More formally, returns the lowest index <tt>i</tt> such that
    * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,
    * or -1 if there is no such index.
    * 返回列表中第一次出现指定元素的下标值，如果不包含指定元素，则返回-1。
    * 更进一步来说，返回最小的索引当(o == null ? get(i) == null : o.equals(get(i)))的时候
    * 或者返回-1 没有此下标值
    *
    */
   public int indexOf(Object o) {
       // 如果o这个对象等于null，就判断elementData中是否有空元素，如果有，返回
       if(o==null) {
           for(int i=0; i<size; i++)
               if(elementData[i]==null)
                   return i;
      } else{
           // 如果不为null，返回这个值的存储位置
           for(int i=0; i<size; i++)
               if(o.equals(elementData[i]))
                   return i;
      }
       return -1;
  }

/**
    * Removes the first occurrence of the specified element from this list,
    * if it is present. If the list does not contain the element, it is
    * unchanged. More formally, removes the element with the lowest index
    * <tt>i</tt> such that
    * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>
    * (if such an element exists). Returns <tt>true</tt> if this list
    * contained the specified element (or equivalently, if this list
    * changed as a result of the call).
    * 如果存在，则移除list中某个第一次出现的元素。如果这个list不包含指定元素，就不会改变
    *
    * @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;
              }
      }
       returnfalse;
  }

/*
    * 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
  }

/**
    * Returns a view of the portion of this list between the specified
    * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive. (If
    * {@code fromIndex} and {@code toIndex} are equal, the returned list is
    * empty.) The returned list is backed by this list, so non-structural
    * changes in the returned list are reflected in this list, and vice-versa.
    * The returned list supports all of the optional list operations.
    * 返回list列表中的一部分视图(相当于list片段),[fromIndex,toIndex)，如果fromIndex 和
    * toIndex 相同的话，表明这个list为空，这个返回的list被返回，所以在list中并没有结构的改变
    * 这个返回的list片段支持所有的list操作
    */
public List<E> subList(int fromIndex, int toIndex) {
       // subList 范围检查
       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;
      }
  }

/**
    * Increases the capacity of this <tt>ArrayList</tt> instance, if
    * necessary, to ensure that it can hold at least the number of elements
    * specified by the minimum capacity argument.
    * 增加ArrayList实例的容量，如果必须的话，确保它能持有最小容量的元素
    *
    * @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);
      }
  }

/**
    * Trims the capacity of this <tt>ArrayList</tt> instance to be the
    * list's current size. An application can use this operation to minimize
    * the storage of an <tt>ArrayList</tt> instance.
    * 去掉ArrayList中的多余空间
    *
    */
   public void trimToSize() {
       modCount++;
       if(size<elementData.length) {
           elementData=(size==0)
             ?EMPTY_ELEMENTDATA
            : Arrays.copyOf(elementData, size);
      }
  }