public class ArrayList<E> {
  // 数组实现，不需要额外的元信息管理，节约空间
  // 为什么用transient修饰符？
  // 因为大部分情况下数组的容量总是不满的，为了提升序列化性能，只序列化有数据的空间，调用writeObject方法而不是完全拷贝elementData属性
  transient Object[] elementData; 
  
  // 默认数组容量是10
  private static final int DEFAULT_CAPACITY = 10;
  
  // 扩容
  private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        // 超出限制会增加原容量一半的空间(oldCapacity >> 1 即一半）
        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);
    }

    // get访问元素通过下标访问数组，效率高
    E elementData(int index) {
        return (E) elementData[index];
    }
    
    public E set(int index, E element) {
        rangeCheck(index);
        // set也是先通过下标获取原来的值返回，再根据下标修改新值
        E oldValue = elementData(index);
        elementData[index] = 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!!
        // 带有下标参数的add方法，要用System.arraycopy复制部分受影响的元素，性能差
        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);
        
        // 删除最后一个元素是特例，不会调用arraycopy影响性能
        int numMoved = size - index - 1;
        if (numMoved > 0)
            // remove也调用System.arraycopy，性能差
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
    }

    public boolean remove(Object o) {
        if (o == null) {
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true;
                }
        } else {
            // 通过值remove元素，要从头遍历，性能差
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }
}