List 经典问

ListJDK 1.83.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 * dataTypeSizebaseAddress数组首地址i索引dataTypeSize元素类型大小int4字节示例array[1] 10 1 * 4 14堆中地址 14 处就是array[1]的值 33。3.1.3 操作时间复杂度操作时间复杂度说明随机访问array[i]O(1)直接计算地址未知索引查找O(n)遍历数组已排序数组二分查找O(log n)二分查找插入O(n)插入位置后的元素都要后移删除O(n)删除位置后的元素都要前移3.2 ArrayListJDK 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 扩容到 10elementData实际存储元素的数组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)); }calculateCapacityprivate static int calculateCapacity(Object[] elementData, int minCapacity) { if (elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { return Math.max(DEFAULT_CAPACITY, minCapacity); // 无参构造第一次 add 扩到 10 } return minCapacity; // 其他情况直接返回 minCapacity }ensureExplicitCapacityprivate 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 初始容量 扩容总结构造方式初始 elementData.length第一次 add 后容量new ArrayList()0 (DEFAULTCAPACITY_EMPTY_ELEMENTDATA)10new ArrayList(0)0 (EMPTY_ELEMENTDATA)1new ArrayList(10)10不扩容扩容逻辑容量不足 → 调grow()→ 新容量 旧容量 * 1.5若不够用则直接用 minCapacity3.2.5 面试题示例ArrayList listnew ArrayList(10)未添加元素未扩容Arrays.asList(array)修改数组 → List 也变底层共享同一内存修改 List 元素 → 数组也变不能 add/remove固定长度list.toArray()返回数组是拷贝修改 List 不影响数组修改数组不影响 List3.3 总结要点面试必备ArrayList 底层结构动态数组Object[] size无参构造第一次 add 才开容量 10扩容策略1.5 倍使用Arrays.copyOfadd(E e) 流程计算所需容量 (size 1) →calculateCapacity确认容量 →ensureExplicitCapacity扩容 →grow添加元素 →elementData[size] e数组与 List 转换Arrays.asList→ 底层共享数组list.toArray()→ 拷贝数组不共享数组操作复杂度随机访问 O(1)遍历查找 O(n)插入/删除 O(n)