1. 从“纸面理论”到“一行行代码”：为什么顺序表是算法入门的基石

如果你刚开始接触数据结构，或者正在准备一场技术面试，那么“线性表”这个概念你肯定绕不过去。而顺序表，作为线性表最直观、最基础的物理实现方式，往往是很多人数据结构之旅的起点。但说实话，很多教程和书籍讲到这里，常常是画个数组图，列几个插入删除的公式，然后就直接跳到链表了。这导致很多朋友学完之后，脑子里只剩下“哦，顺序表就是数组”，至于它到底怎么用代码组织起来、在实际编程中会遇到哪些坑、为什么面试官总爱拿它和链表做比较，反而成了一团浆糊。

我自己带新人或者面试初级开发者时，发现一个普遍现象：能背出顺序表插入时间复杂度是O(n)的人很多，但能清晰解释这个O(n)在代码层面是如何产生的、在什么场景下这个开销可以接受或必须避免的人，却少得多。这中间的差距，就是“知道”和“会用”的鸿沟。今天，我们不谈那些复杂的公式推导，就从一个Java开发者的视角，亲手把顺序表从概念“实现”出来。我会带你写一个最精简但功能完整的顺序表，并在实现过程中，穿插那些只有真正动手写过、调试过才会遇到的“坑”和“技巧”。你会发现，实现一个顺序表，远不止声明一个数组那么简单，它涉及到容量管理、边界检查、数据搬移等一系列工程化细节，而这些细节，恰恰是理解更复杂数据结构的基础。

2. 顺序表的本质：一段连续内存与三个核心属性

在开始敲代码之前，我们必须先统一思想：顺序表到底是什么？你可以把它想象成一个高级的、自带管理功能的“数组”。数组是Java提供的最基础的连续内存存储结构，但它太“原始”了——长度固定，你需要自己记录里面存了多少个有效元素。顺序表就是在数组这个“物理结构”之上，封装出来的一套“逻辑结构”，它对外提供了一组统一的、易于使用的操作接口（如增删改查），而内部则默默处理了数组容量不足时的扩容、删除元素时的数据搬移等脏活累活。

一个完整的顺序表，通常需要维护三个核心属性：

1. 存储数据的数组：这是数据的物理载体，比如int[] data或Object[] data。
2. 当前有效元素个数：我们记为size。这是理解顺序表的关键。数组的长度（capacity）是它最大能装多少，而size是它当前已经装了多少。size永远小于等于capacity。
3. 初始容量或扩容因子：这决定了顺序表的“弹性”。一个设计良好的顺序表不能一开始就分配一个巨大的数组（浪费内存），也不能在每次加一个元素时就扩容（性能低下）。我们需要一个合理的策略。

为什么是连续内存？这是顺序表所有特性的根源。因为内存连续，所以我们可以用data[0]、data[1]这种方式，以常数时间 O(1) 随机访问任何一个位置的元素。这个优势是链表不具备的。但也正因为连续，当我们需要在中间插入或删除元素时，为了保持连续性，就必须移动后续的所有元素，这就导致了O(n)的时间复杂度。理解了这个“优势与代价的共生关系”，你就能明白顺序表和链表各自的应用场景。

3. 手把手实现一个泛型顺序表

理论说再多，不如一行代码。我们来实现一个支持泛型（Generic）的顺序表MyArrayList。使用泛型意味着我们的顺序表可以存放任意类型的对象，而不仅仅是整数或字符串，这大大增强了其通用性。

3.1 类的骨架与构造函数

首先，我们定义类的成员变量和构造函数。

public class MyArrayList<E> { // 存储元素的数组 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); } } }

关键点解析与踩坑提醒：

1. 为什么用Object[]而不是E[]？这是Java泛型擦除机制下的一个经典选择。直接声明E[] elementData = (E[]) new Object[capacity];在编译时会有“未检查的转换”警告。虽然两种方式都能工作，但使用Object[]并在返回元素时进行类型转换(E) elementData[index]是更常见、警告更清晰的做法。JDK自身的ArrayList也采用了Object[]。
2. size的初始值必须是0。这是一个新手极易忽略的细节。size表示有效元素个数，刚创建的顺序表当然是空的。如果你错误地初始化成其他值（比如elementData.length），后续所有基于size的逻辑都会崩盘。
3. 容量合法性校验。在带参构造器中，我们必须对用户传入的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等多个方法中重复编写相同的校验代码，符合DRY（Don‘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++，你就把新元素放到size+1的位置了，中间会留下一个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) { // 搬移数据：将index+1及其之后的元素，整体向左移动一位 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; }

删除操作的关键细节：

1. 置空的重要性：elementData[--size] = null;这行代码至关重要。数组的该位置已经不属于逻辑上的顺序表了（因为size减小了），但物理上这个引用还指向原来的对象。如果不置为null，这个引用会阻止垃圾回收器（GC）回收那个对象，即使程序逻辑上已经不再需要它。这被称为“游离引用”，是导致内存泄漏的常见原因之一。
2. fastRemove的优化：remove(Object o)方法内部调用了fastRemove。因为在这个方法里，我们已经通过遍历找到了确切的索引i，并且知道i是有效的（0 <= i < size），所以可以跳过公共的checkIndex检查，并且不需要返回被删除的值，从而提升一点性能。这是JDKArrayList源码中使用的相同技巧。
3. 对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. 创建与添加 MyArrayList<String> 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. 扩容测试 MyArrayList<Integer> 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)） MyArrayList<Integer> 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. 链表：如何根据场景做选择？

实现完顺序表，你自然就会想到它的老对手——链表。面试中“顺序表和链表的区别”是必问题。现在你可以从实现者的角度来回答，而不仅仅是背八股文。

选择指南（来自实战经验）：

• 优先选择顺序表的情况：

  • 频繁按索引访问：例如，你需要实现一个排行榜，经常要取第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，它还缺少很多工业级的特性：

1. 迭代器 (Iterator)：我们无法用for (String s : list)这种增强for循环来遍历。实现迭代器需要实现Iterable接口。
2. 并发安全：我们的类不是线程安全的。多个线程同时调用add可能导致数据错乱、size值不准确，甚至数组越界。ArrayList本身也不是线程安全的，但可以通过Collections.synchronizedList包装或使用CopyOnWriteArrayList。
3. 快速失败机制 (Fail-Fast)：在迭代过程中，如果其他线程（或本线程）修改了列表结构（增删元素），ArrayList的迭代器会立刻抛出ConcurrentModificationException，防止出现不可预期的行为。这通过一个modCount（修改计数器）来实现。
4. 容量裁剪 (trimToSize)：如果一次添加了大量元素后，又删除了很多，数组里会有大量空闲空间。ArrayList提供了trimToSize()方法，可以将内部数组裁剪到刚好容纳当前元素，节省内存。
5. 批量操作：如addAll(Collection),removeAll(Collection)等，这些方法在JDK中都有经过高度优化的实现。
6. 序列化支持：ArrayList实现了Serializable接口，并且自定义了writeObject和readObject方法，只序列化实际有效的元素（size个），而不是整个elementData数组，减少了序列化后的大小。

理解这些差异，能让你更深刻地认识到，一个生产可用的数据结构库，除了核心算法正确，还需要在性能、内存、安全、易用性等方方面面做大量的打磨。而这，正是我们学习数据结构，然后阅读优秀源码（比如JDK源码）的意义所在——知其然，并知其所以然，最终能为其然。