先分析下ArrayList的源码,

1、ArrayList源码分析

1.1 类实现的接口

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

ArrayList继承List接口，实现了List接口中所有方法

1.2、构造方法

有三个构造方法

• 无参构造方法

public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

看一下具体实现方法
1.这是类中定义好的节点数组

 transient Object[] elementData; // non-private to simplify nested class access

2.定义好的静态空数组

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

当调用无参构造函数的时候，会把静态数组赋给节点数组，数组大小为0

• 有参构造方法（参数是集合的大小）

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);
        }
    }

看下具体实现
先检查给的参数是否正确
如果参数大于0, new一个指定长度的数组

this.elementData = new Object[initialCapacity];

如果参数等于0，将类中定义的空数组赋给节点数组

  private static final Object[] EMPTY_ELEMENTDATA = {};
 this.elementData = EMPTY_ELEMENTDATA;

如果参数小于0，抛出异常

• 有参构造方法（参数是集合）

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;
        }
    }

如果原来的数组的长度为空，就把节点数组指向空数组，
如果不为空，将值赋给节点数组

1.3 add方法

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

 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);
    }

扩充

 private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        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);
    }

添加元素：
1.检查数组的长度，调用ensureCapacityInternal(int minCapacity)方法
   对数组进行扩充，保证可以存放数据，
2.调用ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
  将节点数组和传入的长度进行判断，
3.调用calculateCapacity(elementData, minCapacity)
  如果节点数组是默认数组，返回默认长度（10）和传入值的最大值，
4.调用ensureExplicitCapacity(int minCapacity)方法
  判断返回的长度，如果返回的长度大于节点数组的长度，就扩充，如果不大于，直接返回
5.调用grow扩充

例子：如果是刚创建的集合，添加数据，
1.调用ensureCapacityInternal(size + 1); size默认为0
2.调用ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
3.调用calculateCapacity(elementData, minCapacity)
elementData指向DEFAULTCAPACITY_EMPTY_ELEMENTDATA
minCapacity等于1
判断成立，返回默认值（10）和传入值1的最大值10
4.调用ensureExplicitCapacity(10)，
节点数组现在为空，所以分组
5.调用grow方法
得到原本节点数组的长度，扩充原数组的一半大小，得到新长度，如果新长度小于传入的长度，就将传入的长度作为新长度，判断新长度是否大于最大值（是否内存溢出），执行数组复制，得到一个长度为10的数组
6.添加数据
elementData[size++] = e;
把数据添加进数组

例子：扩容
如果添加的是第11个元素
1.重新分组，扩充原来数组的一半，15个，15比11大，将原数组的数据拷贝到新数组

1.4、size方法

public int size() {
        return size;
    }

返回定义好的长度，每次添加之后size都会自增

1.5 set方法

public E set(int index, E element) {
        rangeCheck(index);

        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }
 private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

具体实现
为某个索引处，设置值
先判断索引是否有效，
数组节点位置的值设为新传入的值，返回原有的值

1.6、get方法

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

        return elementData(index);
    }

判断索引是否有效，返回对应节点处的数据

1.7 remove方法

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;
    }

具体实现

1.移除指定位置的数据
2.判断索引是否正确
3.移除
移除是使用数组复制实现的
System.arraycopy（提供数据数组，从那个位置拷贝，拷贝数据数组，从哪个位置放，拷多长）

image.png

4.移除之后，数组最后一个节点为null

1.8 addAll方法

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;
    }

先将集合转成数组，得到数组长度，将节点数组扩充，将数组内容拷贝节点数组，数组长度增加

1.9 toArray方法

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

其他方法就不说了，

2.自己手动实现

public class MyArrayList {

    private int size;//集合的长度
    private Object[] elementData;//集合数组

    MyArrayList(){
        this(10);
    }
    MyArrayList(int initialCapacity)  {
        if (initialCapacity>0){
            this.elementData = new Object[initialCapacity];
        }else {
            try {
                throw new Exception();
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
    }

    MyArrayList(Collection c){
        Object[] objects = c.toArray();
        int length = objects.length;
        if((size=length)!=0){
            //如果数组长度不等于0
            elementData = Arrays.copyOf(objects,size);
        }
    }

    /**
     * 返回集合长度
     * @return
     */
    int size(){
        return size;
    }

    /**
     * 将集合转成数组
     * @return
     */
    Object[] toArray(){
        return Arrays.copyOf(elementData,size);
    }

    /**
     * 添加元素
     * @param object
     */
    boolean add(Object object){
        ensureCapacityInternal(size + 1);//对数组扩容
        elementData[size++] = object;
        return true;
    }

    private void ensureCapacityInternal(int minCapacity) {
         //判断数组长度是否支持当前索引
        if (minCapacity-elementData.length>0){
            //如果传入的索引比节点数组长度大，分组扩充节点数组大小，
            //分组
            //1.扩充数组长度为原数组的1.5倍
            int oldCapacity = elementData.length;

            int newCapacity= oldCapacity+(oldCapacity >> 1);

            if (minCapacity - newCapacity >0)
                newCapacity = minCapacity;

            //2.新建数组，将原数组数据复制
            elementData =Arrays.copyOf(elementData,newCapacity);
        }
    }

    Object get(int index){
        rangeIndex(index);
        return elementData[index];
    }

    //判断索引是否超标
    private void rangeIndex(int index) {

        if (index >= size || index<0){
            try {
                throw new Exception();
            } catch (Exception e) {
                e.printStackTrace();
            }
        }

    }

    /**
     * 将某处的值设为object
     * @param index
     * @param object
     */
    void set(int index,Object object){
        rangeIndex(index);

        elementData[index] = object;
    }

}

更多详情：qq群 552113611