1. 项目概述从零开始构建你的顺序表在Java的世界里数据结构是构建高效、稳定程序的基石。无论你是刚入门的新手还是有一定经验的开发者当你需要处理一组有序的、需要频繁访问和修改的数据时数组Array往往是你的第一直觉。但数组的长度是固定的一旦初始化就无法改变这在处理动态数据时显得捉襟见肘。这时一个更灵活、更强大的工具——顺序表Sequential List就该登场了。简单来说顺序表就是用数组作为底层存储并在此基础上封装了一系列增、删、改、查操作的线性结构。它继承了数组随机访问通过下标的高效性时间复杂度O(1)又通过动态扩容机制解决了数组长度固定的痛点。理解并亲手实现一个顺序表不仅能让你深刻理解Java集合框架中ArrayList、Vector等类的底层原理更是锻炼你面向对象设计、边界条件处理和算法思维的最佳实践。这篇文章我将带你从零开始用纯Java代码实现一个功能完整的顺序表。我们会从最基础的结构设计开始一步步实现插入、删除、查找、扩容等核心操作并深入探讨每个操作背后的时间复杂度、空间复杂度以及那些教科书上不会写的“踩坑”经验。无论你是为了准备面试还是想夯实基础这篇手把手的实现指南都值得你花时间仔细阅读和动手实践。2. 顺序表的核心设计与思路拆解在动手写代码之前我们必须先想清楚几个关键问题这个顺序表类应该长什么样它需要哪些核心属性它应该对外提供哪些方法这些方法的设计背后又隐藏着哪些权衡和考量2.1 底层存储与核心属性顺序表的本质是一个“智能数组”。因此它的核心属性必然包含一个用于存储数据的数组。在Java中我们通常使用一个Object数组或者泛型数组来保证可以存储任意类型的元素。但仅仅有数组还不够我们还需要一个关键属性来记录当前顺序表中实际存储的有效元素个数这个属性通常叫做size。为什么需要size因为底层数组的length属性表示的是这个容器的“总容量”它可能远大于我们实际存放的数据量。size则精确地指向了最后一个有效元素的下一个位置逻辑上的“尾部”它是所有增删操作的核心坐标。基于此我们的类结构雏形就出来了public class MyArrayList { // 底层存储数组 private Object[] elementData; // 当前有效元素个数 private int size; // 默认初始容量 private static final int DEFAULT_CAPACITY 10; }这里我选择Object[]是为了简化初版实现便于理解。在实际的ArrayList源码中使用的是泛型数组E[]但这涉及到泛型擦除和类型安全问题我们可以在进阶版本中引入。2.2 核心操作的方法签名设计一个实用的顺序表至少需要支持以下操作这些也是面试中的高频考点增Add在尾部添加、在指定索引位置插入。删Remove删除指定索引位置的元素、删除首次出现的指定元素。查Search根据索引获取元素、查找元素首次出现的索引。改Set修改指定索引位置的元素。工具方法获取当前元素数量size、判断是否为空isEmpty、清空所有元素clear。在设计方法签名时我们必须考虑边界情况和用户体验。例如add(int index, E element)方法在插入时如果index等于size则表示在尾部追加这是合法的但如果index大于size或小于0则属于非法索引必须抛出异常如IndexOutOfBoundsException。这种严谨性是工业级代码与玩具代码的区别。2.3 动态扩容策略空间与时间的权衡这是顺序表设计中最精妙的部分。数组是定长的但我们的数据是动态增长的。当size即将达到数组length时我们必须进行扩容。一个朴素的想法是每次不够用时就申请一个只比当前容量大1的新数组。但这会导致频繁的内存申请和数据拷贝插入N个元素的时间复杂度会退化到O(N²)性能极差。因此通用的策略是按比例扩容。ArrayList的默认扩容因子是1.5倍即newCapacity oldCapacity (oldCapacity 1)。这样做的优点是摊还分析Amortized Analysis下每次插入操作的平均时间复杂度仍然是O(1)。虽然单次扩容操作申请新数组拷贝所有元素的成本是O(n)但由于扩容频率以指数级降低这个成本被“摊还”到了多次插入操作中。注意扩容因子是一个权衡。因子太小如1.1倍会导致扩容频繁因子太大如2倍则可能浪费较多内存。1.5倍是一个经验值在时间和空间效率上取得了较好的平衡。3. 核心细节解析与实操要点理解了整体设计我们开始深入每个核心方法的实现细节。这里处处是“坑”一个疏忽就可能导致程序崩溃或数据错乱。3.1 构造方法起始容量的选择顺序表应该提供至少两个构造方法一个无参构造使用默认容量一个带参构造允许使用者指定初始容量。public MyArrayList() { this(DEFAULT_CAPACITY); // 委托给带参构造 } public MyArrayList(int initialCapacity) { if (initialCapacity 0) { throw new IllegalArgumentException(初始容量不能为负数: initialCapacity); } this.elementData new Object[initialCapacity]; this.size 0; }要点必须对传入的initialCapacity进行合法性校验。传入负数是没有意义的应该立即抛出异常快速失败Fail-Fast避免将错误隐藏到后续操作中。3.2 边界检查所有操作的守门员几乎每一个涉及索引参数的方法get,set,add,remove在开始逻辑之前都必须进行索引有效性检查。检查的逻辑是索引index必须满足0 index size。我们可以将这个检查抽成一个私有方法private void rangeCheck(int index) { if (index 0 || index size) { throw new IndexOutOfBoundsException(索引: index , 当前大小: size); } }对于add(int index, E element)方法其索引的有效范围是0 index size允许在size处插入即在尾部添加。因此它需要一个单独的检查方法rangeCheckForAdd。实操心得不要小看这个简单的检查。在复杂的业务逻辑中一个越界访问可能导致难以调试的ArrayIndexOutOfBoundsException甚至 silently corrupt data静默数据损坏。提前进行显式的、信息丰富的异常抛出是提高代码健壮性的关键。3.3 添加操作插入与扩容的艺术添加操作有两个核心方法add(E e)在尾部添加和add(int index, E e)在指定位置插入。尾部添加add(E e) 这是最常用的操作。逻辑是确保容量足够ensureCapacityInternal(size 1)。将元素e赋值给elementData[size]。size自增1。指定位置插入add(int index, E e) 这是顺序表最体现其“顺序”特性的操作也是最耗时的操作之一平均时间复杂度O(n)。逻辑是检查索引合法性rangeCheckForAdd。确保容量足够。关键步骤将index位置及之后的所有元素都向后移动一位。这是通过System.arraycopy方法实现的。// 将elementData从index开始拷贝到index1的位置共拷贝(size-index)个元素 System.arraycopy(elementData, index, elementData, index 1, size - index);将新元素e放入腾出的index位置。size自增1。扩容方法ensureCapacityInternal 这是顺序表的“发动机”。当minCapacity所需最小容量大于当前数组长度时触发。private void ensureCapacityInternal(int minCapacity) { if (minCapacity - elementData.length 0) { grow(minCapacity); } } private void grow(int minCapacity) { int oldCapacity elementData.length; // 核心计算新容量。新容量 旧容量 * 1.5 int newCapacity oldCapacity (oldCapacity 1); // 如果按1.5倍扩容后仍小于所需最小容量则直接使用所需容量 if (newCapacity - minCapacity 0) { newCapacity minCapacity; } // 一些实现会在这里处理大容量情况防止溢出此处简化 elementData Arrays.copyOf(elementData, newCapacity); }注意Arrays.copyOf底层也是调用了System.arraycopy。移动或拷贝数组元素时务必使用这些原生方法而不是自己写for循环。原生方法是本地方法Native Method由JVM底层优化性能远高于Java层面的循环。3.4 删除操作移动元素与清理引用删除操作同样有两个核心remove(int index)按索引删除和remove(Object o)按元素删除。按索引删除remove(int index)边界检查rangeCheck。取出待删除的元素用于返回。关键步骤计算需要移动的元素数量numMoved size - index - 1。如果大于0则将index1位置开始的元素向前移动一位。System.arraycopy(elementData, index 1, elementData, index, numMoved);将数组末尾现在是size-1位置的元素置为null。size自减1返回被删除的元素。第4步将末尾置null至关重要这被称为“清理过期引用”。如果不这样做这个位置仍然持有对对象的强引用即使这个对象在逻辑上已经被移出顺序表垃圾回收器GC也无法回收它可能导致内存泄漏。这是很多人在实现自定义数据结构时容易忽略的细节。按元素删除remove(Object o)遍历数组使用equals方法或处理null找到第一个匹配的元素索引。如果找到调用remove(int index)方法进行删除。返回是否删除成功。要点这里涉及到null值的处理。如果顺序表允许存储null那么remove(null)应该删除第一个null元素。在查找时判断条件应为(o null ? elementData[i] null : o.equals(elementData[i]))。3.5 查找与修改随机访问的优势get(int index)和set(int index, E e)是顺序表效率最高的操作时间复杂度为O(1)因为它们直接通过数组下标进行访问。public E get(int index) { rangeCheck(index); return (E) elementData[index]; // 需要强制转换并抑制警告泛型版本可避免 } public E set(int index, E element) { rangeCheck(index); E oldValue (E) elementData[index]; elementData[index] element; return oldValue; }注意类型安全由于我们使用了Object[]在返回元素时需要强制转换为E这会产生“unchecked cast”的编译警告。在完整的泛型实现中我们会使用(E[]) new Object[capacity]来创建数组但这本身也是一个类型擦除的“把戏”需要SuppressWarnings(“unchecked”)注解。indexOf(Object o)方法则是线性查找时间复杂度O(n)。实现时同样需要注意null值的处理。4. 完整代码实现与逐行解析下面我将给出一个相对完整的、带有基础泛型支持的MyArrayList实现并对关键代码进行逐行解析。/** * 一个简化的顺序表实现模仿ArrayList的核心功能。 * param E 顺序表中元素的类型 */ public class MyArrayListE { /** * 默认初始容量。 */ private static final int DEFAULT_CAPACITY 10; /** * 用于空实例的共享空数组。 */ private static final Object[] EMPTY_ELEMENTDATA {}; /** * 存储元素的数组缓冲区。 * MyArrayList的容量是这个数组缓冲区的长度。 * 当第一个元素被添加时任何以默认大小()创建的空MyArrayList * 其elementData EMPTY_ELEMENTDATA 将被扩展到DEFAULT_CAPACITY。 */ private Object[] elementData; /** * MyArrayList的大小它包含的元素数量。 */ private int size; /** * 构造一个具有指定初始容量的空列表。 * param initialCapacity 列表的初始容量 * throws IllegalArgumentException 如果指定的初始容量为负 */ public MyArrayList(int initialCapacity) { if (initialCapacity 0) { this.elementData new Object[initialCapacity]; } else if (initialCapacity 0) { this.elementData EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException(非法容量: initialCapacity); } this.size 0; } /** * 构造一个初始容量为10的空列表。 */ public MyArrayList() { this.elementData EMPTY_ELEMENTDATA; // 延迟初始化第一次添加时才真正分配DEFAULT_CAPACITY } /** * 将指定的元素追加到此列表的末尾。 * param e 要添加到此列表的元素 * return true (根据Collection.add的规范) */ public boolean add(E e) { ensureCapacityInternal(size 1); // 确保容量足够modCount此处省略了快速失败机制modCount elementData[size] e; return true; } /** * 在此列表中的指定位置插入指定的元素。 * 将当前位于该位置的元素如果有和任何后续元素向右移动将其索引加一。 * param index 要插入指定元素的索引 * param element 要插入的元素 * throws IndexOutOfBoundsException 如果索引超出范围 (index 0 || index size()) */ public void add(int index, E element) { rangeCheckForAdd(index); // 检查index是否在0到size之间含 ensureCapacityInternal(size 1); // 关键数组拷贝将index及之后的元素后移一位 // 参数含义(源数组, 源起始位置, 目标数组, 目标起始位置, 拷贝长度) System.arraycopy(elementData, index, elementData, index 1, size - index); elementData[index] element; size; } /** * 移除此列表中指定位置的元素。 * 将任何后续元素向左移动将其索引减一。 * param index 要移除的元素的索引 * return 从列表中移除的元素 * throws IndexOutOfBoundsException 如果索引超出范围 (index 0 || index size()) */ public E remove(int index) { rangeCheck(index); // 检查index是否在0到size-1之间含 E oldValue elementData(index); // 获取旧值 int numMoved size - index - 1; // 计算需要移动的元素个数 if (numMoved 0) { // 关键数组拷贝将index1及之后的元素前移一位 System.arraycopy(elementData, index 1, elementData, index, numMoved); } // 重要将末尾位置置为null帮助GC elementData[--size] null; return oldValue; } /** * 移除此列表中首次出现的指定元素如果存在。 * param o 要从此列表中移除的元素如果存在 * return 如果此列表包含指定的元素则返回 true */ public boolean remove(Object o) { if (o null) { for (int i 0; i size; i) { if (elementData[i] null) { fastRemove(i); // 快速删除不返回旧值 return true; } } } else { for (int i 0; i size; i) { if (o.equals(elementData[i])) { fastRemove(i); return true; } } } return false; } /** * 快速删除不进行边界检查也不返回被删除的值。 * 仅供内部remove(Object)方法调用。 */ private void fastRemove(int index) { int numMoved size - index - 1; if (numMoved 0) { System.arraycopy(elementData, index 1, elementData, index, numMoved); } elementData[--size] null; } /** * 返回此列表中指定位置的元素。 * param index 要返回的元素的索引 * return 此列表中指定位置的元素 * throws IndexOutOfBoundsException 如果索引超出范围 (index 0 || index size()) */ public E get(int index) { rangeCheck(index); return elementData(index); } /** * 用指定的元素替换此列表中指定位置的元素。 * param index 要替换的元素的索引 * param element 要存储在指定位置的元素 * return 先前在指定位置的元素 * throws IndexOutOfBoundsException 如果索引超出范围 (index 0 || index size()) */ public E set(int index, E element) { rangeCheck(index); E oldValue elementData(index); elementData[index] element; return oldValue; } /** * 返回此列表中的元素数。 * return 此列表中的元素数 */ public int size() { return size; } /** * 如果此列表不包含元素则返回 true。 * return 如果此列表不包含元素则返回 true */ public boolean isEmpty() { return size 0; } /** * 从此列表中移除所有元素。此调用返回后列表将为空。 */ public void clear() { // 清空所有引用帮助GC for (int i 0; i size; i) { elementData[i] null; } size 0; } /** * 返回此列表中指定元素首次出现的索引如果此列表不包含该元素则返回 -1。 * param o 要搜索的元素 * return 此列表中指定元素首次出现的索引如果此列表不包含该元素则返回 -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; } // ------------- 私有工具方法 ------------- /** * 检查给定的索引是否在范围内。 */ private void rangeCheck(int index) { if (index 0 || index size) { throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } } /** * add和addAll使用的rangeCheck版本。 */ private void rangeCheckForAdd(int index) { if (index 0 || index size) { throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } } /** * 构造一个IndexOutOfBoundsException详细消息。 */ private String outOfBoundsMsg(int index) { return 索引: index , 大小: size; } /** * 类型安全的元素获取。 */ SuppressWarnings(unchecked) private E elementData(int index) { return (E) elementData[index]; } /** * 确保内部容量至少满足最小容量minCapacity。 */ private void ensureCapacityInternal(int minCapacity) { // 如果当前是空数组延迟初始化则至少扩容到默认容量 if (elementData EMPTY_ELEMENTDATA) { minCapacity Math.max(DEFAULT_CAPACITY, minCapacity); } if (minCapacity - elementData.length 0) { grow(minCapacity); } } /** * 扩容以确保它能至少容纳最小容量参数指定的元素数。 */ private void grow(int minCapacity) { int oldCapacity elementData.length; // 新容量 旧容量 * 1.5 (即 oldCapacity oldCapacity/2) int newCapacity oldCapacity (oldCapacity 1); // 如果新容量仍然小于最小所需容量则直接使用最小所需容量 if (newCapacity - minCapacity 0) { newCapacity minCapacity; } // 一些极端情况处理此处简化实际ArrayList会处理大容量和溢出 elementData Arrays.copyOf(elementData, newCapacity); } /** * 返回此列表的字符串表示形式。 */ Override public String toString() { if (size 0) { return []; } StringBuilder sb new StringBuilder(); sb.append([); for (int i 0; i size; i) { sb.append(elementData[i]); if (i size - 1) { sb.append(]); } else { sb.append(,).append( ); } } return sb.toString(); } }关键代码解析延迟初始化在无参构造器中我们将elementData初始化为EMPTY_ELEMENTDATA一个空的共享数组。直到第一次调用add方法时才在ensureCapacityInternal中将其真正扩容到DEFAULT_CAPACITY。这样做的好处是如果用户创建了MyArrayList但从未使用可以节省内存。快速删除fastRemove这是一个内部优化方法被remove(Object)调用。因为它已经知道索引是有效的在遍历中找到的并且不需要返回被删除的元素所以跳过了边界检查和保存旧值的步骤稍微提升了一点性能。System.arraycopy的使用这是实现插入和删除元素移动的核心。务必理解其五个参数的含义源数组、源起始位置、目标数组、目标起始位置、拷贝长度。它在内存层面进行批量拷贝效率远高于循环。clear()方法它不仅仅是将size设为0还循环将数组前size个位置的引用都置为null。这是为了防止“内存泄漏”即虽然逻辑上列表空了但数组仍然持有对那些对象的引用阻止GC回收它们。5. 常见问题与排查技巧实录自己动手实现一遍再对比JDK中的ArrayList源码你会发现很多值得深思的细节。下面是我在实现和教学过程中学员们最常遇到的问题和对应的排查思路。5.1 并发修改异常ConcurrentModificationException的模拟与理解我们的简易版MyArrayList没有实现modCount机制但这是ArrayList防止在迭代过程中被结构性修改如add, remove的重要机制。你可以尝试这样理解问题MyArrayListString list new MyArrayList(); list.add(A); list.add(B); list.add(C); // 模拟迭代过程 for (int i 0; i list.size(); i) { if (B.equals(list.get(i))) { list.remove(i); // 在遍历中删除元素 } } System.out.println(list); // 输出 [A, C]没问题 // 但如果用 for-each 或 Iterator在真正的ArrayList中就会抛异常排查技巧在单线程中使用索引遍历并删除元素是安全的但要注意删除后索引i不应该自增或者应该自减i--因为后面的元素会前移。在多线程环境下任何遍历过程中的结构性修改都是不安全的必须加锁或使用并发集合如CopyOnWriteArrayList。5.2 插入或删除后数据错乱或越界这通常是数组拷贝的方向或长度计算错误导致的。症状插入后部分数据被覆盖或丢失删除后末尾出现奇怪的数据或后续访问越界。排查检查System.arraycopy的五个参数。源起始位置和目标起始位置最容易混淆。记住插入时目标是index1源是index删除时目标是index源是index1。检查拷贝长度。插入时长度是size - index将index及之后的元素后移删除时长度是size - index - 1将index1及之后的元素前移。画图辅助在纸上画一个数组标出index和size手动模拟移动过程是解决这类问题最直观的方法。5.3 内存泄漏与“脏数据”这个问题比较隐蔽但危害很大。症状程序运行一段时间后内存占用异常高即使逻辑上已经删除了大量对象。排查检查remove(int index)和clear()方法是否将不再引用的数组位置置为了null。我们的代码在remove的最后有elementData[--size] null;在clear()中有循环置null的操作。使用Java Profiling工具如JVisualVM, YourKit, JProfiler观察堆内存中对象的实例数量和引用链看是否有本应被回收的对象仍然被我们的数组引用着。心得在管理自己分配的内存这里是对象引用数组时要时刻怀有“谁申请谁释放”的责任心。虽然Java有GC但程序员仍需负责解除无用的引用。5.4 性能瓶颈分析与优化方向虽然顺序表的随机访问是O(1)但插入和删除尤其是头部是O(n)的。这是由其连续存储的物理结构决定的。场景如果你需要频繁在列表头部进行插入和删除操作MyArrayList以及ArrayList会非常慢因为每次操作都需要移动后面所有的元素。优化选择此时你应该考虑使用LinkedList链表。链表在头部插入删除是O(1)但随机访问是O(n)。排查工具使用System.currentTimeMillis()或System.nanoTime()在关键操作前后计时进行简单的性能测试。更专业的可以使用JMHJava Microbenchmark Harness进行基准测试。5.5 与标准库ArrayList的差异我们的MyArrayList是一个教学简化版与JDK中的ArrayList相比缺少了以下重要特性了解这些差异有助于你更深入地理解工业级代码Fail-Fast迭代器通过modCount字段实现。任何结构性修改改变列表大小的操作都会使modCount递增。迭代器在每次操作前会检查modCount是否与创建时一致不一致则抛出ConcurrentModificationException。序列化支持ArrayList实现了Serializable接口但它的elementData被标记为transient。它自定义了writeObject和readObject方法只序列化实际存储的元素size个而不是整个数组以节省空间。容量裁剪trimToSizeArrayList提供了一个trimToSize()方法可以将底层数组的容量裁剪到当前元素个数以释放多余的内存。批量操作ArrayList提供了addAll(Collection),removeAll(Collection)等批量操作方法内部进行了优化。更健壮的容量处理ArrayList的grow方法会处理超大容量接近Integer.MAX_VALUE的情况防止溢出。实现这个简易的顺序表就像亲手搭建了一个积木房子。你清楚了每一块积木数组、索引、扩容的位置和作用。下次当你使用ArrayList时你不再把它当作一个黑盒你会知道每一次add背后可能发生的数组拷贝每一次remove时GC可能因此受益你会更清楚在什么场景下该选择它又在什么场景下该选择LinkedList或CopyOnWriteArrayList。这种从底层理解带来的掌控感是仅仅调用API无法获得的。我建议你不仅看懂代码最好能关掉这篇文章自己从头到尾默写实现一遍过程中遇到的每一个问题都会让你对数据结构的理解更深一分。