目录一、任务目标二、 数组的连续存储特性2.1 什么是连续存储2.2 连续存储的优缺点三、 动态数组ArrayList的概念四、 手写简易 ArrayListMyArrayList4.1 类定义和成员变量4.2 核心方法扩容4.3 添加元素4.3.1 添加到最后add(E e)4.3.2 插入到指定位置add(int index, E e)4.4 删除元素4.4.1 删除指定位置的元素remove(int index)4.4.2 删除指定元素remove(Object o)4.5 获取和修改元素4.6 其他辅助方法4.7 完整代码整合五、 扩容机制详解System.arraycopy5.1 为什么需要扩容5.2 System.arraycopy 是什么5.3 在扩容中的应用5.4 扩容时机与容量计算六、 时间复杂度分析七、对比 Java 的 ArrayList一、任务目标1. 理解数组的连续存储特性。2. 实现动态数组ArrayList。3. 掌握扩容机制System.arraycopy。4.基于数组实现一个简易ArrayList支持扩容、删除元素分析时间复杂度。二、 数组的连续存储特性2.1 什么是连续存储数组Array是一种线性表数据结构它用一组连续的内存空间来存储相同类型的数据。每个元素占用相同大小的内存通过下标索引可以直接计算出对应元素的内存地址。例如一个int[] arr new int[5]会在内存中开辟一块连续的 5×420 字节的空间假设 int 占 4 字节。元素arr[0]的地址是起始地址arr[1]的地址是起始地址4以此类推。2.2 连续存储的优缺点优点支持随机访问Random Access即通过索引访问任意元素的时间复杂度为O(1)。因为只需计算偏移量即可直接定位。缺点插入和删除操作需要移动大量元素平均时间复杂度为O(n)。数组长度固定一旦创建不可改变。如果需要存储更多元素必须创建新数组并复制原数组内容这正是动态数组要解决的问题。三、 动态数组ArrayList的概念动态数组是一种基于数组实现的可自动扩容的线性表。它在内部维护一个数组初始大小为10当元素个数超过数组容量时会自动创建一个更大的新数组并将原数组元素复制过去原理。Java 中的ArrayList就是最典型的动态数组实现。我们需要实现一个简化版的MyArrayList包含以下核心功能自动扩容增、删、改、查获取大小、判断是否为空四、 手写简易 ArrayListMyArrayList我们将使用泛型E来支持任意对象类型。底层使用Object[]存储因为 Java 无法直接创建泛型数组new E[size]会编译错误但可以通过类型转换处理。4.1 类定义和成员变量import java.util.Arrays; public class MyArrayListE { private Object[] elementData; // 存储元素的数组 private int size; // 实际元素个数 private static final int DEFAULT_CAPACITY 10; // 默认初始容量 // 构造方法指定初始容量 public MyArrayList(int initialCapacity) { if (initialCapacity 0) { throw new IllegalArgumentException(Illegal Capacity: initialCapacity); } this.elementData new Object[initialCapacity]; } // 无参构造使用默认容量 public MyArrayList() { this(DEFAULT_CAPACITY); } }解释elementData是实际存放元素的数组由于泛型擦除使用Object[]可以存放任何对象。size记录当前已经存储的元素个数注意它不等于数组长度容量。默认初始容量设为 10这是 JDKArrayList的常用值。PS:泛型擦除【补充】泛型擦除1概念解释泛型擦除是 Java 编译器在处理泛型代码时做的一个“把戏”编译时泛型信息会被“擦除”掉转换成普通的非泛型代码强制类型转换所以在运行时程序实际上并不知道泛型的具体类型。换句话说编译时有泛型编译器会做严格的类型检查防止你放错类型。运行时泛型没了所有类都变成了原始类型Raw Type比如ListString和ListInteger在运行时都是List。2为什么需要泛型擦除主要是为了向后兼容。Java 在 1.5 版本才引入泛型但之前已经有大量非泛型的代码如List、ArrayList。如果让泛型在运行时也保留类型信息那么旧的 JVM 和类库就无法识别新格式的类会导致兼容性问题。所以 Java 设计者选择了“擦除”方案编译后的字节码和旧版本一样只是编译器帮你插入了必要的类型转换。这样既有泛型的类型安全又能兼容旧代码。3泛型擦除带来的限制因为运行时没有泛型类型信息所以会有些事做不了1.不能使用基本类型作为类型参数Listint list; // 编译错误必须使用包装类 ListInteger因为擦除后变成Object而int不是对象。2.不能创建泛型数组T[] arr new T[10]; // 编译错误因为运行时不知道T是什么无法确定数组元素类型。通常的解决方法是创建Object[]然后强转或者使用ArrayList。3.不能使用instanceof检查泛型类型if (obj instanceof ListString) // 编译错误4.不能使用new T()T obj new T(); // 编译错误因为类型被擦除无法知道该调用哪个构造函数。通常通过反射传递ClassT来绕开。5.静态上下文中不能引用类型变量public class BoxT { private static T item; // 编译错误 }静态成员属于类而泛型是实例化时才确定的所以无法共存。6.方法签名冲突由于擦除可能导致本来不冲突的方法变得冲突。例如public void set(ListString list) { } public void set(ListInteger list) { } // 编译错误擦除后都是 set(List)4.2 核心方法扩容当添加元素时若数组已满需要扩容。我们定义一个私有方法ensureCapacity来确保容量足够。private void ensureCapacity(int minCapacity) { // 如果当前容量不够则扩容 if (minCapacity elementData.length) { // 新容量 旧容量 * 1.5取整数 int newCapacity elementData.length (elementData.length 1); // 如果新容量仍然小于所需最小容量则取最小容量防止溢出 if (newCapacity minCapacity) { newCapacity minCapacity; } // 使用 Arrays.copyOf 创建新数组并复制原内容 elementData Arrays.copyOf(elementData, newCapacity); } }关键点elementData.length是当前数组容量。minCapacity是所需的最小容量通常是size1。扩容策略int newCapacity elementData.length (elementData.length 1);相当于1.5 倍右移一位相当于除以2。这是 JDK 8 中ArrayList采用的扩容方式。如果计算出的新容量仍小于minCapacity比如初始容量为0时则直接使用minCapacity。Arrays.copyOf内部使用了System.arraycopy这是一个本地方法能够高效地复制数组。4.3 添加元素4.3.1 添加到最后add(E e)public boolean add(E e) { ensureCapacity(size 1); // 确保容量足够 elementData[size] e; // 放入元素size 自增 return true; }4.3.2 插入到指定位置add(int index, E e)public void add(int index, E element) { // 检查索引范围0 index size允许在末尾追加 if (index 0 || index size) { throw new IndexOutOfBoundsException(Index: index , Size: size); } ensureCapacity(size 1); // 保证容量 // 将 index 及之后的元素向后移动一位 // 参数说明源数组、起始位置、目标数组、目标起始位置、移动长度 System.arraycopy(elementData, index, elementData, index 1, size - index); elementData[index] element; // 插入新元素 size; }解释System.arraycopy是数组复制的核心方法它可以在同一个数组内移动元素即使源和目标区域重叠也能正确处理。这里将index开始的元素包括 index全部向后移动一位空出 index 位置。时间复杂度需要移动 O(n) 个元素因此为O(n)。4.4 删除元素4.4.1 删除指定位置的元素remove(int index)SuppressWarnings(unchecked) public E remove(int index) { // 检查索引0 index size if (index 0 || index size) { throw new IndexOutOfBoundsException(Index: index , Size: size); } E oldValue (E) elementData[index]; // 获取被删除的元素 int numMoved size - index - 1; // 需要移动的元素个数 if (numMoved 0) { // 将 index1 及之后的元素向前移动一位 System.arraycopy(elementData, index 1, elementData, index, numMoved); } elementData[--size] null; // 将最后一个位置置为 null帮助 GC return oldValue; }解释如果删除的是最后一个元素index size-1则numMoved 0无需移动。移动完成后将原最后一个位置设为null避免对象游离虽然 size 已减但数组还保留着引用置 null 可以让垃圾回收器回收。时间复杂度平均 O(n)最好 O(1)删除最后一个元素。4.4.2 删除指定元素remove(Object o)public boolean remove(Object o) { // 遍历查找第一个匹配的元素 for (int i 0; i size; i) { if (o null ? elementData[i] null : o.equals(elementData[i])) { remove(i); // 调用上面的 remove(int) 方法 return true; } } return false; }解释需要区分null和非null避免空指针异常。找到后调用remove(int)删除其时间复杂度仍为 O(n)因此整体最坏 O(n)。4.5 获取和修改元素SuppressWarnings(unchecked) public E get(int index) { if (index 0 || index size) { throw new IndexOutOfBoundsException(Index: index , Size: size); } return (E) elementData[index]; } public E set(int index, E element) { if (index 0 || index size) { throw new IndexOutOfBoundsException(Index: index , Size: size); } E oldValue (E) elementData[index]; elementData[index] element; return oldValue; }解释get和set都直接通过索引访问数组时间复杂度O(1)。需要强制类型转换因为elementData是Object[]但我们的设计确保存储的都是E类型所以安全。使用SuppressWarnings(unchecked)消除警告。4.6 其他辅助方法public int size() { return size; } public boolean isEmpty() { return size 0; } // 查找元素第一次出现的索引不存在返回 -1 public int indexOf(Object o) { if (o null) { for (int i 0; i size; i) { if (elementData[i] null) return i; } } else { for (int i 0; i size; i) { if (o.equals(elementData[i])) return i; } } return -1; } // 可选清空列表 public void clear() { // 将每个元素置为 null帮助 GC for (int i 0; i size; i) { elementData[i] null; } size 0; }4.7 完整代码整合将以上所有方法合并并添加必要的导入即得一个简易的MyArrayList。为了便于测试可以添加toString方法可选Override public String toString() { StringBuilder sb new StringBuilder([); for (int i 0; i size; i) { sb.append(elementData[i]); if (i size - 1) sb.append(, ); } sb.append(]); return sb.toString(); }五、 扩容机制详解System.arraycopy5.1 为什么需要扩容因为数组一旦创建长度就固定了。当添加元素时如果size elementData.length说明数组已满必须创建一个更大的新数组并将旧数组的内容复制过去。5.2 System.arraycopy 是什么System.arraycopy是一个本地方法native method它的作用是复制数组的一部分到另一个数组可以是同一个数组。其声明为public static native void arraycopy(Object src, int srcPos, Object dest, int destPos, int length);src源数组srcPos源数组起始位置dest目标数组destPos目标数组起始位置length要复制的元素个数特点它是 Java 中最高效的数组复制方式由 JVM 底层实现通常使用内存块拷贝。支持同一个数组内的重叠区域复制例如将元素向后移动内部会正确处理。5.3 在扩容中的应用在我们的ensureCapacity方法中使用了Arrays.copyOf它内部调用了System.arraycopy。其大致实现如下public static T T[] copyOf(T[] original, int newLength) { return (T[]) copyOf(original, newLength, original.getClass()); } // 最终调用 System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength));所以扩容的核心就是创建一个新数组将旧数组的内容复制到新数组然后将内部引用指向新数组。5.4 扩容时机与容量计算每次添加元素时先调用ensureCapacity(size1)检查是否需要扩容。扩容倍数通常选择1.5 倍原因如果倍数太大例如 2 倍可能浪费内存。如果倍数太小例如 1.1 倍会导致频繁扩容复制开销大。1.5 倍是一个折衷既能减少扩容次数又不会浪费太多空间黄金分割比例近似。注意如果扩容后容量仍小于所需的最小容量比如初始容量为 0计算 1.5 倍还是 0则直接使用最小容量。六、 时间复杂度分析操作时间复杂度说明add(E e)均摊 O(1)大多数情况直接追加偶尔扩容复制 n 个元素但扩容次数少均摊成本低add(int, E)O(n)需要移动 index 之后的元素remove(int)O(n)平均需要移动 n/2 个元素最好 O(1)删除末尾remove(Object)O(n)先遍历查找O(n)再删除O(n)总 O(n)get(int)O(1)直接索引访问set(int, E)O(1)直接索引修改indexOf(Object)O(n)需要遍历size()/isEmpty()O(1)直接返回成员变量补充说明均摊 O(1)虽然add(E e)偶尔会触发 O(n) 的扩容复制但每扩容一次后续 n 次添加都不需要复制所以总时间平摊到每次添加上接近 O(1)。这是动态数组的核心优势。插入/删除在中间位置时因为要移动大量元素所以性能较差。如果业务中频繁在中间插入删除应考虑使用链表如LinkedList。七、对比 Java 的 ArrayList特性手写 MyArrayListJava ArrayList (JDK 8)底层数组Object[]Object[]泛型擦除后默认容量1010扩容倍数1.5 倍1.5 倍JDK 8扩容方法Arrays.copyOfArrays.copyOf线程安全否否快速失败未实现通过 modCount 实现迭代器的快速失败序列化未实现实现 Serializable并自定义 writeObject/readObject克隆未实现实现 Cloneable支持浅拷贝subList 视图无支持子列表视图额外功能基础功能大量方法addAll、removeAll、retainAll、toArray 等总结手写简易 ArrayList 帮助理解底层原理实际开发中应直接使用ArrayList它经过充分测试和优化功能更完善。但通过自己实现可以加深对数组扩容、元素移动等概念的理解。