List与ArrayList

2025-03-30

集合 java

数组

数组（Array）是一种用连续的内存空间存储相同数据类型数据的线性数据结构。

int[] array = {22,33,88,66,55,25};

栈内存会指向堆内存地址

寻址公式

实际上内存地址不是数字，只是为了方便理解把 0X110 这种地址改掉了

内存地址	10	11	12	13	14	15	16	17	18	19	20	21	...
数据空间	22	-	-	-	33		-	-	88	-	-	-	...
分支标记	0	-	-	-	1		-	-	2	-	-	-	...

arr[i] = baseAddress + i * dataTypeSize

baseAddress：数组的首地址
dataTypeSize：代表数组中元素类型的大小，假如数组重存储的是int型的数据，dataTypeSize=4个字节
arr：指的是数组
i：指的是数组的下标

举例：

int[] array = {22,33,88,66,55,25};

公式计算

array[1] =10 + i * 4 = 14

获取到14这个地址，就能获取到下标为1的这个元素33了

思考：为什么索引要从0开始，而不是从1开始？

公式：数组首地址 + 索引 * 存储数据类型大小

如果从1开始，公式计算就是

arr[i] = baseAddress + (i-1) * dataTypeSize

结果仍然是一样的，但是要比下面的公式多一次减法运算，性能就没那么好。

arr[i] = baseAddress + i * dataTypeSize

操作数组的时间复杂度

根据索引查询O(1)

直接通过索引 i 访问数组 a 的元素 a[i]

public int test01(int[] a,int i){
   return a[i];
   // a[i] = baseAddress + i \* dataSize
}

数组在内存中是连续存储的，通过索引可直接定位到元素的内存地址，无需遍历或额外计算，因此时间复杂度为常数级别 O(1)

未知索引查询O(n)或O(log2n)

情况一：查找数组内的元素，查找55号数据，遍历数组时间复杂度为O(n)

情况二：查找排序后数组内的元素，通过二分查找算法查找55号数据时间复杂度为O(logn)

插入或删除0(n)

数组是一段连续的内存空间，因此为了保证数组的连续性会使得数组的插入和删除的效率变的很低

可以看到x后面的元素都要顺序后移1位

当然，如果是在a6后面顺序插入，时间复杂度就是O(1)

总结：

插入操作，最好情况下是O(1)的，最坏情况下是O(n)的，平均情况下的时间复杂度是O(n)。
同理可得：如果我们要删除第 k 个位置的数据，为了内存的连续性，也需要搬移数据，不然中间就会出现空洞，内存就不连续了，时间复杂度仍然是O(n)。

ArrayList源码分析（jdk 1.8）

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

分析ArrayList源码主要从三个方面去翻阅：成员变量，构造函数，关键方法

ArrayList核心成员变量

/**
 * 默认初始容量。
 */
private static final int DEFAULT_CAPACITY = 10;

/**
 * 共享的空数组实例，用于空实例的存储。
 */
private static final Object[] EMPTY_ELEMENTDATA = {};

/**
 * 共享的空数组实例，用于默认大小的空实例的共享空数组实例。
 * 与EMPTY_ELEMENTDATA区分，以便在添加第一个元素时知道如何扩容。
 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/**
 * 存储ArrayList元素的数组缓冲区。
 * ArrayList的容量即此数组缓冲区的长度。
 * 任何elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA的空ArrayList，
 * 在首次添加元素时会扩容至DEFAULT_CAPACITY（默认10）。
 */
transient Object[] elementData; // 非私有化以简化嵌套类访问

/**
 * ArrayList的实际元素数量（包含的元素个数）。
 *
 * @serial
 */
private int size;

构造方法

里面的elementData才是真正存储数据的数组

/**
 * 构造一个具有指定初始容量的空列表。
 * 
 * @param initialCapacity  列表的初始容量
 * @throws IllegalArgumentException 如果指定的初始容量为负数
 * 
 */
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];  // 创建指定大小的Object数组
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;           // 使用预定义的空数组，就是{}
    } else {
        throw new IllegalArgumentException("非法容量: " + initialCapacity); // 负数抛出异常
    }
}

/**
 * 构造一个初始容量为10的空列表。
 * 注意：实际数组在第一次添加元素时才真正分配10个空间
 */
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;  // 使用默认空数组标记
}

1.带参构造函数：

处理三种情况：正数容量/零容量/负数容量
使用EMPTY_ELEMENTDATA优化零容量场景的内存使用

2.无参构造函数：

使用特殊标记DEFAULTCAPACITY_EMPTY_ELEMENTDATA
延迟分配：首次添加元素时才真正分配默认10容量（惰性初始化）

/**
 * 构造一个包含指定集合所有元素的列表，元素顺序与集合迭代器返回顺序一致。
 * 
 * @param c 要将其元素放入此列表的集合
 * @throws NullPointerException 如果指定的集合为null
 */
public ArrayList(Collection<? extends E> c) {
    // 直接将集合转为数组存储
    elementData = c.toArray();
    
    // 处理转换后的数组
    if ((size = elementData.length) != 0) {
        // 解决JDK bug 6260652：某些集合的toArray()可能不返回Object[]类型
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // 空集合时使用共享空数组实例
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

将collection对象转换成数组，然后将数组的地址的赋给elementData

突然想到的一个问题：
在 ArrayList 的初始化策略中，不指定大小（无参构造） 和 显式指定大小为0 有以下关键区别：：

初始化方式	底层数组赋值	首次添加元素时的行为
无参构造 `new ArrayList()`	`DEFAULTCAPACITY_EMPTY_ELEMENTDATA`	扩容到默认容量10（触发`grow()`方法）
指定容量0 `new ArrayList(0)`	`EMPTY_ELEMENTDATA`	从容量0开始按需扩容（首次扩容到1）

小结：
若已知元素数量较多 → 用无参构造或预分配足够容量（如new ArrayList(100)）。
若元素数量极少或不确定 → 用new ArrayList(0)减少初始内存浪费。

添加数据的流程

第一次添加的情况

 // 第一次添加
 List<Integer> list = new ArrayList<Integer>();
 list.add(1);
 
 //默认构造器
 public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;  // 使用默认空数组标记，下面判断会提到
}

当执行add方法（第一次添加数据）

/**
 * 将指定元素追加到列表的末尾。
 * 
 * @param e 要追加到列表的元素
 * @return <tt>true</tt>（遵循{@link Collection#add}规范）
 */
public boolean add(E e) {  // 这里e是1
    // 确保内部容量足够（size+1）之后能存下下一个数据，内部会递增modCount!!
    ensureCapacityInternal(size + 1);  //size默认是0，那么这里就是1了   
    // 将元素放入数组末尾，并增加size计数
    elementData[size++] = e;           //  实际添加元素
    // 固定返回true（符合Collection接口规范）
    return true;
}

第一行ensureCapacityInternal会确保内部容量

private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

minCapacity就是上面传过来的1
elementData是成员变量，用来存数据的数组

calculateCapacity方法如下

  private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { //这里的判断为true，因为这就是上面提到的默认无参构造
            return Math.max(DEFAULT_CAPACITY, minCapacity); //这里用Math.max函数，可以得到10和1肯定10大，所以返回10
        }
        return minCapacity; //处理 非默认初始化场景 的分支逻辑
    }

DEFAULT_CAPACITY默认是10

private static final int DEFAULT_CAPACITY = 10;

然后回到ensureExplicitCapacity方法

  private void ensureExplicitCapacity(int minCapacity) {  //这里minCapacity=10
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0) // 10-0肯定>0，说明容量不够，需要grow扩容
            grow(minCapacity);
    }

看看grow方法

/**
 * 扩容数组以确保至少能容纳minCapacity指定的元素数量。
 * 
 * @param minCapacity 所需的最小容量
 */
private void grow(int minCapacity) {
    // 旧容量 = 当前数组长度
    int oldCapacity = elementData.length;
    
    // 新容量 = 旧容量 + 旧容量/2（即1.5倍扩容），这里>>1是二进制右移，相当于向下除2，比如5/2 -> 2
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    
    // 处理溢出情况：如果1.5倍扩容后仍不满足需求，直接使用minCapacity
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    
    // 处理超大容量请求（超过MAX_ARRAY_SIZE）
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    
    // 数组拷贝，将原数组内容复制到新容量数组中（通常minCapacity接近实际size，效率较高）
    elementData = Arrays.copyOf(elementData, newCapacity);
}

第二行执行elementData[size++] = e;

这里e就是 list.add(1);里面的1，同时size也会++，然后return true

当执行add方法（第2~10次添加数据，即数组不扩容）

在如下方法

  private void ensureExplicitCapacity(int minCapacity) {  //这里minCapacity=10
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0) // 10-10 = 0 了，因此不会扩容
            grow(minCapacity);
    }

记录结构性修改次数： modCount（modification count）是 AbstractList 定义的计数器，专门用于统计列表的 结构性修改 次数（如添加、删除元素，调整容量等）。
触发并发修改检测：当对集合进行迭代（如使用 Iterator）时，迭代器会检查 modCount 是否与初始值一致。若不一致，说明集合在迭代期间被修改，立即抛出 ConcurrentModificationException。

当执行add方法（第11添加数据，数组扩容）

第一行ensureCapacityInternal会确保内部容量，这个时候传了个11过去，就要去重新计算容量了，调用ensureExplicitCapacity方法里面的calculateCapacity方法，回到ensureCapacityInternal方法下的ensureExplicitCapacity方法

  private void ensureExplicitCapacity(int minCapacity) {  //这里minCapacity=11
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0) // 11-10>0，说明容量不够，需要grow扩容
            grow(minCapacity);
    }

走到扩容方法

  private void grow(int minCapacity) { //minCapacity = 11
        // overflow-conscious code
        int oldCapacity = elementData.length;  //10
        int newCapacity = oldCapacity + (oldCapacity >> 1); // 10 + 10/2 = 15 
        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);  //数组拷贝
    }

总结：

ArrayList的底层实现原理

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

数组和List之间的转换

数组转List ，使用JDK中java.util.Arrays工具类的asList方法

下面是asList方法关键代码

 @SafeVarargs
    @SuppressWarnings("varargs")
    public static <T> List<T> asList(T... a) {  // 1.数组传过来T... a
        return new ArrayList<>(a);              // 2.new的ArrayList是当前内部类的
    }

    /**
     * @serial include
     */
    private static class ArrayList<E> extends AbstractList<E>
        implements RandomAccess, java.io.Serializable
    {
        private static final long serialVersionUID = -2764017481108945198L;
        private final E[] a;

        ArrayList(E[] array) {                  // 3.数组a就传过来了
            a = Objects.requireNonNull(array);  // 4/判断当前array是否为空，为空报错，不为空赋值给a，a就是E[] a
        }

因此，这里只涉及对象的引用，并没有创建新的对象。

思考：用Arrays.asList转List后，如果修改了数组内容，list受影响吗？
Arrays.asList转换list之后，如果修改了数组的内容，list会受影响，因为它的底层使用的Arrays类中的一个内部类ArrayList来构造的集合，在这个集合的构造器中，把我们传入的这个集合进行了包装而已，最终指向的都是同一个内存地址

List转数组，使用List的toArray方法。

List转数组，使用List的toArray方法。无参toArray方法返回 Object数组，传入初始化长度的数组对象，返回该对象数组。

<T> T[] toArray(T[] a);

点击toArray，会到ArrayList的toArray方法

@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) { //传递过来的数组a
    if (a.length < size)
        return (T[]) Arrays.copyOf(elementData, size, a.getClass());
    System.arraycopy(elementData, 0, a, 0, size);  //arraycopy重新复制了数据到新的elementData数组中
    if (a.length > size)
        a[size] = null;
    return a;
}

因此，List的toArray方法相当于创建了一个新的数组。

思考：List用toArray转数组后，如果修改了List内容，数组受影响吗？
list用了toArray转数组后，如果修改了list内容，数组不会影响，当调用了toArray以后，在底层是它是进行了数组的拷贝，跟原来的元素就没啥关系了，所以即使list修改了以后，数组也不受影响