Java顺序表实现：从静态数组到动态扩容的底层原理与实战

1. 项目概述：从“容器”到“基石”的认知跃迁

“顺序表”这个词，对于任何一个学过数据结构的人来说，都再熟悉不过了。它常常是数据结构课程的第一章，是算法竞赛选手的入门砖，也是面试官考察基础功底的“必考题”。但很多时候，我们仅仅把它当作一个需要背诵定义的“知识点”：一种线性结构，元素在物理存储上连续，支持随机访问……然后，就匆匆转向了链表、树、图这些看似更“高级”的结构。

然而，当我以一名一线开发者的视角，重新审视“顺序表”在Java中的实现时，我发现它远不止一个简单的知识点。它更像是一块被我们忽略的“基石”，是理解Java集合框架、内存管理乃至性能优化的绝佳入口。我们每天都在用的ArrayList，其底层就是一个动态扩容的顺序表。面试时被问到的“ArrayList和LinkedList有什么区别？”，其核心差异就源于顺序表和链表这两种最基础的数据结构。甚至，当你需要自己实现一个高性能、特定场景下的容器时，顺序表往往是你的第一选择，也是最佳选择。

因此，这篇内容的目的，不是复述教科书上的定义，而是带你从零开始，用Java亲手“造轮子”，实现一个功能完整、考虑周全的顺序表。我们将从最基础的静态数组开始，一步步演进到动态扩容，并在这个过程中，深入探讨每一个设计决策背后的“为什么”：为什么数组索引从0开始？为什么扩容因子通常是1.5或2？为什么add(int index, E element)方法的时间复杂度是O(n)？通过亲手实现，你将获得比单纯使用ArrayList深刻得多的理解。无论你是正在学习数据结构的学生，还是希望夯实基础的开发者，这篇文章都将为你提供一个清晰、透彻、可直接上手的实践指南。

2. 核心设计：从静态数组到动态容器的演进之路

2.1 静态数组的局限性与动态容器的需求

在Java中，最基础的顺序表实现就是数组。我们声明一个int[] arr = new int[10];，就得到了一个容量固定为10的顺序表。它的优势非常明显：内存连续，通过下标访问元素的速度是O(1)，即常数时间复杂度，这是最快的访问方式。

但它的劣势也同样致命：容量固定。一旦我们创建了一个长度为10的数组，就无法再容纳第11个元素。在实际开发中，数据量往往是未知或动态变化的。比如，我们从数据库读取用户列表，从文件解析日志行，或者处理一个实时数据流，我们无法预先知道确切的数量。这时，静态数组就显得力不从心。

于是，动态顺序表（或称动态数组）的概念应运而生。它的核心思想是：对外，它提供一个可以无限（受限于内存）添加元素的列表接口；对内，它维护一个底层数组，并实施一套“容量不足时自动扩容”的机制。Java标准库中的ArrayList正是这一思想的完美实现。我们的目标，就是模仿ArrayList，实现一个我们自己的MyArrayList。

2.2 类结构设计与核心成员变量

首先，我们来设计这个顺序表类的骨架。一个动态顺序表需要哪些核心部件？

1. 底层存储数组 (E[] data)：这是存储元素的真正容器。我们使用泛型E，让我们的顺序表可以存储任意类型的对象，增强通用性。
2. 当前元素个数 (int size)：这是顺序表逻辑上的大小，即用户已经添加了多少个元素。它永远小于或等于底层数组的物理容量(capacity)。
3. 默认初始容量 (DEFAULT_CAPACITY)：当用户没有指定初始大小时，我们提供一个合理的默认值。参考ArrayList，通常设为10。
4. 扩容因子：这是一个关键参数，决定了当数组满时，新数组应该是旧数组的多少倍。常见的值是1.5或2.0。过小会导致频繁扩容，性能损耗大；过大则可能浪费内存。我们这里采用和ArrayList类似的策略，但会显式地展示计算过程。

基于以上分析，我们的类定义如下：

/** * 一个简易的动态顺序表实现 * @param <E> 顺序表中元素的类型 */ public class MyArrayList<E> { // 底层存储数组 private E[] data; // 当前顺序表中元素的数量 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); } // 注意：不能直接创建泛型数组 new E[initialCapacity]，这是Java泛型的限制。 // 我们通过创建Object数组再强制转换的方式绕过限制，并加上@SuppressWarnings注解。 @SuppressWarnings("unchecked") E[] newData = (E[]) new Object[initialCapacity]; this.data = newData; this.size = 0; // 初始时没有元素 } }

注意：关于泛型数组的创建这是Java实现泛型容器时的一个经典“坑”。由于类型擦除，Java运行时并不知道E的具体类型，因此new E[capacity]这样的语法是不允许的。通用的解决方案是创建Object[]数组，然后在需要时强制转换为(E[])。虽然编译器会给出“未经检查的转换”警告，但我们通过@SuppressWarnings(“unchecked”)注解来抑制它，因为我们确信在类的内部，这个数组只会用来存储E类型的对象。ArrayList内部的实现也采用了类似的方式。

3. 核心操作实现：增删改查的细节与权衡

一个完整的数据结构，必须提供基本的增删改查(CRUD)操作。我们将逐一实现，并深入每个操作的细节。

3.1 基础查询与辅助方法

在实现增删之前，我们需要一些基础方法来获取状态和检查边界。

/** * 获取顺序表中元素的数量 * @return 元素个数 */ public int size() { return size; } /** * 判断顺序表是否为空 * @return 如果为空返回true，否则返回false */ public boolean isEmpty() { return size == 0; } /** * 获取顺序表当前的容量（底层数组的长度） * @return 当前容量 */ public int capacity() { return data.length; } /** * 检查索引是否在有效范围内 [0, size) * @param index 待检查的索引 */ private void rangeCheckForAdd(int index) { // 注意：添加时，index可以等于size（表示在末尾添加） if (index < 0 || index > size) { throw new IndexOutOfBoundsException("索引越界: Index: " + index + ", Size: " + size); } } private void rangeCheckForGet(int index) { // 获取或删除时，index必须在 [0, size) 范围内 if (index < 0 || index >= size) { throw new IndexOutOfBoundsException("索引越界: Index: " + index + ", Size: " + size); } }

这里有两个关键的rangeCheck方法。为什么区分ForAdd和ForGet？因为添加操作允许的索引范围是[0, size]，你可以在最后一个元素后面（索引为size处）添加新元素；而获取、修改、删除操作允许的索引范围是[0, size-1]，你必须针对一个已存在的元素进行操作。这个细微的差别是很多初学者容易混淆的地方。

3.2 动态扩容：顺序表的“心脏”机制

这是动态顺序表最核心的机制。当size即将达到data.length（即数组已满）时，我们需要一个更大的新数组，并把旧数组的所有元素复制过去。

/** * 确保顺序表有足够的容量来容纳至少minCapacity个元素。 * 如果当前容量不足，则进行扩容。 * @param minCapacity 所需的最小容量 */ private void ensureCapacity(int minCapacity) { int oldCapacity = data.length; if (minCapacity > oldCapacity) { // 计算新容量。策略：至少扩容为旧容量的1.5倍，但如果minCapacity更大，则采用minCapacity。 int newCapacity = oldCapacity + (oldCapacity >> 1); // oldCapacity * 1.5 (位运算右移1位等于除以2) if (newCapacity < minCapacity) { newCapacity = minCapacity; } // 一些VM可能有数组大小限制，这里简单处理，实际生产代码需考虑Integer.MAX_VALUE - 8等限制 if (newCapacity > Integer.MAX_VALUE - 8) { newCapacity = hugeCapacity(minCapacity); } // 创建新数组并复制数据 data = Arrays.copyOf(data, newCapacity); System.out.println("触发扩容: " + oldCapacity + " -> " + 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. 扩容时机：不是在数组完全满了(size == capacity)才扩容，而是在每次添加操作前检查。参数minCapacity通常是size + 1（添加一个元素）或size + numNew（添加多个元素）。
2. 扩容策略：newCapacity = oldCapacity + (oldCapacity >> 1)。这是一个经典策略，相当于扩容为原来的1.5倍。位运算>> 1比直接乘以1.5或除以2的浮点运算效率更高。为什么是1.5？这是一个经验值，在减少扩容次数和避免内存浪费之间取得了较好的平衡。ArrayList在JDK中的增长因子大约是1.5（具体实现是oldCapacity + (oldCapacity >> 1)）。
3. Arrays.copyOf：这是System.arraycopy的一个更友好的封装，用于创建新数组并复制数据。其内部仍然是本地方法，效率很高。
4. 大容量处理：当所需容量接近JVM数组的最大限制时（Integer.MAX_VALUE - 8，这个8是部分JVM为数组头信息保留的），需要进行特殊处理，防止溢出。

3.3 添加元素：尾插与任意位置插入

添加元素有两种主要场景：在末尾追加，和在指定索引处插入。

/** * 在顺序表末尾添加一个元素 * @param e 要添加的元素 * @return 总是返回true（模仿Collection接口） */ public boolean add(E e) { // 1. 确保容量足够再容纳一个元素 ensureCapacity(size + 1); // 2. 在size索引处放入新元素 data[size] = e; // 3. 逻辑大小加1 size++; return true; } /** * 在顺序表的指定索引处插入一个元素。该索引及其后的所有元素向右移动一位。 * @param index 要插入位置的索引 * @param element 要插入的元素 */ public void add(int index, E element) { // 检查索引合法性（允许index == size） rangeCheckForAdd(index); // 确保容量足够 ensureCapacity(size + 1); // 核心：将index及其后面的所有元素向后移动一位 // 从最后一个元素(size-1)开始，倒序移动到index位置 for (int i = size - 1; i >= index; i--) { data[i + 1] = data[i]; } // 在空出的index位置放入新元素 data[index] = element; // 逻辑大小加1 size++; } /** * 批量添加另一个集合中的所有元素到末尾 * @param c 包含要添加元素的集合 * @return 如果顺序表因调用而改变则返回true */ public boolean addAll(Collection<? extends E> c) { Object[] a = c.toArray(); int numNew = a.length; ensureCapacity(size + numNew); // 一次性确保容量，避免多次扩容 // 使用System.arraycopy进行批量复制，效率高于循环 System.arraycopy(a, 0, data, size, numNew); size += numNew; return numNew != 0; }

时间复杂度分析：

• add(E e)（尾插）：平均时间复杂度为O(1)。虽然偶尔会触发O(n)的扩容复制操作，但均摊到每次添加操作上，成本是常数级别的。这就是均摊时间复杂度的概念。
• add(int index, E element)（指定位置插入）：时间复杂度为O(n)。因为最坏情况下（在索引0处插入），需要移动后面所有的n个元素。这是顺序表在中间插入操作上的主要缺点。

实操心得：System.arraycopyvs 手动循环在add(int index, E element)中，我们使用了for循环来移动元素。实际上，System.arraycopy是一个本地方法，在复制大量连续内存时，效率远高于Java层面的for循环。ArrayList的内部实现就大量使用了System.arraycopy。我们可以优化这个方法：

public void add(int index, E element) { rangeCheckForAdd(index); ensureCapacity(size + 1); // 使用System.arraycopy移动元素 if (index != size) { // 如果不是在末尾插入，才需要移动 System.arraycopy(data, index, data, index + 1, size - index); } data[index] = element; size++; }

这个优化在数据量大时效果显著。

3.4 删除元素：按索引删除与按值删除

删除操作同样涉及元素的移动。

/** * 删除指定索引位置的元素 * @param index 要删除元素的索引 * @return 被删除的元素 */ public E remove(int index) { rangeCheckForGet(index); // 删除索引必须在[0, size-1]范围内 E oldValue = data[index]; // 计算需要移动的元素数量 int numMoved = size - index - 1; if (numMoved > 0) { // 将index+1及其后面的元素向前移动一位 System.arraycopy(data, index + 1, data, index, numMoved); } // 将最后一个位置置为null，帮助垃圾回收 data[--size] = null; return oldValue; } /** * 删除顺序表中第一次出现的指定元素（如果存在） * @param o 要删除的元素 * @return 如果顺序表包含该元素则返回true */ public boolean remove(Object o) { if (o == null) { for (int i = 0; i < size; i++) { if (data[i] == null) { fastRemove(i); return true; } } } else { for (int i = 0; i < size; i++) { if (o.equals(data[i])) { fastRemove(i); return true; } } } return false; } /** * 快速删除（不返回被删除的元素，不进行边界检查，供内部调用） * @param index 要删除的索引 */ private void fastRemove(int index) { int numMoved = size - index - 1; if (numMoved > 0) { System.arraycopy(data, index + 1, data, index, numMoved); } data[--size] = null; } /** * 清空顺序表，将所有元素置为null并重置size */ public void clear() { // 显式地将所有引用置为null，帮助GC回收内存 for (int i = 0; i < size; i++) { data[i] = null; } size = 0; }

关键点解析：

1. 置null操作：在remove和clear方法中，我们将不再使用的数组槽位显式地设为null。这至关重要。因为我们的数组存储的是对象的引用，如果不置null，即使size减小了，数组仍然持有对那些对象的强引用，垃圾回收器(GC)就无法回收它们，导致内存泄漏。ArrayList的源码中也严格进行了这一步。
2. 按值删除的遍历：remove(Object o)方法需要遍历数组来查找元素。它区分了null和非null值，因为null不能用equals方法比较。这是一个常见的模式。
3. fastRemove私有方法：这是一个内部优化，将删除的通用逻辑（移动元素、置null、size--）抽取出来，供remove(Object o)调用，避免代码重复。

3.5 查找与修改：随机访问的优势

这是顺序表相比链表最大的优势所在。

/** * 获取指定索引位置的元素 * @param index 元素的索引 * @return 该索引位置的元素 */ public E get(int index) { rangeCheckForGet(index); return data[index]; // O(1)时间复杂度 } /** * 修改指定索引位置的元素 * @param index 要修改元素的索引 * @param element 新的元素 * @return 该位置原来的元素 */ public E set(int index, E element) { rangeCheckForGet(index); E oldValue = data[index]; data[index] = element; return oldValue; } /** * 判断顺序表是否包含指定元素 * @param o 要查找的元素 * @return 如果包含则返回true */ public boolean contains(Object o) { return indexOf(o) >= 0; } /** * 返回指定元素在顺序表中第一次出现的索引 * @param o 要查找的元素 * @return 索引，如果未找到则返回-1 */ public int indexOf(Object o) { if (o == null) { for (int i = 0; i < size; i++) { if (data[i] == null) { return i; } } } else { for (int i = 0; i < size; i++) { if (o.equals(data[i])) { return i; } } } return -1; } /** * 返回指定元素在顺序表中最后一次出现的索引 * @param o 要查找的元素 * @return 索引，如果未找到则返回-1 */ public int lastIndexOf(Object o) { // 从后向前遍历 if (o == null) { for (int i = size - 1; i >= 0; i--) { if (data[i] == null) { return i; } } } else { for (int i = size - 1; i >= 0; i--) { if (o.equals(data[i])) { return i; } } } return -1; }

性能总结：

• get(int index)/set(int index, E element)：时间复杂度为O(1)。这是随机访问的直接体现，通过索引计算内存偏移量，一步到位。
• indexOf(Object o)/contains(Object o)：时间复杂度为O(n)。因为需要遍历数组（最坏情况遍历全部元素）来进行线性查找。如果需要有更快的查找速度，需要考虑其他数据结构，如HashSet（O(1)平均）或有序数组的二分查找（O(log n)）。

4. 迭代器实现：让顺序表可被foreach遍历

为了让我们的MyArrayList能够使用Java的增强for循环（for (E e : list)），我们需要实现Iterable<E>接口，并提供一个Iterator<E>。

import java.util.Iterator; import java.util.NoSuchElementException; public class MyArrayList<E> implements Iterable<E> { // ... 之前的成员变量和方法 ... /** * 返回一个迭代器，用于遍历顺序表 */ @Override public Iterator<E> iterator() { return new MyArrayListIterator(); } /** * 内部迭代器类 */ private class MyArrayListIterator implements Iterator<E> { private int currentIndex = 0; // 当前迭代到的位置 private int lastReturnedIndex = -1; // 最近一次通过next()返回的元素索引，用于支持remove() @Override public boolean hasNext() { return currentIndex < size; // 是否还有下一个元素 } @Override public E next() { if (!hasNext()) { throw new NoSuchElementException(); } lastReturnedIndex = currentIndex; return data[currentIndex++]; // 返回当前元素，然后索引加1 } /** * 删除迭代器最后一次返回的元素。 * 必须在调用next()之后，且每个元素只能删除一次。 */ @Override public void remove() { if (lastReturnedIndex < 0) { throw new IllegalStateException("在调用remove()之前必须先调用next()"); } // 调用外部类的remove方法进行删除 MyArrayList.this.remove(lastReturnedIndex); // 因为删除后，后面的元素前移了一位，所以当前迭代位置要减1 currentIndex = lastReturnedIndex; // 重置lastReturnedIndex，防止连续调用remove() lastReturnedIndex = -1; } } }

迭代器设计要点：

1. 状态保持：迭代器需要知道当前遍历到了哪个位置（currentIndex）。
2. 快速失败(Fail-Fast)：我们这里实现的是一个简单的迭代器。标准的ArrayList迭代器具有“快速失败”机制，即在迭代过程中，如果检测到列表被非迭代器自身的其他方法修改（结构性修改），会立刻抛出ConcurrentModificationException。这是通过一个modCount（修改计数器）实现的。我们的简易版省略了此机制，但在并发环境下使用时需要特别注意。
3. 迭代器中的删除：Iterator.remove()是一个可选但很有用的操作。它的实现需要小心处理索引。删除元素后，底层数组结构发生了变化，迭代器的内部索引currentIndex需要相应调整（回退一位），否则会跳过下一个元素。

5. 性能分析与实战避坑指南

5.1 时间复杂度总结

让我们系统地回顾一下MyArrayList各项操作的时间复杂度，这直接决定了它的适用场景。

核心结论：顺序表适合“读多写少”，且写入主要在尾部进行的场景。

5.2 常见问题与避坑技巧

在实际使用自研或ArrayList时，下面这些“坑”你很可能遇到。

1. 初始化容量设置不当

// 坑：已知要存储1000个元素，却使用默认构造函数 MyArrayList<String> list = new MyArrayList<>(); // 初始容量10 for (int i = 0; i < 1000; i++) { list.add("item-" + i); // 会触发多次扩容：10->15->22->33->49->73->109->163->244->366->549->823->1234 }

避坑技巧：如果能预估大致的元素数量，务必使用带初始容量的构造函数。这可以避免多次扩容和数据复制带来的性能损耗。

MyArrayList<String> list = new MyArrayList<>(1000); // 一次分配到位，无扩容开销

2. 在循环中调用remove(Object o)或remove(int index)

MyArrayList<Integer> list = new MyArrayList<>(Arrays.asList(1, 2, 2, 3, 4, 2)); // 目标：删除所有值为2的元素 for (int i = 0; i < list.size(); i++) { if (list.get(i) == 2) { list.remove(i); // 这是一个经典的BUG！ } } // 执行后list为 [1, 2, 3, 4]？ 不对！实际是 [1, 2, 3, 4, 2]

问题分析：当i=1时，删除第一个2，后面的元素[2,3,4,2]前移变成[2,3,4,2]，索引1的位置变成了新的元素3。循环继续，i++变成2，这就跳过了原来在索引2位置的那个2。

避坑技巧：从后向前遍历删除。

for (int i = list.size() - 1; i >= 0; i--) { if (list.get(i) == 2) { list.remove(i); // 从后往前删，索引变化不会影响前面待检查的元素 } }

或者使用Iterator.remove()，它会在删除后正确处理迭代状态。

3. 并发修改异常（简易迭代器版）我们的MyArrayListIterator没有实现快速失败机制。如果在迭代过程中，通过列表自身的add或remove方法（而非迭代器的remove）修改了列表，迭代器的行为将是未定义的，很可能导致元素错乱或越界异常。

避坑技巧：在单线程中，确保在迭代时只使用迭代器自身的remove()方法进行删除操作。在多线程环境下，ArrayList本身就不是线程安全的，必须使用外部同步（如synchronized）或改用CopyOnWriteArrayList等并发容器。

4. 存储大量数据后的内存浪费顺序表扩容后，即使你删除了很多元素，底层数组的容量(capacity)也不会自动缩小。这可能导致内存浪费。

list.addAll(/* 添加100万个元素 */); // 底层数组扩容到约150万容量 list.clear(); // 只是size=0，data数组长度仍是150万

避坑技巧：如果确定后续不再需要那么大的容量，可以手动“缩容”。

list.trimToSize(); // 一个可以补充实现的方法，将容量调整为当前size

ArrayList提供了trimToSize()方法正是做这个的。其实现原理是：如果size < data.length，就创建一个大小为size的新数组并拷贝数据。

5.3 与Java标准库ArrayList的对比与扩展思考

我们实现的MyArrayList是一个教学版的简化模型，而java.util.ArrayList则是一个工业级、高度优化的类。了解它们的差异有助于我们更好地使用标准库。

扩展思考：何时需要自己实现顺序表？绝大多数情况下，直接使用ArrayList是最佳选择。但在一些极端性能敏感或特殊需求的场景下，自己实现可能有价值：

1. 存储基本类型：ArrayList<Integer>存在自动装箱/拆箱开销和内存浪费。你可以实现一个专用的IntArrayList，底层用int[]，性能远超通用容器。
2. 极简内存布局：你需要一个完全可控、没有多余字段（如modCount）、内存占用最小的动态数组。
3. 特定的扩容/缩容策略：你的应用有非常独特的内存使用模式，需要定制化的扩容算法。
4. 学习与研究目的：正如我们本文所做的，这是理解数据结构、Java集合框架和性能优化最有效的途径之一。

亲手实现一遍顺序表，再回头去看ArrayList的源码，你会发现以前觉得晦涩的代码变得异常清晰。你知道了elementData为什么是transient的，知道了grow方法里的位运算妙用，也知道了迭代器里那个expectedModCount是干什么的。这种从“使用者”到“创造者”的视角转换，是提升编程内功的关键一步。