ArrayList底层实现

前言

第一次记录源码文章没什么经验，希望从以下几个角度能帮助你加深对java数据结构ArrayList(jdk17)的理解。

• 源码分析
• 执行流程图
• 面试题

源码分析

下面通过注解方式为大伙简单讲一下底层逻辑

构造方式

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    @java.io.Serial
    
    //这是序列号
    private static final long serialVersionUID = 8683452581122892189L;
	
    //无参构造时的默认容量
    private static final int DEFAULT_CAPACITY = 10;
	
	//定义两个空数组，用于判断当前数组的状态
    private static final Object[] EMPTY_ELEMENTDATA = {};
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    //元素储存的数组
    transient Object[] elementData; 

	//当前容量，也可以理解为最后一个元素的下标
    private int size;

	//传入参数为int类型
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            //若传入的值大于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;
    }

	//传入参数为集合
    public ArrayList(Collection<? extends E> c) {
        //先将传入集合转换为数组
        Object[] a = c.toArray();
        //判断传入是否是空集合
        if ((size = a.length) != 0) {
            //非空且传入集合也是ArrayList，则直接将传入集合的地址赋给我们创建的集合
            if (c.getClass() == ArrayList.class) {
                elementData = a;
            } 
            /*非空但传入集合不是ArrayList，则进行数组的浅拷贝，注意！这里的只会将集合里的属性改变而不改变其地址
            也就是说我们若对传入的集合进行操作是不会影响我们创建的List的
            */
            else {
                elementData = Arrays.copyOf(a, size, Object[].class);
            }
        } else {
            elementData = EMPTY_ELEMENTDATA;
        }
    }
}

插入元素

想了一下这里和扩容一起讲比较好

几个插入元素的源码如下：

   //一个其他方法的调用
private void add(E e, Object[] elementData, int s) {
       //判断原来的数组大小是否够用
       if (s == elementData.length)
           //不够用，扩容
           elementData = grow();
       //够用直接插入
       elementData[s] = e;
       size = s + 1;
   }
//集合中插入元素
   public boolean add(E e) {
       modCount++;
       //调用了上面的add()方法
       add(e, elementData, size);
       return true;
   }

//在指定位置插入元素
   public void add(int index, E element) {
       //判断插入的位置是否合法
       rangeCheckForAdd(index);
       modCount++;
       final int s;
       Object[] elementData;
       //判断数组是否够长
       if ((s = size) == (elementData = this.elementData).length)
           //不够长扩容
           elementData = grow();
       //改变其他元素的位置，就是将该下标后的所有元素拷贝到该下标+1位置后
       System.arraycopy(elementData, index,
                        elementData, index + 1,
                        s - index);
       //插入元素
       elementData[index] = element;
       size = s + 1;
   }

下面是扩容操作：

   private Object[] grow(int minCapacity) {
       //记录老容量
       int oldCapacity = elementData.length;
       //如果并不是第一次扩容
       if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
           int newCapacity = ArraysSupport.newLength(oldCapacity,
                   minCapacity - oldCapacity, /*最小扩容量 minimum growth */
                   oldCapacity >> 1           /*首选增长量 preferred growth */);
           return elementData = Arrays.copyOf(elementData, newCapacity);
       } else {
           //第一次扩容至默认容量10
           return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
       }
   }

   private Object[] grow() {
       return grow(size + 1);
   }

   public static int newLength(int oldLength, int minGrowth, int prefGrowth) {

       int prefLength = oldLength + Math.max(minGrowth, prefGrowth); // might overflow
       //如果不是第一次扩容，就将两倍的老容量直接返回
       //SOFT_MAX_ARRAY_LENGTH = INTEGER_MAX-8
       if (0 < prefLength && prefLength <= SOFT_MAX_ARRAY_LENGTH) {
           return prefLength;
       } else {

           return hugeLength(oldLength, minGrowth);
       }
   }
//这个方法不用细看，只要知道最大长度是INTEGER_MAX就行
   private static int hugeLength(int oldLength, int minGrowth) {
       int minLength = oldLength + minGrowth;
       if (minLength < 0) { 
           throw new OutOfMemoryError(
               "Required array length " + oldLength + " + " + minGrowth + " is too large");
       } else if (minLength <= SOFT_MAX_ARRAY_LENGTH) {
           return SOFT_MAX_ARRAY_LENGTH;
       } else {
           return minLength;
       }
   }

数组转List

改变数组会影响List

//这是将array的地址直接传给了a
public static <T> List<T> asList(T... a) {
       return new ArrayList<>(a);
   }
   ArrayList(E[] array) {
       //这个方法用来获取数组的地址
       a = Objects.requireNonNull(array);
   }

List转数组

改变List不会影响数组

   //这里很明显是进行了一次拷贝而不是地址传递
@Override
   public Object[] toArray() {
       return Arrays.copyOf(a, a.length, Object[].class);
   }

流程图

---

面试题

• ArrayList底层的实现原理是什么

ArrayList底层是用动态的数组实现的。
ArrayList初始容量为0，当第一次添加数据的时候才会初始化容量为10。
ArrayList在进行扩容的时候是原来容量的2倍，每次扩容都需要拷贝数组。
ArrayList在添加数据的时候。
确保数组已使用长度（size）加1之后足够存下下一个数据。
计算数组的容量，如果当前数组已使用长度+1后的大于当前的数组长度，则调用grow方法扩容（原来的2倍)。
确保新增的数据有地方存储之后，则将新元素添加到位于size的位置上。
返回添加成功布尔值。

• 如何实现List和数组之间的转换(可参考实现原理)

• ArrayList和LinkedList的区别是什么

底层数据结构：

ArrayList是基于动态数组（时间、空间）

LinkedList是基于双向链表（时间、空间）