顺序表这个名词大家多半是在数据结构教材的线性表那一章第一次见到。教材上往往用很短篇幅讲完定义、存储结构和几个基本操作就让你自己去写代码了。结果真上手就会发现不少细节问题按索引插入的时候到底从后往前遍历还是从前往后初始化容量给多少什么时候该扩容这些内容教材经常一笔带过。所以我想写一份关于顺序表的附录式笔记把教科书跳过的部分补上把我在学习和实战中踩过的坑一起记录下来。这份内容对正在学数据结构的学生、准备笔试面试的开发者都适用读完你不仅能理解顺序表的原理还能直接把代码写得规范、稳健。1. 先搞清楚顺序表到底是什么为什么值得单独写一份附录1.1 顺序表在数据结构体系里的准确位置顺序表Sequence List本质上就是线性表的一种存储实现方式底层依赖一段地址连续的存储空间通常用数组承载。它和链表一起构成线性表的两种最基础、也是面试笔试里最高频的实现方式。教科书里常说的“随机存取”“逻辑上相邻物理上也相邻”这些概念落到代码里就对应两个关键指标逻辑长度 size 和物理容量 capacity。很多人写顺序表时只盯着 size完全忽略 capacity 的存在这就导致一遇到“放不下更多元素”就不知道怎么处理了。其实顺序表最核心的设计就是维护好这两个数字并控制好它们之间的关系。当 size 追上 capacity就需要申请更大的数组把旧数据搬过去这个过程就是扩容。1.2 这份附录想回答的五个具体问题我在带项目、改作业、帮人准备面试的时候发现大家遇到的顺序表问题高度集中基本可以归纳成五类。第一插入操作的循环方向总是混淆总是在“从前往后移”和“从后往前移”之间纠结。第二初始化容量和扩容系数怎么取很多人直接填一个 10却不知道为什么是 10。第三删除操作要不要把尾部元素置空很多人觉得反正 size 减一就够了。第四泛型数组到底怎么创建为什么直接 new T[size] 会报错。第五顺序表和链表在什么场景下选哪个面试里被问到性能对比时经常说不到点子上。这些问题单独看都不大但组合在一起就是一份完整顺序表代码能不能写对、能不能跑稳、能不能在项目里真正可用的关键。这篇附录就是围绕这五个问题展开的。2. Java 实现顺序表的关键设计取舍2.1 底层字段设计size、capacity 和默认初值的选型顺序表的字段设计看起来简单实际上决定了后续所有逻辑的复杂度。我习惯用下面这一组字段public class SequenceListT implements IterableT { private Object[] elementData; private int size; private static final int DEFAULT_CAPACITY 10; }初始化时可以直接给容量 10也可以支持调用方传入自定义容量。有一点需要注意如果调用方传入的 initialCapacity 小于 0必须在构造函数里抛出 IllegalArgumentException。这个问题在面试中经常作为“考察代码严谨性”的小点出现很多人会漏掉。在默认容量为什么经常是 10 这个问题上Java 官方 ArrayList 源码里 DEFAULT_CAPACITY 也是 10这是参考一些早期学习和测试场景的经验值。10 个元素足够覆盖大多数基础演示需求频繁扩容带来的性能损耗也不大。如果是商用系统通常不会用默认值而是根据预估数据量初始化一个更贴近实际的容量避免中间多次扩容。还要注意区分 size 和 capacity 的含义。size 是有意义元素的数量capacity 是数组长度本身。这两个概念一旦混淆插入、删除、遍历的时候就会出现各种越界或者逻辑错误。我见过不少代码用 capacity 去控制遍历结果数组后半部分是 null 或者默认值白白输出了很多无效数据。2.2 插入操作里的索引位移方向问题插入是顺序表最核心的操作也是最容易错的操作。先看两个关键判断条件。public void insert(int index, int value) { if (index 0 || index size) { throw new IndexOutOfBoundsException(index index , size size); } ensureCapacity(size 1); for (int i size; i index; i--) { elementData[i] elementData[i - 1]; } elementData[index] value; size; }这里的边界条件很多人写错index 可以等于 size因为允许在表尾追加元素但 index 绝对不能大于 size因为那意味着中间出现了空位。判断条件写错直接导致的后果就是数组越界或者插入后出现 null 空洞。循环方向为什么必须从后往前你想想移动的过程目标是把 index 位置空出来所以 index 以及它后面的元素都要整体后移一位。如果从前往后遍历先把 index 覆盖了后面的元素还没移动数据就丢了。从后往前遍历先把最后一个元素挪到 size 位置再逐步把 index 位置让出来整个过程就安全了。这里还有一个经验技巧插入过程建议用System.arraycopy代替手写循环。arraycopy 是 JVM 层面的原生方法底层会做内存块复制性能比手动 for 循环好很多代码也更简洁System.arraycopy(elementData, index, elementData, index 1, size - index); elementData[index] value; size;2.3 删除操作和数据置空的隐性作用删除操作同样有一个方向问题但它的方向是从前往后移也就是把后面的元素往前覆盖。public T remove(int index) { if (index 0 || index size) { throw new IndexOutOfBoundsException(index index , size size); } T oldValue (T) elementData[index]; System.arraycopy(elementData, index 1, elementData, index, size - index - 1); elementData[--size] null; return oldValue; }这里最关键的一行是elementData[--size] null。很多人不理解为什么要置空size 已经减了后续操作反正访问不到那个位置了。但问题在于底层数组仍然持有那个对象的引用如果你不手动置空对象就始终被数组引用着。当顺序表存活时间很长里面的元素又被频繁增删那些被删除的对象就一直无法被垃圾回收最终形成内存泄漏。这个问题在 Android 应用和长驻服务里特别容易出现因为内存紧张GC 压力大会直接卡顿甚至闪退。我在项目里已经形成了肌肉记忆只要从顺序表里移除了元素尾部最后一个位置必须置空。这行代码和 size 减一同样重要缺一不可。2.4 泛型数组创建的兼容性处理Java 中直接写T[] array new T[capacity]是编译不过的因为泛型在运行时会被类型擦除JVM 根本不知道 T 到底是什么类型。业界最常见的做法是创建 Object[] 数组再在 get 方法里做强转。SuppressWarnings(unchecked) public T get(int index) { return (T) elementData[index]; }SuppressWarnings(unchecked)的作用是压制编译器警告。很多人不喜欢这个注解觉得它掩盖了潜在错误但在这里它是安全的因为我们所有的写入操作都发生在内部add 方法接收的也是 T 类型类型安全是由代码逻辑保证的。如果完全不做强转调用方只会收到 Object使用起来非常难受。还有一个细节如果你重写了 clone 方法需要对新数组做一次深拷贝而不是简单地把数组引用赋值。浅拷贝会导致两个顺序表对象共享同一片底层数组改动一个另一个也变这在业务代码里是灾难。3. 扩容机制理解运行时的幕后推手3.1 扩容触发条件和扩容倍数的选择逻辑扩容的触发条件很简单插入元素时 size 1 突破 capacity。但扩容时新容量取多少这里就有门道了。private void grow(int minCapacity) { int oldCapacity elementData.length; int newCapacity oldCapacity (oldCapacity 1); if (newCapacity minCapacity) { newCapacity minCapacity; } elementData Arrays.copyOf(elementData, newCapacity); }为什么oldCapacity (oldCapacity 1)得到的是 1.5 倍右移一位相当于除以 2所以新容量是旧容量的 1.5 倍。选择 1.5 而不是 2主要有两个考虑。第一每次扩容越大后续扩容次数越少搬运成本越低但浪费的内存可能更多。第二扩容倍数过小插入元素时频繁扩容整体性能反而恶化。从数学期望上看1.5 倍是一个相对温和的增长速率既能控制扩容次数又能控制内存浪费在可接受范围内。Java ArrayList 的默认实现也是这个策略。如果调用方明确知道要放很多数据可以直接在构造函数里指定一个接近实际规模的初始容量这一步就能避开多次扩容带来的数据搬运损耗。3.2 扩容操作的均摊时间复杂度和数学推导很多人背过“顺序表插入操作的均摊时间复杂度是 O(1)”但不知道为什么。这里可以做一个简单推导。假设表起始容量是 1每次扩容翻倍那么扩容发生时需要搬运的元素数量分别是 1、2、4、8……要插入 n 个元素所有扩容搬运量加起来是 1 2 4 ... n/2约等于 n。平摊到 n 次插入上每次插入才有 O(1) 的量级。1.5 倍扩容的场景也类似调用 add 方法均摊下来依旧是常数级。但这里的前提是选择“预留容量到位、连续多次插入”如果你每插入一个就触发一次扩容那单次插入就是 O(n) 了整体就是 O(n²)。这也是为什么使用顺序表时提前估算容量的价值所在。3.3 缩容策略什么时候才应该瘦身扩容很容易理解缩容就经常被忽略了。当顺序表里大量元素被删除后容量远大于 size数组仍然占据着大量内存。如果你实现的是 ArrayList可以直接调用 trimToSize 方法把容量裁剪到和 size 一致。如果是自己实现的顺序表可以提供一个类似的方法public void trimToSize() { int oldCapacity elementData.length; if (size oldCapacity) { elementData Arrays.copyOf(elementData, size); } }自动缩容我反而不推荐。因为在系统运行过程中容量一直在动态使用过早缩容可能导致后续又需要扩容一来一回反而增加性能损耗。更合理的做法是当 size 小于容量的四分之一时再考虑缩容或者按业务节奏在系统空闲时统一执行。手动 trim 和控制缩容时机是实际项目里更稳健的选择。4. 隐藏 Bug 与边界条件排查4.1 空表删除、空指针和 equals 判断的细节顺序表的边界条件我看很多人写的时候都没做完整校验。常见问题有删除空表元素、在负数索引处插入、使用 null 作为元素值参与扩容判断等。空表删除很好理解直接在 remove 里判断 size 0 或 index size 就会触发异常。但 null 值问题更隐蔽因为顺序表通常允许元素为 null那么进行查询判断时如果你用elementData[index].equals(value)来查找元素而当前元素恰好是 null就会抛 NullPointerException。安全的写法是优先判断查找值本身是否为 nullpublic int indexOf(Object value) { if (value null) { for (int i 0; i size; i) { if (elementData[i] null) return i; } } else { for (int i 0; i size; i) { if (value.equals(elementData[i])) return i; } } return -1; }把查找目标为 null 和非 null 两种情况拆开来处理就不会出现 equals 调用在被搜索元素上、而该元素恰好为 null 的崩溃问题。这个细节在实现 contains、remove(Object) 这一类方法时同样适用。4.2 扩容时迭代器失效的经典问题如果你实现过 Iterable 接口或者使用过 Java 自带的 ArrayList 迭代器应该会遇到 ConcurrentModificationException。这个异常的本质是迭代器在创建时会记录一个 modCount修改次数每次迭代检查当前 modCount 是否和记录值一致。一旦在外面执行了 add、remove、扩容等结构性修改modCount 变了迭代器就会报错。private class Itr implements IteratorT { private int cursor; private int expectedModCount modCount; Override public T next() { checkForComodification(); // ... } private void checkForComodification() { if (modCount ! expectedModCount) { throw new ConcurrentModificationException(); } } }正确的使用方式是在迭代过程中通过迭代器自身的 remove 方法删除元素而不是调用外层顺序表的 remove。如果实在需要在遍历时做批量修改一种稳妥做法是先收集需要删除的索引遍历结束后再统一删除另一种做法是直接使用 Java 8 的 removeIf 方法它会内部正确处理修改计数。4.3 find 和 get 操作的边界组合测试顺序表最容易被测出问题的其实是 get、set 和索引访问这三者之间的边界条件一致性。get 允许的范围是 [0, size-1]set 也是 [0, size-1]而 insert 允许的范围是 [0, size]。把这三类方法分别写成独立的方法再用一组组合测试用例去验证是很有效的排查方式。常见的测试用例包括空表上执行 remove 和 get在 size 位置插入后再 get删除第一个元素后重新遍历连续 insert 超过初始容量触发多次扩容后数据是否完整。我建议把这些测试用例保存下来以后每次改动底层实现都跑一遍能拦截大量回归问题。5. 复杂度分析与性能误区5.1 顺序表各项操作的时间复杂度对照为了讲清楚我做了一张常用操作的时间复杂度对照表操作时间复杂度说明get / set 按索引访问O(1)数组随机访问直接定位add(E) 尾插O(1) 均摊触发扩容时单次 O(n)均摊 O(1)add(index, E) 任意位置插入O(n)需要后移 index 之后的元素remove(index) 按索引删除O(n)需要前移 index 之后的元素indexOf 按值查找O(n)需要线性扫描containsO(n)扫描到底最好情况 O(1)看到这张表很多人会立刻认为顺序表只适合“尾部增删 按下标随机访问”的场景。这个理解基本正确但在真实项目中还有一层维度要考虑数组元素在内存中是连续存放的CPU 缓存预取对连续内存的遍历非常友好。即使两个算法理论复杂度相同顺序表的常数项往往比链表小很多。5.2 顺序表 vs 链表复杂度之外的真实性能场景面试里经常被问到“什么场景用顺序表什么场景用链表”。如果你只回答“频繁插入删除用链表”其实不够全面因为插入删除还要看在什么位置。在头部插入顺序表要移动所有元素链表只需要改一个指针但在尾部插入顺序表只需要直接写入链表却要先遍历到最后一个节点。还有遍历场景。顺序表因为内存连续循环访问时局部性极好Cache 命中率高遍历速度远快于链表。链表节点分散在堆中每次访问都得做一次指针跳转缓存完全不友好。所以实际项目中像消息队列、日志缓存这类频繁遍历的场景使用顺序表往往更合适。5.3 我在实际项目里的几个微优化经验第一能用 index 访问就不要用 value 循环查找。业务里常常出现的一个模式是“先 indexOf 找到位置再 remove 掉”。这一步复杂度是 O(n) 查找加 O(n) 移动。如果业务允许换成尾插尾删或者按下标维护性能差距会非常明显。第二批量添加时使用 addAll 而不是多次 add。addAll 通常只需一次扩容检查而多次 add 可能触发多次扩容每次扩容都是整数组复制。一次扩容和三次扩容在大数据量下的差距可能就是几毫秒和几十毫秒的区别。第三当元素是固定长度的小对象时可以考虑用原始类型数组如int[]替代整型包装类数组Integer[]避免自动装箱拆箱导致的额外对象分配。这一条在计算密集、内存敏感的场景尤为重要。6. 从考场到真实项目顺序表相关的实战经验记录6.1 一次并发环境下扩容导致的异常排查有一回我在项目里用一个静态的顺序表对象作为数据缓存。刚开始数据量小一切正常。上线后数据量上来了偶尔出现数组越界的问题而且方向特别诡异明明 size 已经增长到 1000但底层数组长度还是 16。排查后确认是并发访问导致的问题。线程 A 正在执行扩容流程一行代码都没执行完线程 B 已经往旧数组里写数据了然后 A 又把旧数组整个替换掉B 写进去的数据就丢了甚至数组越界。顺序表本身不是并发容器多线程环境下必须在外部加锁或者直接使用线程安全类。这个事给我的教训是写资料结构代码时不仅要考虑单线程的正确性还要明确标注“非线程安全”提醒后续使用者。6.2 大文件读取场景里 trimToSize 的意外收益另一个案例是日志解析。系统启动时一次性读取几十万行日志顺序表是会频繁扩容最后 size 接近 60 万但底层容量可能已经扩张到 100 万以上。如果不做压缩这 40 万的差额就会持续占用内存。我当时的做法是在数据装载完成后调用一次 trimToSize把底层数组裁剪到精确大小。在监控进程里内存占用瞬时下降了 30 兆左右。虽然这点内存对服务器来说不算大但在内存敏感的环境里这属于零成本优化收益立竿见影。关键是要记住大集合装载完成后做一次容量压缩能有效降低长期驻留内存。6.3 笔试面试中的最佳实践手写顺序表需要注意的三件事如果面试官让你现场手写一个顺序表我建议你把握住三个关键点这种东西平时多练一练面试速度会快很多考试中也不会因为紧张而漏掉。第一框架完整从类的泛型声明、字段初始化到 add、remove、get、size、isEmpty 五个核心方法都写齐全。第二边界条件处理做到位每个 public 方法的最前面先做参数校验索引越界抛 IndexOutOfBoundsException空表移除抛 NoSuchElementException。第三主动考虑扩容和内存释放在 grow 方法里用 Arrays.copyOf 完成数组复制在 remove 方法里把尾部元素置空。写完代码后最好在脑子里过一遍测试用例比如空表插入、尾部插入、头删、扩容后的数据完整性。能把这一套流程走下来面试官对你的代码功底会有很深的印象。顺序表看起来简单但正因为简单很多人会忽略它背后的容量管理、边界校验、内存释放和并发安全问题。我在实际编码过程中的体会是一个顺序表的实现质量往往能直接反映一个人的编程基本功。把这份附录里的细节消化掉再回头去看 Java 源码里的 ArrayList你会发现那些看似平平无奇的操作每一条都是有讲究的。以后遇到类似的数据结构题多留个心眼先想清楚边界再动笔。