List 经典问

List（JDK 1.8）

3.1 数组

3.1.1 数组概述

• 数组定义：连续内存存储相同类型的数据的线性结构。

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

• 内存表示：
  • 栈内存保存数组变量array，存储数组首地址引用
  • 堆内存保存实际数组元素[22,33,88,66,55,25]

3.1.2 数组寻址公式

访问数组元素：

array[i] = baseAddress + i * dataTypeSize

• baseAddress：数组首地址
• i：索引
• dataTypeSize：元素类型大小（int=4字节）

示例：

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

堆中地址 14 处就是array[1]的值 33。

3.1.3 操作时间复杂度

3.2 ArrayList（JDK 1.8）源码分析

3.2.1 成员变量

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; // 实际元素个数

• DEFAULT_CAPACITY：默认初始容量 10，用于无参构造第一次 add 扩容
• EMPTY_ELEMENTDATA：容量为 0 的共享空数组，用于new ArrayList<>(0)
• DEFAULTCAPACITY_EMPTY_ELEMENTDATA：用于无参构造的空数组，第一次 add 扩容到 10
• elementData：实际存储元素的数组
• size：当前元素个数

3.2.2 构造方法

// 带初始容量 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); } } // 无参构造 public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } // 通过 Collection 构造 public ArrayList(Collection<? extends E> c) { elementData = c.toArray(); size = elementData.length; }

• 无参构造不会立即开 10 个长度数组，第一次add时才扩容
• 带容量构造立即分配指定容量数组
• Collection 构造直接把 collection 转成数组赋值给elementData，共享同一内存地址

3.2.3 添加数据流程 (

add(E e)

源码：

public boolean add(E e) { ensureCapacityInternal(size + 1); // 确保容量 elementData[size++] = e; // 添加元素 return true; }

ensureCapacityInternal(size + 1)

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

calculateCapacity

private static int calculateCapacity(Object[] elementData, int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { return Math.max(DEFAULT_CAPACITY, minCapacity); // 无参构造第一次 add 扩到 10 } return minCapacity; // 其他情况直接返回 minCapacity }

ensureExplicitCapacity

private void ensureExplicitCapacity(int minCapacity) { modCount++; if (minCapacity - elementData.length > 0) { grow(minCapacity); // 扩容 } }

grow 方法

private void grow(int minCapacity) { int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); // 扩 1.5 倍 if (newCapacity - minCapacity < 0) newCapacity = minCapacity; // 不够用，直接用 minCapacity if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); elementData = Arrays.copyOf(elementData, newCapacity); // 拷贝旧数组 }

• 1.5 倍扩容，减少频繁扩容开销
• Arrays.copyOf复制旧元素到新数组
• size++后添加新元素

3.2.4 初始容量 & 扩容总结

• 扩容逻辑：容量不足 → 调grow()→ 新容量 = 旧容量 * 1.5（若不够用，则直接用 minCapacity）

3.2.5 面试题示例

1. ArrayList list=new ArrayList(10)：未添加元素，未扩容
2. Arrays.asList(array)
   • 修改数组 → List 也变，底层共享同一内存
   • 修改 List 元素 → 数组也变
   • 不能 add/remove，固定长度
3. list.toArray()
   • 返回数组是拷贝，修改 List 不影响数组，修改数组不影响 List

3.3 总结要点（面试必备）

1. ArrayList 底层结构：动态数组（Object[]）+ size
2. 无参构造：第一次 add 才开容量 10
3. 扩容策略：1.5 倍，使用Arrays.copyOf
4. add(E e) 流程：
   1. 计算所需容量 (size + 1) →calculateCapacity
   2. 确认容量 →ensureExplicitCapacity
   3. 扩容 →grow
   4. 添加元素 →elementData[size++] = e
5. 数组与 List 转换：
   • Arrays.asList→ 底层共享数组
   • list.toArray()→ 拷贝数组，不共享
6. 数组操作复杂度：
   • 随机访问 O(1)
   • 遍历查找 O(n)
   • 插入/删除 O(n)