1. 从“纸面理论”到“一行行代码”为什么顺序表是算法入门的基石如果你刚开始接触数据结构或者正在准备一场技术面试那么“线性表”这个概念你肯定绕不过去。而顺序表作为线性表最直观、最基础的物理实现方式往往是很多人数据结构之旅的起点。但说实话很多教程和书籍讲到这里常常是画个数组图列几个插入删除的公式然后就直接跳到链表了。这导致很多朋友学完之后脑子里只剩下“哦顺序表就是数组”至于它到底怎么用代码组织起来、在实际编程中会遇到哪些坑、为什么面试官总爱拿它和链表做比较反而成了一团浆糊。我自己带新人或者面试初级开发者时发现一个普遍现象能背出顺序表插入时间复杂度是O(n)的人很多但能清晰解释这个O(n)在代码层面是如何产生的、在什么场景下这个开销可以接受或必须避免的人却少得多。这中间的差距就是“知道”和“会用”的鸿沟。今天我们不谈那些复杂的公式推导就从一个Java开发者的视角亲手把顺序表从概念“实现”出来。我会带你写一个最精简但功能完整的顺序表并在实现过程中穿插那些只有真正动手写过、调试过才会遇到的“坑”和“技巧”。你会发现实现一个顺序表远不止声明一个数组那么简单它涉及到容量管理、边界检查、数据搬移等一系列工程化细节而这些细节恰恰是理解更复杂数据结构的基础。2. 顺序表的本质一段连续内存与三个核心属性在开始敲代码之前我们必须先统一思想顺序表到底是什么你可以把它想象成一个高级的、自带管理功能的“数组”。数组是Java提供的最基础的连续内存存储结构但它太“原始”了——长度固定你需要自己记录里面存了多少个有效元素。顺序表就是在数组这个“物理结构”之上封装出来的一套“逻辑结构”它对外提供了一组统一的、易于使用的操作接口如增删改查而内部则默默处理了数组容量不足时的扩容、删除元素时的数据搬移等脏活累活。一个完整的顺序表通常需要维护三个核心属性存储数据的数组这是数据的物理载体比如int[] data或Object[] data。当前有效元素个数我们记为size。这是理解顺序表的关键。数组的长度capacity是它最大能装多少而size是它当前已经装了多少。size永远小于等于capacity。初始容量或扩容因子这决定了顺序表的“弹性”。一个设计良好的顺序表不能一开始就分配一个巨大的数组浪费内存也不能在每次加一个元素时就扩容性能低下。我们需要一个合理的策略。为什么是连续内存这是顺序表所有特性的根源。因为内存连续所以我们可以用data[0]、data[1]这种方式以常数时间 O(1) 随机访问任何一个位置的元素。这个优势是链表不具备的。但也正因为连续当我们需要在中间插入或删除元素时为了保持连续性就必须移动后续的所有元素这就导致了O(n)的时间复杂度。理解了这个“优势与代价的共生关系”你就能明白顺序表和链表各自的应用场景。3. 手把手实现一个泛型顺序表理论说再多不如一行代码。我们来实现一个支持泛型Generic的顺序表MyArrayList。使用泛型意味着我们的顺序表可以存放任意类型的对象而不仅仅是整数或字符串这大大增强了其通用性。3.1 类的骨架与构造函数首先我们定义类的成员变量和构造函数。public class MyArrayListE { // 存储元素的数组 private Object[] elementData; // 当前顺序表中元素的数量 private int size; // 默认初始容量 private static final int DEFAULT_CAPACITY 10; /** * 构造一个具有默认初始容量的空列表。 */ public MyArrayList() { this.elementData new Object[DEFAULT_CAPACITY]; this.size 0; } /** * 构造一个具有指定初始容量的空列表。 * param initialCapacity 列表的初始容量 * throws IllegalArgumentException 如果初始容量为负数 */ public MyArrayList(int initialCapacity) { if (initialCapacity 0) { this.elementData new Object[initialCapacity]; this.size 0; } else if (initialCapacity 0) { this.elementData new Object[]{}; } else { throw new IllegalArgumentException(非法容量: initialCapacity); } } }关键点解析与踩坑提醒为什么用Object[]而不是E[]这是Java泛型擦除机制下的一个经典选择。直接声明E[] elementData (E[]) new Object[capacity];在编译时会有“未检查的转换”警告。虽然两种方式都能工作但使用Object[]并在返回元素时进行类型转换(E) elementData[index]是更常见、警告更清晰的做法。JDK自身的ArrayList也采用了Object[]。size的初始值必须是0。这是一个新手极易忽略的细节。size表示有效元素个数刚创建的顺序表当然是空的。如果你错误地初始化成其他值比如elementData.length后续所有基于size的逻辑都会崩盘。容量合法性校验。在带参构造器中我们必须对用户传入的initialCapacity进行检查。传入负数必须抛出异常这是健壮性编程的基本要求。传入0可以创建一个空数组这在某些“已知元素极少”的场景下可以节省内存。3.2 基础辅助方法size(),isEmpty(),checkIndex()在实现核心的增删改查前我们先写几个简单但至关重要的辅助方法。/** * 返回顺序表中的元素数量。 */ public int size() { return size; } /** * 判断顺序表是否为空。 */ public boolean isEmpty() { return size 0; } /** * 检查索引是否在有效范围内 (0 index size)。 * 用于所有需要索引参数的方法内部。 * param index 待检查的索引 * throws IndexOutOfBoundsException 如果索引越界 */ private void checkIndex(int index) { if (index 0 || index size) { throw new IndexOutOfBoundsException(索引: index , 大小: size); } }经验之谈把索引检查抽象成一个独立的私有方法checkIndex是很好的工程实践。它避免了在get、set、remove等多个方法中重复编写相同的校验代码符合DRYDon‘t Repeat Yourself原则。当校验逻辑需要修改时比如以后想支持负索引从末尾计数你只需要改这一个地方。3.3 核心操作之“查”与“改”get()和set()查和改是顺序表的优势操作因为它们不涉及元素移动。/** * 返回指定索引位置的元素。 * param index 要返回的元素的索引 * return 该索引处的元素 * throws IndexOutOfBoundsException 如果索引越界 */ public E get(int index) { checkIndex(index); // 先检查索引是否合法 return (E) elementData[index]; // 类型转换 } /** * 用指定元素替换指定索引位置的元素并返回被替换的旧元素。 * param index 要替换的元素的索引 * param element 要存储在指定位置的新元素 * return 之前位于该位置的元素 * throws IndexOutOfBoundsException 如果索引越界 */ public E set(int index, E element) { checkIndex(index); E oldValue (E) elementData[index]; elementData[index] element; return oldValue; }这里有个小技巧set方法返回旧值是一个很贴心的设计。这样调用者可以在替换元素的同时知道之前这里存的是什么在某些场景下如undo操作非常有用。虽然我们的简单实现可能用不到但这体现了API设计的完备性思考。3.4 核心操作之“增”add()与动态扩容策略“增”是顺序表最有趣也最需要小心的地方因为它可能触发扩容。我们先实现一个在末尾添加的简单方法/** * 将指定元素追加到列表的末尾。 * param element 要添加的元素 * return true (因为List接口的约定) */ public boolean add(E element) { // 关键添加前先确保容量足够 ensureCapacityInternal(size 1); elementData[size] element; size; // 重要先赋值再增加size return true; }看到ensureCapacityInternal了吗这就是扩容逻辑的入口。我们来实现它/** * 确保内部数组至少有 minCapacity 那么大。 * param minCapacity 所需的最小容量 */ private void ensureCapacityInternal(int minCapacity) { if (minCapacity - elementData.length 0) { // 当前容量不足需要扩容 grow(minCapacity); } } /** * 扩容核心方法。 * param minCapacity 所需的最小容量 */ private void grow(int minCapacity) { int oldCapacity elementData.length; // 新容量 旧容量的1.5倍。这是ArrayList的标准策略在时间和空间上取得了较好平衡。 int newCapacity oldCapacity (oldCapacity 1); // 如果1.5倍扩容后仍小于最小需求则直接使用最小需求容量。 // 这种情况通常发生在初始化旧容量为0或一次性添加大量元素时。 if (newCapacity - minCapacity 0) { newCapacity minCapacity; } // 一些JVM实现可能有上限这里我们简单处理。实际ArrayList会处理巨大容量。 if (newCapacity Integer.MAX_VALUE - 8) { newCapacity hugeCapacity(minCapacity); } // 核心操作创建新数组拷贝旧数据 elementData Arrays.copyOf(elementData, newCapacity); } private static int hugeCapacity(int minCapacity) { if (minCapacity 0) { // 溢出 throw new OutOfMemoryError(); } return (minCapacity Integer.MAX_VALUE - 8) ? Integer.MAX_VALUE : Integer.MAX_VALUE - 8; }扩容策略深度解析这是顺序表实现中最具艺术性的部分。为什么是1.5倍oldCapacity (oldCapacity 1)时间与空间的权衡扩容成本很高需要分配新内存和拷贝所有数据。如果扩容倍数太小比如每次只增加10个位置那么频繁添加元素会导致频繁扩容性能低下。如果扩容倍数太大比如每次翻倍虽然扩容次数少了但可能会造成大量的内存浪费很多空间闲置。1.5倍是一个经验值在多数场景下取得了较好的平衡。像Python的list、Go的slice也采用类似的策略Go是2倍。位运算优化oldCapacity 1是oldCapacity / 2的等价位运算但通常更快。这是底层代码中常见的微优化。Arrays.copyOf的便利性这个方法底层调用了System.arraycopy这是一个本地native方法由JVM实现效率远高于我们自己用循环拷贝。一个极易出错的细节在add(E element)方法中elementData[size] element;和size;的顺序绝对不能颠倒。你必须先赋值再增加size。因为size始终指向下一个待插入元素的位置也是当前有效元素的末尾。如果先size你就把新元素放到size1的位置了中间会留下一个null的空洞并且原来的size位置数据是未定义的。接下来我们实现更通用的在任意位置插入/** * 在列表的指定位置插入指定元素。将当前位于该位置的元素如果有和任何后续元素向右移动。 * param index 要在其中插入指定元素的索引 * param element 要插入的元素 * throws IndexOutOfBoundsException 如果索引越界这里index可以等于size表示末尾插入 */ public void add(int index, E element) { // 注意这里允许 index size表示在末尾添加 if (index 0 || index size) { throw new IndexOutOfBoundsException(索引: index , 大小: size); } // 1. 确保容量足够 ensureCapacityInternal(size 1); // 2. 搬移数据将index及其之后的元素整体向右移动一位 // System.arraycopy(源数组, 源起始位置, 目标数组, 目标起始位置, 拷贝长度) System.arraycopy(elementData, index, elementData, index 1, size - index); // 3. 放入新元素 elementData[index] element; // 4. 更新大小 size; }这是顺序表插入操作时间复杂度O(n)的直观体现System.arraycopy(elementData, index, elementData, index 1, size - index);这一行代码平均需要移动n/2个元素。如果插入位置在开头则需要移动全部n个元素。这就是“连续存储”带来的代价。3.5 核心操作之“删”remove()与数据搬移删除操作同样需要移动元素以填补被删除元素留下的“空洞”。/** * 移除列表中指定位置的元素。将任何后续元素向左移动。 * param index 要移除的元素的索引 * return 从列表中移除的元素 * throws IndexOutOfBoundsException 如果索引越界 */ public E remove(int index) { checkIndex(index); E oldValue (E) elementData[index]; // 计算需要移动的元素个数 int numMoved size - index - 1; if (numMoved 0) { // 搬移数据将index1及其之后的元素整体向左移动一位 System.arraycopy(elementData, index 1, elementData, index, numMoved); } // 重要将最后一个位置置为null帮助垃圾回收并防止内存泄漏 elementData[--size] null; return oldValue; } /** * 移除列表中首次出现的指定元素如果存在。 * param o 要移除的元素可以为null * 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; } // 私有快速移除方法跳过边界检查因为调用处已保证索引有效不返回被删除的值。 private void fastRemove(int index) { int numMoved size - index - 1; if (numMoved 0) { System.arraycopy(elementData, index 1, elementData, index, numMoved); } elementData[--size] null; }删除操作的关键细节置空的重要性elementData[--size] null;这行代码至关重要。数组的该位置已经不属于逻辑上的顺序表了因为size减小了但物理上这个引用还指向原来的对象。如果不置为null这个引用会阻止垃圾回收器GC回收那个对象即使程序逻辑上已经不再需要它。这被称为“游离引用”是导致内存泄漏的常见原因之一。fastRemove的优化remove(Object o)方法内部调用了fastRemove。因为在这个方法里我们已经通过遍历找到了确切的索引i并且知道i是有效的0 i size所以可以跳过公共的checkIndex检查并且不需要返回被删除的值从而提升一点性能。这是JDKArrayList源码中使用的相同技巧。对null的支持remove(Object o)方法需要处理传入对象o为null的情况。在遍历比较时必须用来判断null用equals()来判断非null对象这是遵循List接口的规范。3.6 工具方法clear(),indexOf(),contains()最后我们再实现几个常用的工具方法让我们的顺序表更实用。/** * 移除列表中的所有元素。 */ public void clear() { // 显式地将所有有效位置的引用置为null帮助GC for (int i 0; i size; i) { elementData[i] null; } size 0; } /** * 返回指定元素在列表中首次出现的索引如果列表不包含该元素则返回-1。 * param o 要查找的元素 */ 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; } /** * 判断列表是否包含指定元素。 * param o 要测试是否存在的元素 */ public boolean contains(Object o) { return indexOf(o) 0; } /** * 返回列表的字符串表示形式。 */ 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(); }clear()的注意点和remove方法中的置空一样clear()也需要遍历数组将引用置null而不是简单地size 0。否则数组里那些引用依然持有对象导致GC无法回收。4. 实战测试与性能分析现在让我们写个简单的main方法来测试一下我们的MyArrayList并直观感受一下顺序表的特性。public class TestMyArrayList { public static void main(String[] args) { // 1. 创建与添加 MyArrayListString list new MyArrayList(); System.out.println(初始状态: list , size list.size() , isEmpty list.isEmpty()); list.add(Apple); list.add(Banana); list.add(1, Orange); // 在索引1处插入 System.out.println(添加后: list); // 2. 查询与修改 System.out.println(索引1的元素: list.get(1)); String old list.set(1, Grape); System.out.println(替换索引1旧值: old , 新列表: list); // 3. 删除 list.remove(0); System.out.println(删除索引0后: list); boolean removed list.remove(Banana); System.out.println(删除‘Banana‘结果: removed , 列表: list); // 4. 扩容测试 MyArrayListInteger intList new MyArrayList(3); for (int i 0; i 10; i) { intList.add(i); // 观察添加过程中的内部数组长度需要通过反射这里仅示意 System.out.println(添加 i 后size intList.size()); } System.out.println(最终列表: intList); // 5. 性能对比感知 // 在末尾添加很快O(1)平均偶尔触发扩容O(n) // 在开头插入很慢每次都是O(n) MyArrayListInteger perfList new MyArrayList(); long start System.nanoTime(); for (int i 0; i 100000; i) { perfList.add(i); // 末尾添加 } long end System.nanoTime(); System.out.println(在末尾添加100000个元素耗时: (end - start) / 1_000_000 ms); perfList.clear(); start System.nanoTime(); for (int i 0; i 10000; i) { // 数量减少因为开头插入太慢 perfList.add(0, i); // 总是在开头插入 } end System.nanoTime(); System.out.println(在开头插入10000个元素耗时: (end - start) / 1_000_000 ms); } }运行这个测试你可以清晰地看到基本操作增删改查都正常工作。当不断添加元素导致容量不足时顺序表会自动扩容虽然代码里没直接打印容量但你可以通过添加日志或反射来观察。最重要的你会看到“末尾添加”和“开头插入”巨大的性能差异。这就是顺序表随机访问快、但中间插入删除慢的特性在数据上的直接体现。5. 顺序表 vs. 链表如何根据场景做选择实现完顺序表你自然就会想到它的老对手——链表。面试中“顺序表和链表的区别”是必问题。现在你可以从实现者的角度来回答而不仅仅是背八股文。特性顺序表 (ArrayList)链表 (LinkedList)底层存储连续内存数组分散内存节点通过指针连接随机访问O(1)通过索引直接计算地址O(n)需要从头遍历头部插入/删除O(n)需要移动后面所有元素O(1)修改指针即可尾部插入/删除O(1) (均摊)偶尔触发扩容O(1) (双向链表)中间插入/删除O(n)需要移动元素O(n)需要先遍历找到位置内存占用较小只存数据本身内存连续较大每个节点需额外存储指针内存利用率可能有容量浪费预留空间按需分配无浪费缓存友好性好数据连续容易被CPU缓存命中差数据分散缓存命中率低选择指南来自实战经验优先选择顺序表的情况频繁按索引访问例如你需要实现一个排行榜经常要取第1、第10、第100名的数据。遍历操作远多于插入删除例如存储一批配置项初始化后主要就是读取和遍历。元素总量可预估或增长平稳避免频繁扩容。如果你知道大概要存1000个元素就用new ArrayList(1000)初始化一次分配好空间效率最高。追求极致的遍历速度顺序表连续的内存布局对CPU缓存预取非常友好遍历起来比链表快得多。优先选择链表的情况频繁在头部或中间插入/删除例如实现一个撤销Undo操作栈总是在头部进行操作。元素数量巨大且频繁变动无法预估大小链表每次插入只分配一个节点没有扩容开销。需要实现队列、双端队列等结构链表在两端操作的效率很高。一个常见的误区很多人觉得链表插入删除就是O(1)所以一定比顺序表快。这忽略了“找到插入位置”的成本。如果你要在链表中间插入你需要先遍历找到那个节点这个操作本身就是O(n)。只有在你已经持有要插入位置节点的引用时链表的插入才是真正的O(1)。而顺序表即使要移动数据但因为是连续内存可以用高效的System.arraycopy批量操作在数据量不是特别大时实际速度可能比链表遍历更快。这就是为什么在实际开发中ArrayList的使用频率远高于LinkedList。6. 从玩具到工业级我们实现的顺序表还缺什么我们实现的MyArrayList是一个教学版的、功能完整的顺序表它帮你理解了所有核心原理。但对比JDK中的java.util.ArrayList它还缺少很多工业级的特性迭代器 (Iterator)我们无法用for (String s : list)这种增强for循环来遍历。实现迭代器需要实现Iterable接口。并发安全我们的类不是线程安全的。多个线程同时调用add可能导致数据错乱、size值不准确甚至数组越界。ArrayList本身也不是线程安全的但可以通过Collections.synchronizedList包装或使用CopyOnWriteArrayList。快速失败机制 (Fail-Fast)在迭代过程中如果其他线程或本线程修改了列表结构增删元素ArrayList的迭代器会立刻抛出ConcurrentModificationException防止出现不可预期的行为。这通过一个modCount修改计数器来实现。容量裁剪 (trimToSize)如果一次添加了大量元素后又删除了很多数组里会有大量空闲空间。ArrayList提供了trimToSize()方法可以将内部数组裁剪到刚好容纳当前元素节省内存。批量操作如addAll(Collection),removeAll(Collection)等这些方法在JDK中都有经过高度优化的实现。序列化支持ArrayList实现了Serializable接口并且自定义了writeObject和readObject方法只序列化实际有效的元素size个而不是整个elementData数组减少了序列化后的大小。理解这些差异能让你更深刻地认识到一个生产可用的数据结构库除了核心算法正确还需要在性能、内存、安全、易用性等方方面面做大量的打磨。而这正是我们学习数据结构然后阅读优秀源码比如JDK源码的意义所在——知其然并知其所以然最终能为其然。 1. 从“纸面理论”到“一行行代码”为什么顺序表是算法入门的基石如果你刚开始接触数据结构或者正在准备一场技术面试那么“线性表”这个概念你肯定绕不过去。而顺序表作为线性表最直观、最基础的物理实现方式往往是很多人数据结构之旅的起点。但说实话很多教程和书籍讲到这里常常是画个数组图列几个插入删除的公式然后就直接跳到链表了。这导致很多朋友学完之后脑子里只剩下“哦顺序表就是数组”至于它到底怎么用代码组织起来、在实际编程中会遇到哪些坑、为什么面试官总爱拿它和链表做比较反而成了一团浆糊。我自己带新人或者面试初级开发者时发现一个普遍现象能背出顺序表插入时间复杂度是O(n)的人很多但能清晰解释这个O(n)在代码层面是如何产生的、在什么场景下这个开销可以接受或必须避免的人却少得多。这中间的差距就是“知道”和“会用”的鸿沟。今天我们不谈那些复杂的公式推导就从一个Java开发者的视角亲手把顺序表从概念“实现”出来。我会带你写一个最精简但功能完整的顺序表并在实现过程中穿插那些只有真正动手写过、调试过才会遇到的“坑”和“技巧”。你会发现实现一个顺序表远不止声明一个数组那么简单它涉及到容量管理、边界检查、数据搬移等一系列工程化细节而这些细节恰恰是理解更复杂数据结构的基础。2. 顺序表的本质一段连续内存与三个核心属性在开始敲代码之前我们必须先统一思想顺序表到底是什么你可以把它想象成一个高级的、自带管理功能的“数组”。数组是Java提供的最基础的连续内存存储结构但它太“原始”了——长度固定你需要自己记录里面存了多少个有效元素。顺序表就是在数组这个“物理结构”之上封装出来的一套“逻辑结构”它对外提供了一组统一的、易于使用的操作接口如增删改查而内部则默默处理了数组容量不足时的扩容、删除元素时的数据搬移等脏活累活。一个完整的顺序表通常需要维护三个核心属性存储数据的数组这是数据的物理载体比如int[] data或Object[] data。当前有效元素个数我们记为size。这是理解顺序表的关键。数组的长度capacity是它最大能装多少而size是它当前已经装了多少。size永远小于等于capacity。初始容量或扩容因子这决定了顺序表的“弹性”。一个设计良好的顺序表不能一开始就分配一个巨大的数组浪费内存也不能在每次加一个元素时就扩容性能低下。我们需要一个合理的策略。为什么是连续内存这是顺序表所有特性的根源。因为内存连续所以我们可以用data[0]、data[1]这种方式以常数时间 O(1) 随机访问任何一个位置的元素。这个优势是链表不具备的。但也正因为连续当我们需要在中间插入或删除元素时为了保持连续性就必须移动后续的所有元素这就导致了O(n)的时间复杂度。理解了这个“优势与代价的共生关系”你就能明白顺序表和链表各自的应用场景。3. 手把手实现一个泛型顺序表理论说再多不如一行代码。我们来实现一个支持泛型Generic的顺序表MyArrayList。使用泛型意味着我们的顺序表可以存放任意类型的对象而不仅仅是整数或字符串这大大增强了其通用性。3.1 类的骨架与构造函数首先我们定义类的成员变量和构造函数。public class MyArrayListE { // 存储元素的数组 private Object[] elementData; // 当前顺序表中元素的数量 private int size; // 默认初始容量 private static final int DEFAULT_CAPACITY 10; /** * 构造一个具有默认初始容量的空列表。 */ public MyArrayList() { this.elementData new Object[DEFAULT_CAPACITY]; this.size 0; } /** * 构造一个具有指定初始容量的空列表。 * param initialCapacity 列表的初始容量 * throws IllegalArgumentException 如果初始容量为负数 */ public MyArrayList(int initialCapacity) { if (initialCapacity 0) { this.elementData new Object[initialCapacity]; this.size 0; } else if (initialCapacity 0) { this.elementData new Object[]{}; } else { throw new IllegalArgumentException(非法容量: initialCapacity); } } }关键点解析与踩坑提醒为什么用Object[]而不是E[]这是Java泛型擦除机制下的一个经典选择。直接声明E[] elementData (E[]) new Object[capacity];在编译时会有“未检查的转换”警告。虽然两种方式都能工作但使用Object[]并在返回元素时进行类型转换(E) elementData[index]是更常见、警告更清晰的做法。JDK自身的ArrayList也采用了Object[]。size的初始值必须是0。这是一个新手极易忽略的细节。size表示有效元素个数刚创建的顺序表当然是空的。如果你错误地初始化成其他值比如elementData.length后续所有基于size的逻辑都会崩盘。容量合法性校验。在带参构造器中我们必须对用户传入的initialCapacity进行检查。传入负数必须抛出异常这是健壮性编程的基本要求。传入0可以创建一个空数组这在某些“已知元素极少”的场景下可以节省内存。3.2 基础辅助方法size(),isEmpty(),checkIndex()在实现核心的增删改查前我们先写几个简单但至关重要的辅助方法。/** * 返回顺序表中的元素数量。 */ public int size() { return size; } /** * 判断顺序表是否为空。 */ public boolean isEmpty() { return size 0; } /** * 检查索引是否在有效范围内 (0 index size)。 * 用于所有需要索引参数的方法内部。 * param index 待检查的索引 * throws IndexOutOfBoundsException 如果索引越界 */ private void checkIndex(int index) { if (index 0 || index size) { throw new IndexOutOfBoundsException(索引: index , 大小: size); } }经验之谈把索引检查抽象成一个独立的私有方法checkIndex是很好的工程实践。它避免了在get、set、remove等多个方法中重复编写相同的校验代码符合DRYDon‘t Repeat Yourself原则。当校验逻辑需要修改时比如以后想支持负索引从末尾计数你只需要改这一个地方。3.3 核心操作之“查”与“改”get()和set()查和改是顺序表的优势操作因为它们不涉及元素移动。/** * 返回指定索引位置的元素。 * param index 要返回的元素的索引 * return 该索引处的元素 * throws IndexOutOfBoundsException 如果索引越界 */ public E get(int index) { checkIndex(index); // 先检查索引是否合法 return (E) elementData[index]; // 类型转换 } /** * 用指定元素替换指定索引位置的元素并返回被替换的旧元素。 * param index 要替换的元素的索引 * param element 要存储在指定位置的新元素 * return 之前位于该位置的元素 * throws IndexOutOfBoundsException 如果索引越界 */ public E set(int index, E element) { checkIndex(index); E oldValue (E) elementData[index]; elementData[index] element; return oldValue; }这里有个小技巧set方法返回旧值是一个很贴心的设计。这样调用者可以在替换元素的同时知道之前这里存的是什么在某些场景下如undo操作非常有用。虽然我们的简单实现可能用不到但这体现了API设计的完备性思考。3.4 核心操作之“增”add()与动态扩容策略“增”是顺序表最有趣也最需要小心的地方因为它可能触发扩容。我们先实现一个在末尾添加的简单方法/** * 将指定元素追加到列表的末尾。 * param element 要添加的元素 * return true (因为List接口的约定) */ public boolean add(E element) { // 关键添加前先确保容量足够 ensureCapacityInternal(size 1); elementData[size] element; size; // 重要先赋值再增加size return true; }看到ensureCapacityInternal了吗这就是扩容逻辑的入口。我们来实现它/** * 确保内部数组至少有 minCapacity 那么大。 * param minCapacity 所需的最小容量 */ private void ensureCapacityInternal(int minCapacity) { if (minCapacity - elementData.length 0) { // 当前容量不足需要扩容 grow(minCapacity); } } /** * 扩容核心方法。 * param minCapacity 所需的最小容量 */ private void grow(int minCapacity) { int oldCapacity elementData.length; // 新容量 旧容量的1.5倍。这是ArrayList的标准策略在时间和空间上取得了较好平衡。 int newCapacity oldCapacity (oldCapacity 1); // 如果1.5倍扩容后仍小于最小需求则直接使用最小需求容量。 // 这种情况通常发生在初始化旧容量为0或一次性添加大量元素时。 if (newCapacity - minCapacity 0) { newCapacity minCapacity; } // 一些JVM实现可能有上限这里我们简单处理。实际ArrayList会处理巨大容量。 if (newCapacity Integer.MAX_VALUE - 8) { newCapacity hugeCapacity(minCapacity); } // 核心操作创建新数组拷贝旧数据 elementData Arrays.copyOf(elementData, newCapacity); } private static int hugeCapacity(int minCapacity) { if (minCapacity 0) { // 溢出 throw new OutOfMemoryError(); } return (minCapacity Integer.MAX_VALUE - 8) ? Integer.MAX_VALUE : Integer.MAX_VALUE - 8; }扩容策略深度解析这是顺序表实现中最具艺术性的部分。为什么是1.5倍oldCapacity (oldCapacity 1)时间与空间的权衡扩容成本很高需要分配新内存和拷贝所有数据。如果扩容倍数太小比如每次只增加10个位置那么频繁添加元素会导致频繁扩容性能低下。如果扩容倍数太大比如每次翻倍虽然扩容次数少了但可能会造成大量的内存浪费很多空间闲置。1.5倍是一个经验值在多数场景下取得了较好的平衡。像Python的list、Go的slice也采用类似的策略Go是2倍。位运算优化oldCapacity 1是oldCapacity / 2的等价位运算但通常更快。这是底层代码中常见的微优化。Arrays.copyOf的便利性这个方法底层调用了System.arraycopy这是一个本地native方法由JVM实现效率远高于我们自己用循环拷贝。一个极易出错的细节在add(E element)方法中elementData[size] element;和size;的顺序绝对不能颠倒。你必须先赋值再增加size。因为size始终指向下一个待插入元素的位置也是当前有效元素的末尾。如果先size你就把新元素放到size1的位置了中间会留下一个null的空洞并且原来的size位置数据是未定义的。接下来我们实现更通用的在任意位置插入/** * 在列表的指定位置插入指定元素。将当前位于该位置的元素如果有和任何后续元素向右移动。 * param index 要在其中插入指定元素的索引 * param element 要插入的元素 * throws IndexOutOfBoundsException 如果索引越界这里index可以等于size表示末尾插入 */ public void add(int index, E element) { // 注意这里允许 index size表示在末尾添加 if (index 0 || index size) { throw new IndexOutOfBoundsException(索引: index , 大小: size); } // 1. 确保容量足够 ensureCapacityInternal(size 1); // 2. 搬移数据将index及其之后的元素整体向右移动一位 // System.arraycopy(源数组, 源起始位置, 目标数组, 目标起始位置, 拷贝长度) System.arraycopy(elementData, index, elementData, index 1, size - index); // 3. 放入新元素 elementData[index] element; // 4. 更新大小 size; }这是顺序表插入操作时间复杂度O(n)的直观体现System.arraycopy(elementData, index, elementData, index 1, size - index);这一行代码平均需要移动n/2个元素。如果插入位置在开头则需要移动全部n个元素。这就是“连续存储”带来的代价。3.5 核心操作之“删”remove()与数据搬移删除操作同样需要移动元素以填补被删除元素留下的“空洞”。/** * 移除列表中指定位置的元素。将任何后续元素向左移动。 * param index 要移除的元素的索引 * return 从列表中移除的元素 * throws IndexOutOfBoundsException 如果索引越界 */ public E remove(int index) { checkIndex(index); E oldValue (E) elementData[index]; // 计算需要移动的元素个数 int numMoved size - index - 1; if (numMoved 0) { // 搬移数据将index1及其之后的元素整体向左移动一位 System.arraycopy(elementData, index 1, elementData, index, numMoved); } // 重要将最后一个位置置为null帮助垃圾回收并防止内存泄漏 elementData[--size] null; return oldValue; } /** * 移除列表中首次出现的指定元素如果存在。 * param o 要移除的元素可以为null * 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; } // 私有快速移除方法跳过边界检查因为调用处已保证索引有效不返回被删除的值。 private void fastRemove(int index) { int numMoved size - index - 1; if (numMoved 0) { System.arraycopy(elementData, index 1, elementData, index, numMoved); } elementData[--size] null; }删除操作的关键细节置空的重要性elementData[--size] null;这行代码至关重要。数组的该位置已经不属于逻辑上的顺序表了因为size减小了但物理上这个引用还指向原来的对象。如果不置为null这个引用会阻止垃圾回收器GC回收那个对象即使程序逻辑上已经不再需要它。这被称为“游离引用”是导致内存泄漏的常见原因之一。fastRemove的优化remove(Object o)方法内部调用了fastRemove。因为在这个方法里我们已经通过遍历找到了确切的索引i并且知道i是有效的0 i size所以可以跳过公共的checkIndex检查并且不需要返回被删除的值从而提升一点性能。这是JDKArrayList源码中使用的相同技巧。对null的支持remove(Object o)方法需要处理传入对象o为null的情况。在遍历比较时必须用来判断null用equals()来判断非null对象这是遵循List接口的规范。3.6 工具方法clear(),indexOf(),contains()最后我们再实现几个常用的工具方法让我们的顺序表更实用。/** * 移除列表中的所有元素。 */ public void clear() { // 显式地将所有有效位置的引用置为null帮助GC for (int i 0; i size; i) { elementData[i] null; } size 0; } /** * 返回指定元素在列表中首次出现的索引如果列表不包含该元素则返回-1。 * param o 要查找的元素 */ 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; } /** * 判断列表是否包含指定元素。 * param o 要测试是否存在的元素 */ public boolean contains(Object o) { return indexOf(o) 0; } /** * 返回列表的字符串表示形式。 */ 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(); }clear()的注意点和remove方法中的置空一样clear()也需要遍历数组将引用置null而不是简单地size 0。否则数组里那些引用依然持有对象导致GC无法回收。4. 实战测试与性能分析现在让我们写个简单的main方法来测试一下我们的MyArrayList并直观感受一下顺序表的特性。public class TestMyArrayList { public static void main(String[] args) { // 1. 创建与添加 MyArrayListString list new MyArrayList(); System.out.println(初始状态: list , size list.size() , isEmpty list.isEmpty()); list.add(Apple); list.add(Banana); list.add(1, Orange); // 在索引1处插入 System.out.println(添加后: list); // 2. 查询与修改 System.out.println(索引1的元素: list.get(1)); String old list.set(1, Grape); System.out.println(替换索引1旧值: old , 新列表: list); // 3. 删除 list.remove(0); System.out.println(删除索引0后: list); boolean removed list.remove(Banana); System.out.println(删除‘Banana‘结果: removed , 列表: list); // 4. 扩容测试 MyArrayListInteger intList new MyArrayList(3); for (int i 0; i 10; i) { intList.add(i); // 观察添加过程中的内部数组长度需要通过反射这里仅示意 System.out.println(添加 i 后size intList.size()); } System.out.println(最终列表: intList); // 5. 性能对比感知 // 在末尾添加很快O(1)平均偶尔触发扩容O(n) // 在开头插入很慢每次都是O(n) MyArrayListInteger perfList new MyArrayList(); long start System.nanoTime(); for (int i 0; i 100000; i) { perfList.add(i); // 末尾添加 } long end System.nanoTime(); System.out.println(在末尾添加100000个元素耗时: (end - start) / 1_000_000 ms); perfList.clear(); start System.nanoTime(); for (int i 0; i 10000; i) { // 数量减少因为开头插入太慢 perfList.add(0, i); // 总是在开头插入 } end System.nanoTime(); System.out.println(在开头插入10000个元素耗时: (end - start) / 1_000_000 ms); } }运行这个测试你可以清晰地看到基本操作增删改查都正常工作。当不断添加元素导致容量不足时顺序表会自动扩容虽然代码里没直接打印容量但你可以通过添加日志或反射来观察。最重要的你会看到“末尾添加”和“开头插入”巨大的性能差异。这就是顺序表随机访问快、但中间插入删除慢的特性在数据上的直接体现。5. 顺序表 vs. 链表如何根据场景做选择实现完顺序表你自然就会想到它的老对手——链表。面试中“顺序表和链表的区别”是必问题。现在你可以从实现者的角度来回答而不仅仅是背八股文。特性顺序表 (ArrayList)链表 (LinkedList)底层存储连续内存数组分散内存节点通过指针连接随机访问O(1)通过索引直接计算地址O(n)需要从头遍历头部插入/删除O(n)需要移动后面所有元素O(1)修改指针即可尾部插入/删除O(1) (均摊)偶尔触发扩容O(1) (双向链表)中间插入/删除O(n)需要移动元素O(n)需要先遍历找到位置内存占用较小只存数据本身内存连续较大每个节点需额外存储指针内存利用率可能有容量浪费预留空间按需分配无浪费缓存友好性好数据连续容易被CPU缓存命中差数据分散缓存命中率低选择指南来自实战经验优先选择顺序表的情况频繁按索引访问例如你需要实现一个排行榜经常要取第1、第10、第100名的数据。遍历操作远多于插入删除例如存储一批配置项初始化后主要就是读取和遍历。元素总量可预估或增长平稳避免频繁扩容。如果你知道大概要存1000个元素就用new ArrayList(1000)初始化一次分配好空间效率最高。追求极致的遍历速度顺序表连续的内存布局对CPU缓存预取非常友好遍历起来比链表快得多。优先选择链表的情况频繁在头部或中间插入/删除例如实现一个撤销Undo操作栈总是在头部进行操作。元素数量巨大且频繁变动无法预估大小链表每次插入只分配一个节点没有扩容开销。需要实现队列、双端队列等结构链表在两端操作的效率很高。一个常见的误区很多人觉得链表插入删除就是O(1)所以一定比顺序表快。这忽略了“找到插入位置”的成本。如果你要在链表中间插入你需要先遍历找到那个节点这个操作本身就是O(n)。只有在你已经持有要插入位置节点的引用时链表的插入才是真正的O(1)。而顺序表即使要移动数据但因为是连续内存可以用高效的System.arraycopy批量操作在数据量不是特别大时实际速度可能比链表遍历更快。这就是为什么在实际开发中ArrayList的使用频率远高于LinkedList。6. 从玩具到工业级我们实现的顺序表还缺什么我们实现的MyArrayList是一个教学版的、功能完整的顺序表它帮你理解了所有核心原理。但对比JDK中的java.util.ArrayList它还缺少很多工业级的特性迭代器 (Iterator)我们无法用for (String s : list)这种增强for循环来遍历。实现迭代器需要实现Iterable接口。并发安全我们的类不是线程安全的。多个线程同时调用add可能导致数据错乱、size值不准确甚至数组越界。ArrayList本身也不是线程安全的但可以通过Collections.synchronizedList包装或使用CopyOnWriteArrayList。快速失败机制 (Fail-Fast)在迭代过程中如果其他线程或本线程修改了列表结构增删元素ArrayList的迭代器会立刻抛出ConcurrentModificationException防止出现不可预期的行为。这通过一个modCount修改计数器来实现。容量裁剪 (trimToSize)如果一次添加了大量元素后又删除了很多数组里会有大量空闲空间。ArrayList提供了trimToSize()方法可以将内部数组裁剪到刚好容纳当前元素节省内存。批量操作如addAll(Collection),removeAll(Collection)等这些方法在JDK中都有经过高度优化的实现。序列化支持ArrayList实现了Serializable接口并且自定义了writeObject和readObject方法只序列化实际有效的元素size个而不是整个elementData数组减少了序列化后的大小。理解这些差异能让你更深刻地认识到一个生产可用的数据结构库除了核心算法正确还需要在性能、内存、安全、易用性等方方面面做大量的打磨。而这正是我们学习数据结构然后阅读优秀源码比如JDK源码的意义所在——知其然并知其所以然最终能为其然。 
