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 类结构设计与核心成员变量首先我们来设计这个顺序表类的骨架。一个动态顺序表需要哪些核心部件底层存储数组 (E[] data)这是存储元素的真正容器。我们使用泛型E让我们的顺序表可以存储任意类型的对象增强通用性。当前元素个数 (int size)这是顺序表逻辑上的大小即用户已经添加了多少个元素。它永远小于或等于底层数组的物理容量(capacity)。默认初始容量 (DEFAULT_CAPACITY)当用户没有指定初始大小时我们提供一个合理的默认值。参考ArrayList通常设为10。扩容因子这是一个关键参数决定了当数组满时新数组应该是旧数组的多少倍。常见的值是1.5或2.0。过小会导致频繁扩容性能损耗大过大则可能浪费内存。我们这里采用和ArrayList类似的策略但会显式地展示计算过程。基于以上分析我们的类定义如下/** * 一个简易的动态顺序表实现 * param E 顺序表中元素的类型 */ public class MyArrayListE { // 底层存储数组 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; }关键点解析扩容时机不是在数组完全满了(size capacity)才扩容而是在每次添加操作前检查。参数minCapacity通常是size 1添加一个元素或size numNew添加多个元素。扩容策略newCapacity oldCapacity (oldCapacity 1)。这是一个经典策略相当于扩容为原来的1.5倍。位运算 1比直接乘以1.5或除以2的浮点运算效率更高。为什么是1.5这是一个经验值在减少扩容次数和避免内存浪费之间取得了较好的平衡。ArrayList在JDK中的增长因子大约是1.5具体实现是oldCapacity (oldCapacity 1)。Arrays.copyOf这是System.arraycopy的一个更友好的封装用于创建新数组并复制数据。其内部仍然是本地方法效率很高。大容量处理当所需容量接近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) { // 将index1及其后面的元素向前移动一位 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; }关键点解析置null操作在remove和clear方法中我们将不再使用的数组槽位显式地设为null。这至关重要。因为我们的数组存储的是对象的引用如果不置null即使size减小了数组仍然持有对那些对象的强引用垃圾回收器(GC)就无法回收它们导致内存泄漏。ArrayList的源码中也严格进行了这一步。按值删除的遍历remove(Object o)方法需要遍历数组来查找元素。它区分了null和非null值因为null不能用equals方法比较。这是一个常见的模式。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)。因为需要遍历数组最坏情况遍历全部元素来进行线性查找。如果需要有更快的查找速度需要考虑其他数据结构如HashSetO(1)平均或有序数组的二分查找O(log n)。4. 迭代器实现让顺序表可被foreach遍历为了让我们的MyArrayList能够使用Java的增强for循环for (E e : list)我们需要实现IterableE接口并提供一个IteratorE。import java.util.Iterator; import java.util.NoSuchElementException; public class MyArrayListE implements IterableE { // ... 之前的成员变量和方法 ... /** * 返回一个迭代器用于遍历顺序表 */ Override public IteratorE iterator() { return new MyArrayListIterator(); } /** * 内部迭代器类 */ private class MyArrayListIterator implements IteratorE { 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; } } }迭代器设计要点状态保持迭代器需要知道当前遍历到了哪个位置currentIndex。快速失败(Fail-Fast)我们这里实现的是一个简单的迭代器。标准的ArrayList迭代器具有“快速失败”机制即在迭代过程中如果检测到列表被非迭代器自身的其他方法修改结构性修改会立刻抛出ConcurrentModificationException。这是通过一个modCount修改计数器实现的。我们的简易版省略了此机制但在并发环境下使用时需要特别注意。迭代器中的删除Iterator.remove()是一个可选但很有用的操作。它的实现需要小心处理索引。删除元素后底层数组结构发生了变化迭代器的内部索引currentIndex需要相应调整回退一位否则会跳过下一个元素。5. 性能分析与实战避坑指南5.1 时间复杂度总结让我们系统地回顾一下MyArrayList各项操作的时间复杂度这直接决定了它的适用场景。操作时间复杂度说明访问get(index)/set(index, e)O(1)随机访问顺序表的王牌优势。尾部插入add(e)O(1) 均摊大部分情况直接赋值偶尔触发O(n)扩容。任意位置插入add(index, e)O(n)需要移动后续所有元素最坏在头部插入需移动n个元素。按索引删除remove(index)O(n)需要移动后续所有元素最坏删除头部元素需移动n-1个元素。按值删除remove(Object o)O(n)需要先O(n)查找再O(n)移动元素。查找indexOf(o)/contains(o)O(n)需要遍历数组进行线性查找。核心结论顺序表适合“读多写少”且写入主要在尾部进行的场景。5.2 常见问题与避坑技巧在实际使用自研或ArrayList时下面这些“坑”你很可能遇到。1. 初始化容量设置不当// 坑已知要存储1000个元素却使用默认构造函数 MyArrayListString 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 }避坑技巧如果能预估大致的元素数量务必使用带初始容量的构造函数。这可以避免多次扩容和数据复制带来的性能损耗。MyArrayListString list new MyArrayList(1000); // 一次分配到位无扩容开销2. 在循环中调用remove(Object o)或remove(int index)MyArrayListInteger 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]问题分析当i1时删除第一个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(); // 只是size0data数组长度仍是150万避坑技巧如果确定后续不再需要那么大的容量可以手动“缩容”。list.trimToSize(); // 一个可以补充实现的方法将容量调整为当前sizeArrayList提供了trimToSize()方法正是做这个的。其实现原理是如果size data.length就创建一个大小为size的新数组并拷贝数据。5.3 与Java标准库ArrayList的对比与扩展思考我们实现的MyArrayList是一个教学版的简化模型而java.util.ArrayList则是一个工业级、高度优化的类。了解它们的差异有助于我们更好地使用标准库。特性我们的MyArrayListjava.util.ArrayList扩容策略明确为1.5倍 (oldCapacity (oldCapacity 1))。JDK版本间有细微调整但核心是1.5倍左右。在添加大量元素时会尝试计算更精确的容量。快速失败未实现。通过modCount实现。迭代器创建时会记录当前的modCount每次操作前检查如果不一致则抛出ConcurrentModificationException。序列化未实现。实现了自定义的writeObject和readObject方法只序列化实际元素size范围内的而不是整个底层数组节省空间。容量调整未提供trimToSize()。提供trimToSize()和ensureCapacity(int minCapacity)公有方法。子列表视图未实现。提供subList(int fromIndex, int toIndex)返回一个原列表的“视图”对子列表的修改会反映到原列表。函数式编程未实现。实现了forEach,removeIf,replaceAll,sort等方法继承自List接口。扩展思考何时需要自己实现顺序表绝大多数情况下直接使用ArrayList是最佳选择。但在一些极端性能敏感或特殊需求的场景下自己实现可能有价值存储基本类型ArrayListInteger存在自动装箱/拆箱开销和内存浪费。你可以实现一个专用的IntArrayList底层用int[]性能远超通用容器。极简内存布局你需要一个完全可控、没有多余字段如modCount、内存占用最小的动态数组。特定的扩容/缩容策略你的应用有非常独特的内存使用模式需要定制化的扩容算法。学习与研究目的正如我们本文所做的这是理解数据结构、Java集合框架和性能优化最有效的途径之一。亲手实现一遍顺序表再回头去看ArrayList的源码你会发现以前觉得晦涩的代码变得异常清晰。你知道了elementData为什么是transient的知道了grow方法里的位运算妙用也知道了迭代器里那个expectedModCount是干什么的。这种从“使用者”到“创造者”的视角转换是提升编程内功的关键一步。
