1. 项目概述从零开始理解顺序表很多刚接触数据结构的朋友一听到“线性表”、“顺序表”这些词可能就觉得头大感觉是些抽象又枯燥的理论。但如果你写过Java用过ArrayList那你其实已经在用顺序表了。今天我们不谈那些复杂的数学推导和严苛的定义就从一个Java程序员最熟悉的视角出发亲手用最基础的数组实现一个我们自己的“迷你版ArrayList”——也就是顺序表。这不仅仅是完成一个作业或面试题更重要的是通过这个看似简单的过程你能彻底搞懂ArrayList内部是怎么工作的为什么它能动态扩容以及增删改查这些操作背后真实的性能开销。理解了这些你再看ArrayList的源码就会有一种“原来如此”的通透感这才是我们学习数据结构最实在的收获。2. 顺序表的核心设计与实现思路2.1 为什么是数组顺序表的本质剖析顺序表顾名思义就是用一段连续的物理存储单元来依次存放线性表中的数据元素。在Java的世界里最符合这个描述的就是数组。数组在内存中占据一块连续的空间我们可以通过一个整数索引下标在O(1)的时间复杂度内直接访问到任何一个位置的元素这是它最核心的优势也是顺序表实现“随机访问”能力的基石。那么直接用数组不就行了吗为什么还要封装成顺序表因为原生的数组有个致命缺点长度固定。一旦初始化其容量就不可改变。而我们的数据集合往往是动态变化的有时需要插入新元素有时需要删除旧元素。顺序表就是在数组的基础上增加了一套动态管理的逻辑。它内部维护一个数组并记录当前已经存放了多少个有效元素我们称之为size。当数组快满时它会自动创建一个更大的新数组把老数据拷贝过去从而实现“扩容”。ArrayList的底层就是这么干的。所以我们实现顺序表的核心思路就是用一个Object[]数组作为底层存储用一个int变量size记录当前有效元素个数然后围绕这个数组实现一整套增、删、改、查、扩容的方法。2.2 接口定义我们要实现哪些功能在动手写代码之前我们先规划好这个顺序表类我们叫它MyArrayList应该具备哪些基本功能。这其实就是定义我们自己的“API契约”。一个最基础的顺序表通常包括以下操作初始化创建一个指定初始容量的空顺序表。获取元素根据索引位置获取元素。更新元素根据索引位置设置新的元素值。添加元素在顺序表末尾添加一个元素。在指定索引位置插入一个元素这个位置及之后的元素都要向后挪动。删除元素删除指定索引位置的元素这个位置之后的元素都要向前挪动。删除第一个匹配的指定值的元素。查找元素查找指定值在顺序表中第一次出现的索引。判断状态判断顺序表是否为空、是否已满对我们动态扩容的实现来说“已满”是个临时状态。获取信息获取当前顺序表的元素个数size和底层数组的总容量。清空逻辑上清空顺序表通常只需将size置为0无需清空数组每个位置这是一种“懒”处理效率更高。扩容当数组容量不足时自动进行扩容这是实现动态性的关键。我们将围绕这些功能点来构建我们的MyArrayList。3. 核心代码实现与逐行解析下面我们开始动手实现。我会先给出完整的类结构然后对关键方法进行逐行解析并解释每一步的意图和注意事项。/** * 一个简单的顺序表实现 * param E 顺序表中存储的元素类型 */ public class MyArrayListE { // 核心成员变量 private Object[] elementData; // 底层存储数组使用Object类型以保证通用性 private int size; // 当前顺序表中有效元素的个数 private static final int DEFAULT_CAPACITY 10; // 默认初始容量 // 构造方法 public MyArrayList() { this(DEFAULT_CAPACITY); // 无参构造使用默认容量 } public MyArrayList(int initialCapacity) { if (initialCapacity 0) { throw new IllegalArgumentException(初始容量必须大于0: initialCapacity); } this.elementData new Object[initialCapacity]; this.size 0; } // 1. 基础信息获取方法 public int size() { return size; } public boolean isEmpty() { return size 0; } public int capacity() { return elementData.length; } // 2. 核心动态扩容机制 private void ensureCapacity(int minCapacity) { int oldCapacity elementData.length; if (minCapacity oldCapacity) { // 新容量计算策略旧容量的1.5倍但至少满足minCapacity int newCapacity oldCapacity (oldCapacity 1); // oldCapacity * 1.5 if (newCapacity minCapacity) { newCapacity minCapacity; } // 数组拷贝是扩容的性能瓶颈 elementData Arrays.copyOf(elementData, newCapacity); System.out.println(触发扩容: oldCapacity - newCapacity); } } // 3. 添加元素尾插法 public boolean add(E e) { // 添加前确保容量足够。当前size表示下一个元素要插入的位置所以需要size1的空间。 ensureCapacity(size 1); elementData[size] e; // 在size位置放入元素然后size自增 return true; } // 4. 添加元素在指定索引处插入 public void add(int index, E element) { // 索引越界检查插入位置必须在[0, size]之间。注意允许在size处插入即尾部追加。 rangeCheckForAdd(index); // 确保容量足够 ensureCapacity(size 1); // 核心将index及其之后的所有元素向后移动一位 // 从最后一个有效元素(size-1)开始倒序移动到index位置 for (int i size - 1; i index; i--) { elementData[i 1] elementData[i]; } // 在腾出的index位置放入新元素 elementData[index] element; size; // 元素总数增加 } // 5. 获取元素 SuppressWarnings(unchecked) public E get(int index) { // 获取元素的索引必须在[0, size)范围内 rangeCheck(index); // 强制类型转换因为我们知道存储的是E类型 return (E) elementData[index]; } // 6. 设置更新元素 SuppressWarnings(unchecked) public E set(int index, E element) { rangeCheck(index); E oldValue (E) elementData[index]; elementData[index] element; return oldValue; // 返回被替换的旧值这是模仿标准API的设计 } // 7. 删除元素按索引删除 SuppressWarnings(unchecked) public E remove(int index) { rangeCheck(index); E removedElement (E) elementData[index]; // 核心将index之后的所有元素向前移动一位 // 从index1开始正序移动到size-1 for (int i index 1; i size; i) { elementData[i - 1] elementData[i]; } // 将最后一个位置原size-1位置移动后已空出置为null帮助GC回收 elementData[--size] null; return removedElement; } // 8. 删除元素按值删除删除第一个匹配项 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; // 未找到匹配项 } // 内部快速删除方法避免重复检查 private void fastRemove(int index) { // 移动元素的逻辑与remove(int index)相同 for (int i index 1; i size; i) { elementData[i - 1] elementData[i]; } elementData[--size] null; } // 9. 查找元素索引 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; // 未找到 } // 10. 清空 public void clear() { // 显式地将所有有效位置置为null帮助GC回收对象 for (int i 0; i size; i) { elementData[i] null; } size 0; // 逻辑清空 } // 11. 转换为字符串方便调试打印 Override public String toString() { if (size 0) { return []; } 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(); } // 私有辅助方法索引越界检查用于get, set, remove private void rangeCheck(int index) { if (index 0 || index size) { throw new IndexOutOfBoundsException(索引: index , 大小: size); } } // 私有辅助方法索引越界检查用于add允许index size private void rangeCheckForAdd(int index) { if (index 0 || index size) { throw new IndexOutOfBoundsException(插入索引: index , 大小: size); } } }3.1 关键方法深度解析1. 扩容机制ensureCapacity(int minCapacity)这是顺序表动态性的灵魂。参数minCapacity表示至少需要的最小容量。当size 1即插入一个新元素后需要的容量大于当前数组长度时触发扩容。新容量计算int newCapacity oldCapacity (oldCapacity 1);这行代码是精髓。oldCapacity 1是位运算等价于oldCapacity / 2。所以newCapacity oldCapacity * 1.5。这是ArrayList默认的扩容策略不同JDK版本可能微调在空间和时间效率上取得了较好的平衡。一次性扩容太多浪费空间扩容太少则会导致频繁拷贝。Arrays.copyOf这是实际执行扩容操作的方法。它在底层创建了一个指定新容量的新数组并将老数组的元素拷贝过去。这是一个O(n)的操作是顺序表添加操作最耗时的部分。为什么是1.5倍这是一个经验值。数学上当扩容因子为黄金比例(≈1.618)时在多次扩容后之前被浪费的空间可以被重新利用总体内存使用率较高。1.5是一个接近且易于计算的近似值。2. 指定位置插入add(int index, E element)这是顺序表最体现其数据结构特性的操作也是性能瓶颈之一。rangeCheckForAdd(index)注意这里允许index size这等同于在尾部添加。元素移动for (int i size - 1; i index; i--)这个循环是核心。它必须从后往前移动元素。如果从前往后移动你会用elementData[index]覆盖elementData[index1]导致数据丢失。想象一下整理书架如果你想在中间插入一本新书必须先把后面的书一本本往后挪出一个空位而不能先把前面的书往后推。时间复杂度这个移动操作平均需要移动n/2个元素因此平均时间复杂度为O(n)。在最坏情况在头部插入下需要移动所有n个元素时间复杂度为O(n)。3. 按索引删除remove(int index)这是插入操作的逆过程。元素移动for (int i index 1; i size; i)这个循环是从前往后移动将后面的元素覆盖到前一个位置。置空操作elementData[--size] null;这行代码非常重要。在移动完成后原来最后一个有效元素size-1位置已经被复制到了前一个位置size-2。此时size-1位置还保留着那个对象的引用。我们将size先减1然后将这个位置新的size位置即原size-1位置的引用置为null。这样做是为了避免“内存泄漏”。如果不置null这个已经不属于顺序表逻辑范围的引用依然指向那个对象垃圾回收器GC就无法回收它即使程序其他地方已经不再使用它。时间复杂度与插入类似平均O(n)最坏O(n)。4. 按值删除remove(Object o)和查找indexOf(Object o)这两个方法都涉及遍历和判等。null值处理这是Java集合类的一个通用约定。因为null调用.equals()会抛出NullPointerException所以必须对null值进行特殊处理使用进行判断。遍历它们都需要从头开始遍历数组直到找到匹配项或遍历结束。平均时间复杂度为O(n)。fastRemove这是一个内部辅助方法将按索引删除的逻辑复用避免代码重复。4. 实战测试与性能观察代码写完了我们得跑起来看看验证功能并直观感受一下顺序表操作的特点。下面是一个简单的测试类public class MyArrayListTest { public static void main(String[] args) { // 1. 初始化测试 MyArrayListString list new MyArrayList(5); // 初始容量设为5方便观察扩容 System.out.println(初始化后 - 容量: list.capacity() , 大小: list.size() , 是否为空: list.isEmpty()); // 2. 添加元素测试尾插 list.add(Apple); list.add(Banana); list.add(Cherry); System.out.println(添加3个元素后: list); // 3. 指定位置插入测试 list.add(1, Blueberry); // 在索引1Banana之前插入 System.out.println(在索引1插入Blueberry后: list); // 观察Banana, Cherry 是否向后移动了 // 4. 扩容测试继续添加触发扩容 list.add(Date); list.add(Elderberry); System.out.println(添加Date和Elderberry后: list); // 此时应有5个元素容量为5刚好满 list.add(Fig); // 添加第6个元素应触发扩容 System.out.println(添加Fig后: list); System.out.println(当前容量: list.capacity()); // 预期扩容为 5 5/2 7 (JDK的整数计算) // 5. 获取和设置测试 System.out.println(索引2的元素是: list.get(2)); // 应为 Cherry String old list.set(3, Durian); System.out.println(将索引3从 old 替换为 Durian 后: list); // 6. 按索引删除测试 String removed list.remove(0); System.out.println(删除索引0的元素 \ removed \ 后: list); // 观察所有元素是否向前移动了一位Fig的索引是否变了 // 7. 按值删除测试 boolean isRemoved list.remove(Cherry); System.out.println(删除 \Cherry\ 是否成功: isRemoved , 删除后: list); // 8. 查找测试 int index list.indexOf(Durian); System.out.println(\Durian\ 的索引是: index); index list.indexOf(Mango); System.out.println(\Mango\ 的索引是: index (未找到返回-1)); // 9. 清空测试 list.clear(); System.out.println(清空后 - 大小: list.size() , 是否为空: list.isEmpty() , 列表: list); } }运行这个测试你会看到类似以下的输出初始化后 - 容量: 5, 大小: 0, 是否为空: true 添加3个元素后: [Apple, Banana, Cherry] 在索引1插入Blueberry后: [Apple, Blueberry, Banana, Cherry] 添加Date和Elderberry后: [Apple, Blueberry, Banana, Cherry, Date, Elderberry] 触发扩容: 5 - 7 添加Fig后: [Apple, Blueberry, Banana, Cherry, Date, Elderberry, Fig] 当前容量: 7 索引2的元素是: Banana 将索引3从 Cherry 替换为 Durian 后: [Apple, Blueberry, Banana, Durian, Date, Elderberry, Fig] 删除索引0的元素 Apple 后: [Blueberry, Banana, Durian, Date, Elderberry, Fig] 删除 Cherry 是否成功: false, 删除后: [Blueberry, Banana, Durian, Date, Elderberry, Fig] Durian 的索引是: 2 Mango 的索引是: -1 (未找到返回-1) 清空后 - 大小: 0, 是否为空: true, 列表: []通过输出你可以清晰地看到插入时元素的移动、扩容的触发时机和新容量、删除后元素的移动以及索引的变化。5. 顺序表的优缺点与适用场景分析通过亲手实现我们对顺序表的特性有了血肉般的认识。现在来系统总结一下它的优缺点这决定了我们何时该用它。5.1 核心优势随机访问效率极高由于底层是数组通过索引get(int index)、set(int index, E element)操作的时间复杂度是O(1)。这是它最核心的竞争力。如果你需要频繁地根据位置读取或修改数据顺序表是首选。尾部操作效率高在顺序表末尾进行add(E e)和remove(int size-1)操作即栈的入栈出栈操作不需要移动元素时间复杂度也是O(1)不考虑扩容。内存空间局部性好数据在内存中连续存储CPU缓存命中率高遍历起来效率也很不错。实现简单直观逻辑清晰代码易于理解和维护。5.2 主要劣势插入/删除效率低在非尾部的位置进行插入或删除需要移动大量元素平均时间复杂度为O(n)。这是它最大的软肋。如果你的应用场景中频繁在列表中间增删数据顺序表的性能会急剧下降。内存空间要求连续扩容时需要找到一块更大的连续内存空间如果系统内存碎片化严重可能会触发更频繁的垃圾回收GC甚至导致OutOfMemoryError。存在空间浪费为了减少扩容频率通常会预留一些额外容量capacity size。这部分空间在未被使用前是浪费的。扩容成本高扩容操作Arrays.copyOf需要将旧数组所有元素复制到新数组这是一个O(n)的操作。虽然均摊到每次插入后成本不高均摊O(1)但单次扩容的瞬时延迟可能对实时性要求高的系统有影响。5.3 经典应用场景基于以上分析顺序表以及其代表ArrayList的适用场景非常明确“读多写少”且以随机访问为主例如从一个配置列表中按索引读取配置项存储一批计算好的结果供后续频繁查询实现一个栈只在一端操作或队列如果使用循环队列优化数据结构。数据量可预估或增长平稳如果你能大致知道数据量的上限可以在初始化时指定一个合理的容量从而完全避免或减少扩容次数。需要频繁遍历例如对集合中的所有元素进行某种计算或过滤。避坑指南何时不该用ArrayList当你需要频繁在列表头部或中部进行插入和删除操作时比如实现一个消息队列频繁在头部出队或者维护一个随时需要排序插入的有序列表使用ArrayList会带来大量的数据移动开销。这时你应该考虑使用链表LinkedList因为链表在任意位置的插入和删除如果已持有节点引用时间复杂度是O(1)。6. 与Java标准库ArrayList的对比与思考我们实现的MyArrayList是一个极度简化的教学模型。JDK中的ArrayList要复杂和健壮得多主要体现在并发控制ArrayList不是线程安全的。如果在多线程环境下使用需要外部同步或使用Collections.synchronizedList包装或者使用CopyOnWriteArrayList。迭代器与快速失败机制ArrayList提供了Iterator和ListIterator并且在迭代过程中如果检测到结构被修改除了通过迭代器自身的remove方法会抛出ConcurrentModificationException这就是“快速失败”机制用于帮助发现并发修改的错误。序列化支持实现了Serializable接口但通过transient修饰底层数组elementData并自定义了writeObject和readObject方法只序列化实际包含的元素size个而不是整个数组节省了空间。更细致的容量管理提供了trimToSize()方法将容量缩减至当前大小ensureCapacity()方法供用户手动提前扩容以避免后续自动扩容的开销。批量操作优化addAll(Collection c),removeRange(int fromIndex, int toIndex)等方法在系统层面可能进行了优化。从我们的实现中能学到什么通过这个简单的轮子我们穿透了ArrayList的黑盒理解了其动态扩容、随机访问、插入删除数据移动的本质。下次当你使用ArrayList时你就能做出更明智的选择如果知道大概数据量就用new ArrayList(initialCapacity)指定初始大小如果需要频繁在中间增删就考虑换用LinkedList遍历时优先使用for-each或Iterator而不是低效的for循环get对LinkedList尤其重要。这才是学习数据结构与算法最实在的价值——不是死记硬背概念而是获得一种预判和优化程序性能的直觉与能力。