尧图网站开发 
最近在帮组里新人过数据结构发现一个很有趣的现象让写链表的删除、反转、合并大家基本都能写出来但一碰到顺序表尤其是“递增有序表插入”“按位置删除”这类题反而容易出错。一开始我还挺意外后来想想也正常——顺序表太“基础”了基础到很多人默认自己已经会了于是直接跳过原理去写代码结果在边界条件、扩容策略、数组移动方向这些地方反复踩坑。这件事也让我想把顺序表彻底讲透。不只是给出一套能跑的代码而是把几个高频题目——比如热词里那两道常见的“7-2 递增有序顺序表的插入”和“7-3 顺序表删除”——从原理到实现完整拆一遍顺便把工程上真正会用的 Java 版本也写出来。你可以把这篇当成一份“顺序表核心实战手册”不管是准备考试、刷 OJ还是在项目里需要自己实现一个动态数组都能直接拿来做参考。1. 顺序表到底是什么为什么它这么重要1.1 用一个日常场景理解顺序表你可以把顺序表想象成电影院的连排座位。观众一个一个按顺序坐下中间不留空位工作人员需要知道总共有多少座位、已经坐了多少人。观众进场时要么从最后一排往后顺着坐要么插到某一排中间——插的时候后面所有人都得站起来往后挪一个位置。散场时有人提前离开同样的后面的人得往前补位。这个场景里座位本身对应的是内存中一段连续的空间观众就是存储的元素。知道某个观众坐在第几个座位理论上你可以直接走过去找到他不需要挨个问。这就是顺序表最核心的两个特性物理连续、随机访问。1.2 数组和顺序表的关系很多人分不清数组和顺序表其实一句话就能讲明白顺序表是基于数组实现的线性表数组是它的底层存储结构顺序表是数组的一层“逻辑包装”。裸数组有三个问题不好处理第一长度固定装满了就装不下了第二插入和删除时需要手动移动元素代码分散且容易越界第三没有维护“已经用了多少空间”这个信息写代码时很容易把容量capacity和实际元素个数size搞混。顺序表做的事就是把这三件事收拢起来内部维护一个数组作为存储再维护一个 size 变量记录实际元素个数对外提供插入、删除、查找、扩容等统一方法。Java 里天天用的 ArrayList本质上就是一个封装得非常好的顺序表。1.3 什么时候选顺序表什么时候选链表这是面试里高频出现的问题也是在实际开发中选择数据结构时绕不开的权衡。顺序表的优势在随机访问按下标取元素的时间复杂度是 O(1)因为数组在内存里是连续的可以直接通过“首地址 下标 × 元素大小”算出目标位置。但它在头部插入或删除元素时需要把所有元素整体后移或前移时间复杂度是 O(n)。链表正好相反它不要求内存连续插入和删除只需要修改相邻节点的指针在已知节点引用的情况下是 O(1)。但随机访问某个节点时只能从头开始一步步走时间复杂度是 O(n)。如果你需要频繁按下标访问元素数据规模又比较稳定顺序表更合适。如果数据频繁增删、很少按下标取数链表可能更合适。不过在 Java 工程实践中绝大多数场景直接用 ArrayList 就够了真到了需要大量在头部操作的场景LinkedList 也未必是好选择更应该考虑 ArrayDeque 或者其他结构。2. 从零搭一个顺序表的结构2.1 底层字段设计写一个自己的动态顺序表基础字段其实就三个public class MyArrayListE { private Object[] data; // 真正存数据的数组 private int size; // 当前元素个数 private static final int DEFAULT_CAPACITY 10; }这里有个初学者一定会遇到的坑Java 不允许直接创建泛型数组。你不能写new E[10]编译器会直接报错。业界通用的做法是创建一个Object[]使用时强转成泛型E。SuppressWarnings(unchecked) public MyArrayList(int initialCapacity) { if (initialCapacity 0) { throw new IllegalArgumentException(容量不能为负数: initialCapacity); } data new Object[initialCapacity]; size 0; }2.2 为什么初始容量不能太小也不能太大初始容量的选择是一个典型的空间换时间问题。给太小比如写成 1那么每次插入几乎都要触发扩容性能会很差给太大比如直接开 10000而真实数据量只有几十个就会造成大量空间浪费。工程上默认给 10 是比较稳妥的做法这是一个经验值兼顾了大多数场景的内存占用和扩容频率。如果你明确知道数据量级——比如要存十万条记录——就直接在构造函数里指定初始容量避免中途反复扩容。2.3 扩容机制为什么是 1.5 倍而不是每次加一动态扩容是顺序表提升“动态”能力的关键但很多人只记得扩容时有这么个方法不清楚背后的策略取舍。先看最差的方案每次插入发现空间不够就只多开一个位置然后把所有旧数据复制过去。假设往空表里插入 n 个元素复制元素的次数大约为 123...n也就是 O(n²) 的总开销。数据量一大系统直接变卡。再来看成倍扩容的方案容量不够时扩大到原来的 2 倍。反复扩容过程中总共复制的元素数量是等比数列求和最后的量级是 O(n)。每次插入的平均时间复杂度就被摊销到了 O(1)。这就是为什么所有动态数组都要成倍扩容而不是“缺多少补多少”。至于为什么很多实现选 1.5 倍而不是 2 倍主要原因是内存碎片问题——倍数越小扩容后向操作系统申请新内存时越容易复用之前释放的旧内存块。Java 的 ArrayList 老版本扩容规则就是oldCapacity (oldCapacity 1)也就是 1.5 倍这是经过充分实践验证过的策略。3. 顺序表核心操作实现与复杂度分析3.1 插入操作方向错了直接覆盖数据插入操作是顺序表最核心、也最容易写错的方法。写错大多是因为移动方向搞反了。正确的思路是从最后一个元素开始逐个往后挪给要插入的位置腾出空间。比如要在下标为 index 的位置插入新元素那么下标从 size-1 到 index 的所有元素都要平移到自己后面一个位置。public void add(int index, E element) { // 1. 校验索引 if (index 0 || index size) { throw new IndexOutOfBoundsException(index: index , size: size); } // 2. 检查容量不够就扩容 ensureCapacity(size 1); // 3. 从后往前移动元素 for (int i size - 1; i index; i--) { data[i 1] data[i]; } // 4. 赋值size 自增 data[index] element; size; }我见过新手把循环写成从前往后移动for (int i index; i size; i) { data[i 1] data[i]; }这样写的结果是后一个位置被前一个位置的值覆盖整个区间后面的元素全部变得一样数据直接被破坏。所以记住一句话从后往前移动安全从前往后移动覆盖。从复杂度上看在末尾插入只需要 O(1)在头部插入需要移动 n 个元素需要 O(n)中间位置平均移动 n/2 个元素也是 O(n)。3.2 删除操作跟插入正好相反删除和插入是镜像操作。删除下标为 index 的元素时要把 index 后面的所有元素向前移动一位。这时候必须从前往后移动public E remove(int index) { if (index 0 || index size) { throw new IndexOutOfBoundsException(index: index , size: size); } E oldValue (E) data[index]; // 从前往后移动元素 for (int i index; i size - 1; i) { data[i] data[i 1]; } data[size - 1] null; // 最后一个位置置空防止内存泄漏 size--; return oldValue; }注意这里最后一行data[size - 1] null很多人会漏。如果不把最后一个位置置空数组会一直持有这个引用。如果里面存的是一个很大的对象GC 就没办法回收它长时间运行下来会造成内存泄露。这在 Java 的 ArrayList 源码里也有类似处理属于教科书不会细讲但实际工程必须注意的细节。3.3 查找操作的两个分支顺序表的查找分两种复杂度完全不同按下标查找直接返回data[index]O(1)。这是顺序表的天然优势。按值查找需要从 0 开始逐个比较equals找到则返回下标没找到返回 -1O(n)。如果数据本身有序可以优化成二分查找后面讲递增有序插入时会用到。3.4 扩容的核心代码扩容的逻辑不复杂但有几个细节值得说一下。private void ensureCapacity(int minCapacity) { if (minCapacity data.length) { return; } int oldCapacity data.length; int newCapacity oldCapacity (oldCapacity 1); // 1.5 倍 if (newCapacity minCapacity) { newCapacity minCapacity; } data Arrays.copyOf(data, newCapacity); }oldCapacity 1等价于oldCapacity / 2写成位运算一方面是性能略好另一方面也是源码风格的惯例。把原来数组的内容复制到新数组后直接把对象的 data 字段指向新数组旧数组会被 GC 回收。这里你可能会遇到一个问题扩容后外部如果有变量持有旧数组引用理论上还能访问旧数组。但在封装好的顺序表类里外部只能通过对象访问不会直接拿到内部数组所以不存在这个问题。如果你自己写代码时不小心把内部数组暴露给了外部那扩容后就可能出现数据不一致。4. 递增有序顺序表的插入4.1 题目本质先定位再插入“7-2 递增有序顺序表的插入”这类题目的描述基本都是这样的有一个递增有序的顺序表现在要插入一个元素 x要求插入后仍然是递增有序的。这类题的核心可以拆成两个步骤第一步找到 x 应该插入的位置第二步调用或实现一个“指定位置插入”的操作。很多人在第一步上栽跟头。对于有序序列要找 x 插入的位置本质是找“第一个大于 x 的元素位置”。如果所有元素都小于等于 x那么 x 直接插入到末尾。4.2 方式一顺序查找最容易写对public static int searchInsertPosition(int[] arr, int size, int x) { for (int i 0; i size; i) { if (arr[i] x) { return i; } } return size; }这个写法简单直观从前往后扫描第一个比 x 大的元素下标就是插入位置。如果全部比完都没找到说明 x 比所有元素都大插到末尾也就是返回当前 size。有一个很普遍的疑问这里有元素等于 x 怎么办比如数组是 1, 3, 3, 5插入 3应该插在哪里如果题目要求“插入后仍然递增”并没有约束相等元素的位置那么插到第一个大于 x 的位置也就是第一个 5 的位置得到 1, 3, 3, 3, 5依然是递增的。也可以插到第一个等于 x 的元素之前得到的结果也仍然递增。绝大多数题目不会对此做硬性要求只要你不插到破坏顺序的位置就行。4.3 方式二二分查找面试加分项顺序查找的时间复杂度是 O(n)再配合移动元素的 O(n)整体是 O(n)这已经是最优量级了因为无论如何都要移动元素。但定位这一步本身可以更快——二分查找时间复杂度是 O(log n)。不过这里有一个典型的边界陷阱普通的二分查找找到的是“是否存在目标值”而你需要的是“第一个大于 x 的位置”两者不完全等价。你必须维护一个pos变量每当做往右收拢区间时记录当前的下标。public static int binarySearchInsertPosition(int[] arr, int size, int x) { int low 0, high size - 1; int pos size; // 默认插到末尾 while (low high) { int mid (low high) 1; if (arr[mid] x) { pos mid; // 第一个大于 x 的位置先记下来 high mid - 1; } else { low mid 1; } } return pos; }这里有两个细节值得展开说一下。第一为什么pos初始值是 size。因为如果整个数组里没有大于 x 的元素说明 x 应该放在最后面。如果初始值设为 0后续又没进到if分支返回值就会是错误的。第二为什么中位数计算用(low high) 1而不是(low high) / 2。当 low 和 high 都是很大的 int 时两者相加可能溢出。是无符号右移可以避免溢出带来的负数问题。很多老面试题会考这个点现在面试里也偶尔会问到。在有序顺序表插入的场景里由于移动元素本身是 O(n)二分查找的 O(log n) 并不会改变整体 O(n) 的复杂度。但从代码健壮性和面试表现来看二分查找方案明显更有亮点也体现了你对数据的敏感度。4.4 完整示例Java 实现“递增有序插入”如果是在 OJ 上做题你通常不需要写一个完整的类只需要实现核心逻辑。这里给一个完整可运行的 Java 示例import java.util.Arrays; public class SortedListInsert { public static void main(String[] args) { int[] data new int[10]; int size 5; // 初始有序数组1, 3, 5, 7, 9 for (int i 0; i size; i) { data[i] 2 * i 1; } int x 6; // 1. 找位置 int pos binarySearchInsertPosition(data, size, x); // 2. 移动元素从后往前 for (int i size; i pos; i--) { data[i] data[i - 1]; } // 3. 插入 data[pos] x; size; System.out.println(Arrays.toString(Arrays.copyOf(data, size))); // 输出[1, 3, 5, 6, 7, 9] } public static int binarySearchInsertPosition(int[] arr, int size, int x) { int low 0, high size - 1, pos size; while (low high) { int mid (low high) 1; if (arr[mid] x) { pos mid; high mid - 1; } else { low mid 1; } } return pos; } }运行结果会在控制台打印[1, 3, 5, 6, 7, 9]插入顺序正确元素移动也没有越界。这段代码可以直接拷到本地跑也可以改写成 C、Python 等语言逻辑是通用的。5. 顺序表的删除操作从基础到变形5.1 基础版按位置删除“7-3 顺序表删除”最基础的版本就是按位置删除上一节已经给过完整代码。这里重点提醒一下常见错误。很多新手的循环边界会写成for (int i index; i size; i) { data[i] data[i 1]; }当i size - 1时data[i 1]访问的就是data[size]而当前元素个数是 size最大下标是 size - 1所以这里一定越界。正确的循环结束条件是i size - 1确保i 1最大是 size - 1。5.2 按值删除如何处理所有匹配的元素比按位置删除更进一步的是按值删除。例如删除所有等于 x 的元素。最笨的办法是外层循环多次扫描找到一个删一个时间复杂度最坏 O(n²)。面试或者做题时这样写通常也能过但谈不上好。更优的做法是“双指针原地覆盖法”一个指针负责遍历原数组另一个指针指向新数组的写入位置。把不等于 x 的元素依次复制到前面去最后把 size 设为新长度。public static int removeAllOccurrences(int[] data, int size, int x) { int write 0; for (int read 0; read size; read) { if (data[read] ! x) { data[write] data[read]; } } return write; // 新 size }这个写法非常经典一次遍历完成删除时间复杂度 O(n)空间复杂度 O(1)。它的巧妙之处在于不需要频繁移动大量元素而是让保留下来的元素直接“竞争”到前面。5.3 有序顺序表去重如果顺序表是有序的删除重复元素也是一个高频变体。由于有序重复元素一定相邻所以同样可以用双指针法public static int removeDuplicates(int[] data, int size) { if (size 1) { return size; } int write 0; for (int read 1; read size; read) { if (data[read] ! data[write]) { write; data[write] data[read]; } } return write 1; }这里需要注意最后一个细节write从 0 开始代表最后一个保留元素的下标。每次遇到新元素先把 write 加一再把新值写入。循环结束后新数组长度是write 1因为这个下标是从 0 开始数的。5.4 删除指定区间的数据还有一种题目要求删除下标区间 [from, to) 内的元素。这个写法是移动元素 调整 size 的组合应用public static int removeRange(int[] data, int size, int from, int to) { if (from 0 || to size || from to) { throw new IllegalArgumentException(区间参数不合法); } int removed to - from; for (int i to; i size; i) { data[i - removed] data[i]; } return size - removed; }本质上就是把 to 后面的元素整体平移到 from 位置。这类变体的核心思路不变先确定要保留的元素区间再做平移最后调整 size。把最基础的移动思想理解透任何变形题都能拆解成“定位 移动 改长度”这三步。6. 完整可用的 Java 顺序表实现6.1 封装一个带扩容的顺序表类把前面所有方法整合到一个类里就是一份完整的、可复用的 Java 顺序表实现。工程上直接用 ArrayList 当然更省事但自己实现一遍能真正掌握它的内部机制也有助于理解 ArrayList 源码。import java.util.Arrays; public class MyArrayListE { private Object[] 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(容量不能为负数: initialCapacity); } data new Object[initialCapacity]; size 0; } public int size() { return size; } public boolean isEmpty() { return size 0; } SuppressWarnings(unchecked) public E get(int index) { checkIndexForGet(index); return (E) data[index]; } public void add(E element) { add(size, element); } public void add(int index, E element) { if (index 0 || index size) { throw new IndexOutOfBoundsException(index: index , size: size); } ensureCapacity(size 1); for (int i size - 1; i index; i--) { data[i 1] data[i]; } data[index] element; size; } SuppressWarnings(unchecked) public E remove(int index) { checkIndexForGet(index); E oldValue (E) data[index]; for (int i index; i size - 1; i) { data[i] data[i 1]; } data[size - 1] null; size--; return oldValue; } public boolean removeByValue(E value) { for (int i 0; i size; i) { if (value.equals(data[i])) { remove(i); return true; } } return false; } public int indexOf(E value) { for (int i 0; i size; i) { if (value.equals(data[i])) { return i; } } return -1; } private void checkIndexForGet(int index) { if (index 0 || index size) { throw new IndexOutOfBoundsException(index: index , size: size); } } private void ensureCapacity(int minCapacity) { if (minCapacity data.length) { return; } int oldCapacity data.length; int newCapacity oldCapacity (oldCapacity 1); if (newCapacity minCapacity) { newCapacity minCapacity; } data Arrays.copyOf(data, newCapacity); } Override public String toString() { return Arrays.toString(Arrays.copyOf(data, size)); } }这个类麻雀虽小但五脏俱全。它包含了顺序表的核心操作构造、扩容、插入、删除、查找、输出。6.2 ArrayList 里那些值得学习的“隐藏细节”如果你去看 JDK 里 ArrayList 的源码会发现它的实现比上面的版本复杂很多但有几个细节非常值得学习。第一ArrayList 提供了trimToSize()方法可以把容量缩减到当前元素个数释放多余空间。这在数据量从大变小、且内存比较紧张的瞬间很实用。第二ArrayList 的remove方法里面确实做了“最后一个位置置 null”的操作目的就是让 GC 能回收对象引用防止内存泄漏。第三ArrayList 的扩容上限是Integer.MAX_VALUE - 8而不是Integer.MAX_VALUE。这是因为部分虚拟机在数组对象中会保留一些头部信息如果数组容量接近 int 的上界可能会导致内存溢出。当然正常业务里几乎不会碰到这个边界但知道这一点能避免你在极端的面试题里发懵。6.3 用这个类快速解决“7-2”和“7-3”有了这个类做类似题目就很简单了。比如用 MyArrayList 完成一个带有序插入的逻辑public class Demo { public static void main(String[] args) { MyArrayListInteger list new MyArrayList(); list.add(1); list.add(3); list.add(5); list.add(7); int x 4; // 找到第一个大于 x 的位置 int pos 0; while (pos list.size() list.get(pos) x) { pos; } list.add(pos, x); System.out.println(list); // [1, 3, 4, 5, 7] } }删除操作也是同理用removeByValue或者remove(index)都能直接解决问题。你完全可以用这样一个自写的类来刷题比直接操作裸数组更不容易出错代码也更好读。7. 顺序表实战中的常见问题与排查思路7.1 数组越界看到 ArrayIndexOutOfBoundsException 怎么处理数组越界是顺序表相关代码里最常见的报错。出现这个异常绝大多数情况下不是数组长度有问题而是“逻辑下标”超出了“当前有效元素范围”。排查思路要清晰先看 size 是多少。比如一个顺序表添加了 3 个元素size 是 3有效下标范围是 0 到 2。如果你删除了 1 个元素但没有正确更新 size那么后续遍历拿到的是旧的 size 3访问 data[2] 时实际上这个位置已经不属于有效数据了就会出现各种诡异问题。一个很实用的技巧是在涉及数组下标的地方注释上标注“这个 index 是逻辑下标还是物理下标”。逻辑下标对应的是元素在顺序表中的序号物理下标对应的是数据在数组中的位置。两者大多数情况下一致但在删除、插入后如果代码本身有误就会错位。7.2 扩容后旧数据丢失一个隐蔽的引用问题有人会把数组定义在外部然后这样扩容Object[] newData Arrays.copyOf(data, data.length * 2); data newData;这一步没问题问题可能出在这一行Object[] arr list.getData(); // 假设你写了 getData 方法如果外部拿到了内部数组的引用然后内部发生了扩容外部持有的还是旧数组引用于是读到的数据就是旧的、不完整的。这就是为什么封装类里不应该把内部数组直接暴露出去。如果你需要遍历可以提供get(int index)或迭代器而不是直接返回数组。7.3 删除或插入后数据错乱移动方向没搞清这个问题前面已经反复强调过这里再提供一个自查方法。插入时你要在空出来的位置放新元素所以移动方向是从后往前保证先腾出空间再逐个后移。删除时你要把后面的元素往前填方向是从前往后保证前面的位置先被覆盖不会覆盖到还没处理的数据。写成口诀就是插入从后往前删除从前往后。如果发现自己代码运行结果里元素顺序乱了先检查循环方向和移动区间。7.4 equals 和 的坑在按值查找或删除时比较两个元素是否相等是一个核心操作。对于基本类型包装类如 Integer、Stringequals是比较内容是比较引用。对于自定义对象如果不重写equals即使两个对象内容完全相同equals也会返回 false。所以写按值查找时规范写法是if (value null ? data[i] null : value.equals(data[i])) { // found }要处理 value 为 null 的情况避免空指针。Java 7 以后的Objects.equals(value, data[i])内部已经处理过 null可以直接用。7.5 为什么不建议在循环里频繁扩容最后说一个性能相关的问题。如果一开始就知道要插入一万条数据就不要用默认构造器然后循环 add因为默认容量只有 10插入过程会触发多次扩容每一次扩容都要复制已有元素。数据量大时这个开销会被明显放大。正确做法是在构造时直接指定容量或者提前调用ensureCapacity。ArrayList 源码对这个场景提供了ArrayList(int initialCapacity)构造函数就是这个原因。同理自己的动态顺序表类也应该保留类似的能力这也是工程中对性能的基本尊重。8. 从实战题目到工程使用的几点个人体会做数据结构题和写工程代码看起来是两件事但底层的能力要求是相通的你能不能在有限的时间内把“数据怎么存”“操作怎么做”“边界条件是什么”想清楚。我从带新人和刷 OJ 题目里总结出几条个人经验分享出来供参考。第一顺序表的题目不要硬记代码。反复出现的高频题——“递增有序插入”“删除所有等于某个值的元素”“有序去重”——本质上都是三个动作的组合定位、移动、调整长度。把这三个动作吃透遇到什么变形题都不慌。第二写代码前先在纸上画数组。哪怕是很短的一段数组把下标标出来手动推一遍移动过程比直接写代码再调试快得多。很多越界和覆盖问题在画图阶段就能被发现。第三学习 ArrayList 源码是一种回报率很高的投资。它的代码不算长但里面凝聚了大量工程经验扩容策略、迭代器设计、快速失败机制、性能优化细节。读一遍源码你对顺序表的理解深度会远超只会调 API 的同事。第四能复现题目逻辑和能在工程中设计动态数组结构是两种不同的水平。做题时只需要保证功能正确工程中还要考虑并发、性能、内存、可读性。如果未来想往中间件、大数据、数据库方向走这类底层数据结构的理解会直接影响你的天花板。顺序表本身不难难的是把它背后的空间分配、元素移动、边界处理这些细节内化为自己的本能。写代码时多想一想“内存里到底发生了什么”多动手验证几次这些细节就会慢慢变成你的手感。这篇指南里提到的几个易错点和代码片段都是我实际调试中遇到过的问题希望你少走这些弯路。 
最近在帮组里新人过数据结构发现一个很有趣的现象让写链表的删除、反转、合并大家基本都能写出来但一碰到顺序表尤其是“递增有序表插入”“按位置删除”这类题反而容易出错。一开始我还挺意外后来想想也正常——顺序表太“基础”了基础到很多人默认自己已经会了于是直接跳过原理去写代码结果在边界条件、扩容策略、数组移动方向这些地方反复踩坑。这件事也让我想把顺序表彻底讲透。不只是给出一套能跑的代码而是把几个高频题目——比如热词里那两道常见的“7-2 递增有序顺序表的插入”和“7-3 顺序表删除”——从原理到实现完整拆一遍顺便把工程上真正会用的 Java 版本也写出来。你可以把这篇当成一份“顺序表核心实战手册”不管是准备考试、刷 OJ还是在项目里需要自己实现一个动态数组都能直接拿来做参考。1. 顺序表到底是什么为什么它这么重要1.1 用一个日常场景理解顺序表你可以把顺序表想象成电影院的连排座位。观众一个一个按顺序坐下中间不留空位工作人员需要知道总共有多少座位、已经坐了多少人。观众进场时要么从最后一排往后顺着坐要么插到某一排中间——插的时候后面所有人都得站起来往后挪一个位置。散场时有人提前离开同样的后面的人得往前补位。这个场景里座位本身对应的是内存中一段连续的空间观众就是存储的元素。知道某个观众坐在第几个座位理论上你可以直接走过去找到他不需要挨个问。这就是顺序表最核心的两个特性物理连续、随机访问。1.2 数组和顺序表的关系很多人分不清数组和顺序表其实一句话就能讲明白顺序表是基于数组实现的线性表数组是它的底层存储结构顺序表是数组的一层“逻辑包装”。裸数组有三个问题不好处理第一长度固定装满了就装不下了第二插入和删除时需要手动移动元素代码分散且容易越界第三没有维护“已经用了多少空间”这个信息写代码时很容易把容量capacity和实际元素个数size搞混。顺序表做的事就是把这三件事收拢起来内部维护一个数组作为存储再维护一个 size 变量记录实际元素个数对外提供插入、删除、查找、扩容等统一方法。Java 里天天用的 ArrayList本质上就是一个封装得非常好的顺序表。1.3 什么时候选顺序表什么时候选链表这是面试里高频出现的问题也是在实际开发中选择数据结构时绕不开的权衡。顺序表的优势在随机访问按下标取元素的时间复杂度是 O(1)因为数组在内存里是连续的可以直接通过“首地址 下标 × 元素大小”算出目标位置。但它在头部插入或删除元素时需要把所有元素整体后移或前移时间复杂度是 O(n)。链表正好相反它不要求内存连续插入和删除只需要修改相邻节点的指针在已知节点引用的情况下是 O(1)。但随机访问某个节点时只能从头开始一步步走时间复杂度是 O(n)。如果你需要频繁按下标访问元素数据规模又比较稳定顺序表更合适。如果数据频繁增删、很少按下标取数链表可能更合适。不过在 Java 工程实践中绝大多数场景直接用 ArrayList 就够了真到了需要大量在头部操作的场景LinkedList 也未必是好选择更应该考虑 ArrayDeque 或者其他结构。2. 从零搭一个顺序表的结构2.1 底层字段设计写一个自己的动态顺序表基础字段其实就三个public class MyArrayListE { private Object[] data; // 真正存数据的数组 private int size; // 当前元素个数 private static final int DEFAULT_CAPACITY 10; }这里有个初学者一定会遇到的坑Java 不允许直接创建泛型数组。你不能写new E[10]编译器会直接报错。业界通用的做法是创建一个Object[]使用时强转成泛型E。SuppressWarnings(unchecked) public MyArrayList(int initialCapacity) { if (initialCapacity 0) { throw new IllegalArgumentException(容量不能为负数: initialCapacity); } data new Object[initialCapacity]; size 0; }2.2 为什么初始容量不能太小也不能太大初始容量的选择是一个典型的空间换时间问题。给太小比如写成 1那么每次插入几乎都要触发扩容性能会很差给太大比如直接开 10000而真实数据量只有几十个就会造成大量空间浪费。工程上默认给 10 是比较稳妥的做法这是一个经验值兼顾了大多数场景的内存占用和扩容频率。如果你明确知道数据量级——比如要存十万条记录——就直接在构造函数里指定初始容量避免中途反复扩容。2.3 扩容机制为什么是 1.5 倍而不是每次加一动态扩容是顺序表提升“动态”能力的关键但很多人只记得扩容时有这么个方法不清楚背后的策略取舍。先看最差的方案每次插入发现空间不够就只多开一个位置然后把所有旧数据复制过去。假设往空表里插入 n 个元素复制元素的次数大约为 123...n也就是 O(n²) 的总开销。数据量一大系统直接变卡。再来看成倍扩容的方案容量不够时扩大到原来的 2 倍。反复扩容过程中总共复制的元素数量是等比数列求和最后的量级是 O(n)。每次插入的平均时间复杂度就被摊销到了 O(1)。这就是为什么所有动态数组都要成倍扩容而不是“缺多少补多少”。至于为什么很多实现选 1.5 倍而不是 2 倍主要原因是内存碎片问题——倍数越小扩容后向操作系统申请新内存时越容易复用之前释放的旧内存块。Java 的 ArrayList 老版本扩容规则就是oldCapacity (oldCapacity 1)也就是 1.5 倍这是经过充分实践验证过的策略。3. 顺序表核心操作实现与复杂度分析3.1 插入操作方向错了直接覆盖数据插入操作是顺序表最核心、也最容易写错的方法。写错大多是因为移动方向搞反了。正确的思路是从最后一个元素开始逐个往后挪给要插入的位置腾出空间。比如要在下标为 index 的位置插入新元素那么下标从 size-1 到 index 的所有元素都要平移到自己后面一个位置。public void add(int index, E element) { // 1. 校验索引 if (index 0 || index size) { throw new IndexOutOfBoundsException(index: index , size: size); } // 2. 检查容量不够就扩容 ensureCapacity(size 1); // 3. 从后往前移动元素 for (int i size - 1; i index; i--) { data[i 1] data[i]; } // 4. 赋值size 自增 data[index] element; size; }我见过新手把循环写成从前往后移动for (int i index; i size; i) { data[i 1] data[i]; }这样写的结果是后一个位置被前一个位置的值覆盖整个区间后面的元素全部变得一样数据直接被破坏。所以记住一句话从后往前移动安全从前往后移动覆盖。从复杂度上看在末尾插入只需要 O(1)在头部插入需要移动 n 个元素需要 O(n)中间位置平均移动 n/2 个元素也是 O(n)。3.2 删除操作跟插入正好相反删除和插入是镜像操作。删除下标为 index 的元素时要把 index 后面的所有元素向前移动一位。这时候必须从前往后移动public E remove(int index) { if (index 0 || index size) { throw new IndexOutOfBoundsException(index: index , size: size); } E oldValue (E) data[index]; // 从前往后移动元素 for (int i index; i size - 1; i) { data[i] data[i 1]; } data[size - 1] null; // 最后一个位置置空防止内存泄漏 size--; return oldValue; }注意这里最后一行data[size - 1] null很多人会漏。如果不把最后一个位置置空数组会一直持有这个引用。如果里面存的是一个很大的对象GC 就没办法回收它长时间运行下来会造成内存泄露。这在 Java 的 ArrayList 源码里也有类似处理属于教科书不会细讲但实际工程必须注意的细节。3.3 查找操作的两个分支顺序表的查找分两种复杂度完全不同按下标查找直接返回data[index]O(1)。这是顺序表的天然优势。按值查找需要从 0 开始逐个比较equals找到则返回下标没找到返回 -1O(n)。如果数据本身有序可以优化成二分查找后面讲递增有序插入时会用到。3.4 扩容的核心代码扩容的逻辑不复杂但有几个细节值得说一下。private void ensureCapacity(int minCapacity) { if (minCapacity data.length) { return; } int oldCapacity data.length; int newCapacity oldCapacity (oldCapacity 1); // 1.5 倍 if (newCapacity minCapacity) { newCapacity minCapacity; } data Arrays.copyOf(data, newCapacity); }oldCapacity 1等价于oldCapacity / 2写成位运算一方面是性能略好另一方面也是源码风格的惯例。把原来数组的内容复制到新数组后直接把对象的 data 字段指向新数组旧数组会被 GC 回收。这里你可能会遇到一个问题扩容后外部如果有变量持有旧数组引用理论上还能访问旧数组。但在封装好的顺序表类里外部只能通过对象访问不会直接拿到内部数组所以不存在这个问题。如果你自己写代码时不小心把内部数组暴露给了外部那扩容后就可能出现数据不一致。4. 递增有序顺序表的插入4.1 题目本质先定位再插入“7-2 递增有序顺序表的插入”这类题目的描述基本都是这样的有一个递增有序的顺序表现在要插入一个元素 x要求插入后仍然是递增有序的。这类题的核心可以拆成两个步骤第一步找到 x 应该插入的位置第二步调用或实现一个“指定位置插入”的操作。很多人在第一步上栽跟头。对于有序序列要找 x 插入的位置本质是找“第一个大于 x 的元素位置”。如果所有元素都小于等于 x那么 x 直接插入到末尾。4.2 方式一顺序查找最容易写对public static int searchInsertPosition(int[] arr, int size, int x) { for (int i 0; i size; i) { if (arr[i] x) { return i; } } return size; }这个写法简单直观从前往后扫描第一个比 x 大的元素下标就是插入位置。如果全部比完都没找到说明 x 比所有元素都大插到末尾也就是返回当前 size。有一个很普遍的疑问这里有元素等于 x 怎么办比如数组是 1, 3, 3, 5插入 3应该插在哪里如果题目要求“插入后仍然递增”并没有约束相等元素的位置那么插到第一个大于 x 的位置也就是第一个 5 的位置得到 1, 3, 3, 3, 5依然是递增的。也可以插到第一个等于 x 的元素之前得到的结果也仍然递增。绝大多数题目不会对此做硬性要求只要你不插到破坏顺序的位置就行。4.3 方式二二分查找面试加分项顺序查找的时间复杂度是 O(n)再配合移动元素的 O(n)整体是 O(n)这已经是最优量级了因为无论如何都要移动元素。但定位这一步本身可以更快——二分查找时间复杂度是 O(log n)。不过这里有一个典型的边界陷阱普通的二分查找找到的是“是否存在目标值”而你需要的是“第一个大于 x 的位置”两者不完全等价。你必须维护一个pos变量每当做往右收拢区间时记录当前的下标。public static int binarySearchInsertPosition(int[] arr, int size, int x) { int low 0, high size - 1; int pos size; // 默认插到末尾 while (low high) { int mid (low high) 1; if (arr[mid] x) { pos mid; // 第一个大于 x 的位置先记下来 high mid - 1; } else { low mid 1; } } return pos; }这里有两个细节值得展开说一下。第一为什么pos初始值是 size。因为如果整个数组里没有大于 x 的元素说明 x 应该放在最后面。如果初始值设为 0后续又没进到if分支返回值就会是错误的。第二为什么中位数计算用(low high) 1而不是(low high) / 2。当 low 和 high 都是很大的 int 时两者相加可能溢出。是无符号右移可以避免溢出带来的负数问题。很多老面试题会考这个点现在面试里也偶尔会问到。在有序顺序表插入的场景里由于移动元素本身是 O(n)二分查找的 O(log n) 并不会改变整体 O(n) 的复杂度。但从代码健壮性和面试表现来看二分查找方案明显更有亮点也体现了你对数据的敏感度。4.4 完整示例Java 实现“递增有序插入”如果是在 OJ 上做题你通常不需要写一个完整的类只需要实现核心逻辑。这里给一个完整可运行的 Java 示例import java.util.Arrays; public class SortedListInsert { public static void main(String[] args) { int[] data new int[10]; int size 5; // 初始有序数组1, 3, 5, 7, 9 for (int i 0; i size; i) { data[i] 2 * i 1; } int x 6; // 1. 找位置 int pos binarySearchInsertPosition(data, size, x); // 2. 移动元素从后往前 for (int i size; i pos; i--) { data[i] data[i - 1]; } // 3. 插入 data[pos] x; size; System.out.println(Arrays.toString(Arrays.copyOf(data, size))); // 输出[1, 3, 5, 6, 7, 9] } public static int binarySearchInsertPosition(int[] arr, int size, int x) { int low 0, high size - 1, pos size; while (low high) { int mid (low high) 1; if (arr[mid] x) { pos mid; high mid - 1; } else { low mid 1; } } return pos; } }运行结果会在控制台打印[1, 3, 5, 6, 7, 9]插入顺序正确元素移动也没有越界。这段代码可以直接拷到本地跑也可以改写成 C、Python 等语言逻辑是通用的。5. 顺序表的删除操作从基础到变形5.1 基础版按位置删除“7-3 顺序表删除”最基础的版本就是按位置删除上一节已经给过完整代码。这里重点提醒一下常见错误。很多新手的循环边界会写成for (int i index; i size; i) { data[i] data[i 1]; }当i size - 1时data[i 1]访问的就是data[size]而当前元素个数是 size最大下标是 size - 1所以这里一定越界。正确的循环结束条件是i size - 1确保i 1最大是 size - 1。5.2 按值删除如何处理所有匹配的元素比按位置删除更进一步的是按值删除。例如删除所有等于 x 的元素。最笨的办法是外层循环多次扫描找到一个删一个时间复杂度最坏 O(n²)。面试或者做题时这样写通常也能过但谈不上好。更优的做法是“双指针原地覆盖法”一个指针负责遍历原数组另一个指针指向新数组的写入位置。把不等于 x 的元素依次复制到前面去最后把 size 设为新长度。public static int removeAllOccurrences(int[] data, int size, int x) { int write 0; for (int read 0; read size; read) { if (data[read] ! x) { data[write] data[read]; } } return write; // 新 size }这个写法非常经典一次遍历完成删除时间复杂度 O(n)空间复杂度 O(1)。它的巧妙之处在于不需要频繁移动大量元素而是让保留下来的元素直接“竞争”到前面。5.3 有序顺序表去重如果顺序表是有序的删除重复元素也是一个高频变体。由于有序重复元素一定相邻所以同样可以用双指针法public static int removeDuplicates(int[] data, int size) { if (size 1) { return size; } int write 0; for (int read 1; read size; read) { if (data[read] ! data[write]) { write; data[write] data[read]; } } return write 1; }这里需要注意最后一个细节write从 0 开始代表最后一个保留元素的下标。每次遇到新元素先把 write 加一再把新值写入。循环结束后新数组长度是write 1因为这个下标是从 0 开始数的。5.4 删除指定区间的数据还有一种题目要求删除下标区间 [from, to) 内的元素。这个写法是移动元素 调整 size 的组合应用public static int removeRange(int[] data, int size, int from, int to) { if (from 0 || to size || from to) { throw new IllegalArgumentException(区间参数不合法); } int removed to - from; for (int i to; i size; i) { data[i - removed] data[i]; } return size - removed; }本质上就是把 to 后面的元素整体平移到 from 位置。这类变体的核心思路不变先确定要保留的元素区间再做平移最后调整 size。把最基础的移动思想理解透任何变形题都能拆解成“定位 移动 改长度”这三步。6. 完整可用的 Java 顺序表实现6.1 封装一个带扩容的顺序表类把前面所有方法整合到一个类里就是一份完整的、可复用的 Java 顺序表实现。工程上直接用 ArrayList 当然更省事但自己实现一遍能真正掌握它的内部机制也有助于理解 ArrayList 源码。import java.util.Arrays; public class MyArrayListE { private Object[] 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(容量不能为负数: initialCapacity); } data new Object[initialCapacity]; size 0; } public int size() { return size; } public boolean isEmpty() { return size 0; } SuppressWarnings(unchecked) public E get(int index) { checkIndexForGet(index); return (E) data[index]; } public void add(E element) { add(size, element); } public void add(int index, E element) { if (index 0 || index size) { throw new IndexOutOfBoundsException(index: index , size: size); } ensureCapacity(size 1); for (int i size - 1; i index; i--) { data[i 1] data[i]; } data[index] element; size; } SuppressWarnings(unchecked) public E remove(int index) { checkIndexForGet(index); E oldValue (E) data[index]; for (int i index; i size - 1; i) { data[i] data[i 1]; } data[size - 1] null; size--; return oldValue; } public boolean removeByValue(E value) { for (int i 0; i size; i) { if (value.equals(data[i])) { remove(i); return true; } } return false; } public int indexOf(E value) { for (int i 0; i size; i) { if (value.equals(data[i])) { return i; } } return -1; } private void checkIndexForGet(int index) { if (index 0 || index size) { throw new IndexOutOfBoundsException(index: index , size: size); } } private void ensureCapacity(int minCapacity) { if (minCapacity data.length) { return; } int oldCapacity data.length; int newCapacity oldCapacity (oldCapacity 1); if (newCapacity minCapacity) { newCapacity minCapacity; } data Arrays.copyOf(data, newCapacity); } Override public String toString() { return Arrays.toString(Arrays.copyOf(data, size)); } }这个类麻雀虽小但五脏俱全。它包含了顺序表的核心操作构造、扩容、插入、删除、查找、输出。6.2 ArrayList 里那些值得学习的“隐藏细节”如果你去看 JDK 里 ArrayList 的源码会发现它的实现比上面的版本复杂很多但有几个细节非常值得学习。第一ArrayList 提供了trimToSize()方法可以把容量缩减到当前元素个数释放多余空间。这在数据量从大变小、且内存比较紧张的瞬间很实用。第二ArrayList 的remove方法里面确实做了“最后一个位置置 null”的操作目的就是让 GC 能回收对象引用防止内存泄漏。第三ArrayList 的扩容上限是Integer.MAX_VALUE - 8而不是Integer.MAX_VALUE。这是因为部分虚拟机在数组对象中会保留一些头部信息如果数组容量接近 int 的上界可能会导致内存溢出。当然正常业务里几乎不会碰到这个边界但知道这一点能避免你在极端的面试题里发懵。6.3 用这个类快速解决“7-2”和“7-3”有了这个类做类似题目就很简单了。比如用 MyArrayList 完成一个带有序插入的逻辑public class Demo { public static void main(String[] args) { MyArrayListInteger list new MyArrayList(); list.add(1); list.add(3); list.add(5); list.add(7); int x 4; // 找到第一个大于 x 的位置 int pos 0; while (pos list.size() list.get(pos) x) { pos; } list.add(pos, x); System.out.println(list); // [1, 3, 4, 5, 7] } }删除操作也是同理用removeByValue或者remove(index)都能直接解决问题。你完全可以用这样一个自写的类来刷题比直接操作裸数组更不容易出错代码也更好读。7. 顺序表实战中的常见问题与排查思路7.1 数组越界看到 ArrayIndexOutOfBoundsException 怎么处理数组越界是顺序表相关代码里最常见的报错。出现这个异常绝大多数情况下不是数组长度有问题而是“逻辑下标”超出了“当前有效元素范围”。排查思路要清晰先看 size 是多少。比如一个顺序表添加了 3 个元素size 是 3有效下标范围是 0 到 2。如果你删除了 1 个元素但没有正确更新 size那么后续遍历拿到的是旧的 size 3访问 data[2] 时实际上这个位置已经不属于有效数据了就会出现各种诡异问题。一个很实用的技巧是在涉及数组下标的地方注释上标注“这个 index 是逻辑下标还是物理下标”。逻辑下标对应的是元素在顺序表中的序号物理下标对应的是数据在数组中的位置。两者大多数情况下一致但在删除、插入后如果代码本身有误就会错位。7.2 扩容后旧数据丢失一个隐蔽的引用问题有人会把数组定义在外部然后这样扩容Object[] newData Arrays.copyOf(data, data.length * 2); data newData;这一步没问题问题可能出在这一行Object[] arr list.getData(); // 假设你写了 getData 方法如果外部拿到了内部数组的引用然后内部发生了扩容外部持有的还是旧数组引用于是读到的数据就是旧的、不完整的。这就是为什么封装类里不应该把内部数组直接暴露出去。如果你需要遍历可以提供get(int index)或迭代器而不是直接返回数组。7.3 删除或插入后数据错乱移动方向没搞清这个问题前面已经反复强调过这里再提供一个自查方法。插入时你要在空出来的位置放新元素所以移动方向是从后往前保证先腾出空间再逐个后移。删除时你要把后面的元素往前填方向是从前往后保证前面的位置先被覆盖不会覆盖到还没处理的数据。写成口诀就是插入从后往前删除从前往后。如果发现自己代码运行结果里元素顺序乱了先检查循环方向和移动区间。7.4 equals 和 的坑在按值查找或删除时比较两个元素是否相等是一个核心操作。对于基本类型包装类如 Integer、Stringequals是比较内容是比较引用。对于自定义对象如果不重写equals即使两个对象内容完全相同equals也会返回 false。所以写按值查找时规范写法是if (value null ? data[i] null : value.equals(data[i])) { // found }要处理 value 为 null 的情况避免空指针。Java 7 以后的Objects.equals(value, data[i])内部已经处理过 null可以直接用。7.5 为什么不建议在循环里频繁扩容最后说一个性能相关的问题。如果一开始就知道要插入一万条数据就不要用默认构造器然后循环 add因为默认容量只有 10插入过程会触发多次扩容每一次扩容都要复制已有元素。数据量大时这个开销会被明显放大。正确做法是在构造时直接指定容量或者提前调用ensureCapacity。ArrayList 源码对这个场景提供了ArrayList(int initialCapacity)构造函数就是这个原因。同理自己的动态顺序表类也应该保留类似的能力这也是工程中对性能的基本尊重。8. 从实战题目到工程使用的几点个人体会做数据结构题和写工程代码看起来是两件事但底层的能力要求是相通的你能不能在有限的时间内把“数据怎么存”“操作怎么做”“边界条件是什么”想清楚。我从带新人和刷 OJ 题目里总结出几条个人经验分享出来供参考。第一顺序表的题目不要硬记代码。反复出现的高频题——“递增有序插入”“删除所有等于某个值的元素”“有序去重”——本质上都是三个动作的组合定位、移动、调整长度。把这三个动作吃透遇到什么变形题都不慌。第二写代码前先在纸上画数组。哪怕是很短的一段数组把下标标出来手动推一遍移动过程比直接写代码再调试快得多。很多越界和覆盖问题在画图阶段就能被发现。第三学习 ArrayList 源码是一种回报率很高的投资。它的代码不算长但里面凝聚了大量工程经验扩容策略、迭代器设计、快速失败机制、性能优化细节。读一遍源码你对顺序表的理解深度会远超只会调 API 的同事。第四能复现题目逻辑和能在工程中设计动态数组结构是两种不同的水平。做题时只需要保证功能正确工程中还要考虑并发、性能、内存、可读性。如果未来想往中间件、大数据、数据库方向走这类底层数据结构的理解会直接影响你的天花板。顺序表本身不难难的是把它背后的空间分配、元素移动、边界处理这些细节内化为自己的本能。写代码时多想一想“内存里到底发生了什么”多动手验证几次这些细节就会慢慢变成你的手感。这篇指南里提到的几个易错点和代码片段都是我实际调试中遇到过的问题希望你少走这些弯路。