ArrayList源码解析（数据结构及底层实现）

流程图

Main.java（我们的操作）

public class Main{
    public static void main(String[] args){
        //首先创建了一个ArrayList集合,该集合中只能存放E类型的数据
        ArrayList list=new ArrayList<>();//初始化ArrayList实例，由于ArrayList底层是通过数组实现的，该数组初始大小为空。
        list.add("a1");//当集合第一次被赋值时，容量大小为10。与初始化时不同。每次添加数据时会对底层数组进行扩容
    }
}

属性

public class ArrayList extends AbstractList 
implements List, RandomAccess, Cloneable, java.io.Serializable {
    
    private static final int DEFAULT_CAPACITY = 10;
    
    
    transient Object[] elementData;
    
    
    private int size;//未赋值，即默认初始为0
    
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    
    
    // MAX_ARRAY_SIZE=2147483639=01111111 11111111 11111111 11110111
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    
}

构造方法

public class ArrayList extends AbstractList 
implements List, RandomAccess, Cloneable, java.io.Serializable {
    //常用构造方法
    // eg1：初始化ArrayList实例，则elementData={}
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; // Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    }
}

add方法及其涉及到的方法

public class ArrayList extends AbstractList 
implements List, RandomAccess, Cloneable, java.io.Serializable {
    
     // eg1：第一次新增元素e="a1"
    public boolean add(E e) {
        
        ensureCapacityInternal(size + 1);  // 此处size+1但未给size赋值，故此时size还是0
    
        // eg1：size=0，elementData[0]="a1"，然后a自增为1
        elementData[size++] = e;
        return true;
    }
    
    // eg1：第一次新增元素，所以size=0，则：minCapacity=size+1=1
    private void ensureCapacityInternal(int minCapacity) {
        // eg1：第一次新增元素，calculateCapacity方法返回值为DEFAULT_CAPACITY=10
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }
    
    
    // eg1：第一次新增元素，elementData={} minCapacity=1
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            // eg1：满足if判断，DEFAULT_CAPACITY=10
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }
    
    
    // eg1：第一次新增元素，minCapacity=10
    private void ensureExplicitCapacity(int minCapacity) {
        // eg1: modCount++后，modCount=1
        modCount++;
    
        
        if (minCapacity - elementData.length > 0) { // eg1：10-0=10，满足扩容需求
            // eg1：minCapacity=10
            grow(minCapacity);
        }
    }
    
    
    // eg1：第一次新增元素，minCapacity=10，即：需要将elementData的0长度扩容为10长度。
    private void grow(int minCapacity) {
    
        
        int oldCapacity = elementData.length; // eg1：oldCapacity=0
    
        
        
        int newCapacity = oldCapacity + (oldCapacity >> 1); // eg1：newCapacity=0+(0>>1)=0
    
        
        if (newCapacity - minCapacity < 0) {
            // eg1：newCapacity=10
            newCapacity = minCapacity;
        }
    
        
        if (newCapacity - MAX_ARRAY_SIZE > 0) {
            newCapacity = hugeCapacity(minCapacity);
        }
    
        
        // eg1：newCapacity=10， 扩容elementData的length=10
        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;
    }
}