实现List接口及List的所有方法
ArrayList 创建时的大小为 0；当加入第一个元素时，进行第一次扩容时，默认容 量大小为 10；ArrayList 每次扩容都以当前数组大小的 1.5 倍去扩容；ArrayList 和 Vector 的 add、 get、 size 方法的复杂度都为 O(1)， remove 方法的复杂度为 O(n)ArrayList 非线程安全属性较少，所有方法建立在elementData上
//默认容量的大小 private static final int DEFAULT_CAPACITY = 10; //空数组常量 private static final Object[] EMPTY_ELEMENTDATA = {}; //默认的空数组常量 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; //存放元素的数组，从这可以发现 ArrayList 的底层实现就是一个 Object数组 transient Object[] elementData; //数组中包含的元素个数 private int size; //数组的最大上限 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;1. 构造方法 默认情况下，elementData数组是一个大小为0的空数组，当指定初始大小时，elementData的初始大小即为指定值
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); } } public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }2.get方法 ArrayList 是采用数组结构来存储的，所以它的 get 方法非常简单，先是判断有没有越界，之后就可以直接通过数组下标来获取元素了，所以 get 的时间复杂度是== O(1)==。
public E get(int index) { rangeCheck(index); return elementData(index); } private void rangeCheck(int index) { //检查输入的下标是否越界 if (index >= size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } E elementData(int index) { return (E) elementData[index];3.add方法 add添加方法，在插入元素之前，会先检查是否需要扩容，然后将元素添加到数组的最后，当elementData为空数组时，会使用默认的大小10去扩容，当增加到比10大，进行grow。 不带下标的add方法，时间复杂度扩容操作忽略时，为O(1),带下标的add方法，涉及到数组中元素的移动，时间复杂度O(n)
public boolean add(E e) { //检查是否需要扩容 ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e;//size++的方法，在size索引处加上e，然后size+1； return true; } public void add(int index, E element) { rangeCheckForAdd(index); ensureCapacityInternal(size + 1); // Increments modCount!! //调用一个 native 的复制方法，把 index 位置开始的元素都往后挪一位 System.arraycopy(elementData, index, elementData, index +1,size - index); elementData[index] = element; size++; } private void ensureCapacityInternal(int minCapacity) { //如果elementData 为默认空数组时，在输入的size与属性的默认size 进行比较，选择最大的 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); } private void ensureExplicitCapacity(int minCapacity) { modCount++; if (minCapacity - elementData.length > 0) grow(minCapacity); } }4.set方法 将下标为index的元素替换为element，时间复杂度为O(1),返回替换前的元素
public E set(int index, E element) { rangeCheck(index); E oldValue = elementData(index); elementData[index]=element; return oldValue;5.remove方法 进行数组元素的移动，时间复杂度为O(n)
public E remove(int index) { //检查待删除节点的索引是否越界 rangeCheck(index); modCount++; E oldValue=elementData[index] int numMoved=size-index-1; System.arraycopy(elementData,index+1,elementData,index,numMoved); elementData[--size]=null;//进行GC return oldValue;6.size 返回数组中元素的大小，不是数组的实际大小，==O(1)==的时间复杂度
public int size(){ return size;7.indexOf方法和lastIndexOf方法
indexOf方法返回该元素第一次出现的位置 lastIndexOf方法返回该元素最后一次出现的位置 时间复杂度均为O(n)
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; } 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; }