1. 顺序表到底是什么：先摘掉“数据结构”这顶帽子
很多初学者看到“顺序表（SeqList）”这个名字，第一反应是又要背一个抽象概念了。但实际上，你早就见过它了——数组中里日常写的 int[]、String[]，底层就是顺序表；Java 里天天用的 ArrayList，本质就是装进类壳子里的顺序表。顺序表不是某种高深魔法，它就是“用一段连续的内存空间，按顺序存储一列相同类型数据”的容器。
1.1 数组和顺序表：同一件事的两种说法
数组是语言层面的东西，你写int[] arr = new int[10]，编译器就给你划一块连续内存。顺序表是数据结构层面的概念，它描述的是“逻辑上相邻的元素，在物理存储上也相邻”的线性结构。区别在哪里？
数组的长度在创建时就固定了，装满了想再装就得自己找新数组、自己拷数据；顺序表却把这一套“扩容、移动、管理”的逻辑封装成了操作，使用者只需要 add、get、remove，不用关心底层数组满了怎么办。
所以，顺序表 = 数组 + 一套自动管理的操作方法。这也是为什么 Java 里ArrayList的实现核心就是一个Object[] elementData——它就是一个会自己长大的数组。
1.2 顺序表的三个底层特征
要真正理解顺序表，抓住三个特征就够了：
- 逻辑连续：元素之间的先后关系是线性排列的，第 i 个元素有且只有一个前驱（除第一个）和一个后继（除最后一个）。
- 物理连续：所有元素存放在一块地址连续的内存中，第 i 个元素的地址可以通过
基地址 + i × 元素大小直接算出来。 - 随机访问：因为物理连续，访问任意下标的时间都是 O(1)，这是顺序表最大的底牌。
这三个特征决定了顺序表的性格：查找特别快，但插入删除要搬家。
1.3 为什么顺序表是“入门第一课”
数据结构这门课，几乎所有教材都从顺序表讲起。不是因为简单，是因为它是后面所有结构的基石：栈、队列的底层实现，哈希表的 open addressing 方案，堆排序里的数组建堆……到处都依赖“物理连续 + 随机访问”这个底层能力。
我见过太多人跳着学，上来就看 HashMap 源码、二叉树平衡旋转，结果遇到“为什么 ArrayList 扩容用位运算”、“为什么 remove 后要置空引用”这类基础问题就卡壳。顺序表这一章学透了，后面的源码阅读和算法设计会顺畅得多。
2. 自己动手实现一个 SeqList：不依赖 ArrayList 的顺序表
想真正搞懂 ArrayList，最好的方式是自己写一个。不要用 IDE 的自动补全，打开一个空白文件，从类名开始敲。写完之后你会发现，再看 Java 源码简直是“拿着参考答案做题”。
2.1 怎么选底层存储：固定数组版和可变容量版
最朴素的实现方式有两种。
方案一：构造时指定容量，满了就抛异常。这种写法简单，但是实用性很差，因为实际业务里几乎无法预测数据量的上限。很多数据结构的教材题里会这么写，因为教学场景要回避扩容逻辑。如果你只是做课设，可以这样写：
public class SeqList { private int[] data; private int size; public SeqList(int capacity) { data = new int[capacity]; size = 0; } public void add(int element) { if (size >= data.length) { throw new IllegalStateException("顺序表已满"); } data[size++] = element; } public int get(int index) { rangeCheck(index); return data[index]; } }注意这里我用的是int[]而不是Object[]，因为不涉及泛型，写起来最清爽，做实验最合适。
方案二：自动扩容版，容量不够就“搬家”。这才是 ArrayList 的真实形态。扩容时的关键是：先判断元素个数是否已经等于数组长度，如果等于，就申请一个新数组（长度通常是旧数组的 1.5 倍），用System.arraycopy把旧数据整体搬过去，再把新元素放到 size 的位置上。搬迁成本均摊下来，每次 add 的时间复杂度仍然是 O(1)。
有个细节值得注意：很多教材里的扩容是“满了才扩”，但生产级实现会在“size + 1 超出容量”时触发 grow。两者的差别在于：前者创建空表时就要指定容量，后者可以选择懒加载（先不申请底层数组，第一次 add 再分配）。ArrayList 就采用了后者，这也是它构造开销极小的原因。
2.2 扩容为什么要用 1.5 倍而不是 2 倍
这是我在讲 ArrayList 源码时一定会展开的问题。先看 JDK 里实际怎么写：
private Object[] grow(int minCapacity) { int oldCapacity = elementData.length; if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { int newCapacity = oldCapacity + (oldCapacity >> 1); ... } ... }oldCapacity >> 1就是除以 2，所以新容量是旧容量的 1.5 倍。为什么不直接翻倍？
一方面，1.5 倍能显著减少内存浪费。如果一直翻倍，一个初始容量 10 的列表，扩容到第 10 次时容量会到 10240，但实际可能只用了 1000 个，浪费了九成。1.5 倍的增长曲线更平缓，内存占用更收敛。另一方面，1.5 倍依然保证了“均摊 O(1) 插入”的数学性质，因为每次扩容增加的容量和已用容量是同阶的，搬运 n 个元素的累计成本仍然是 O(n)。翻倍不是不行，Redis 的 list 就常用翻倍策略，但 Java 选择了更省内存的方案。
这个细节，面试中考“为什么”的人是真多，但真正能说透的少。你如果能从“均摊复杂度”和“内存浪费”两个角度解释，基本就是满分回答。
2.3 元素移动的微优化：System.arraycopy 为什么比 for 循环快
中间插入或删除时，需要把后面的元素整体前移或后移。新手最容易写成：
for (int i = size; i > index; i--) { data[i] = data[i - 1]; }这写法没错，但性能差点意思。更好的方式是调用System.arraycopy：
System.arraycopy(data, index, data, index + 1, size - index);System.arraycopy是 JVM 层面的 native 方法，它不仅仅是一个“循环搬数据”的语法糖。JVM 在实现它时会尝试使用 SIMD 指令做向量化拷贝，一次搬运 8 字节甚至更多数据，同时还能配合内存屏障做一些特殊优化。相比之下，普通 for 循环每次只搬一个元素，还要受 JIT 启发式优化的不确定性影响。所以在顺序表核心操作里，凡是涉及批量移动元素的地方，都应该用System.arraycopy。
另一个细节是：删除元素后，如果不把data[size]置为 null，对象引用会一直留在数组里，导致 GC 无法回收这段内存，这在长时间运行的 Java 服务里会变成隐性内存泄漏。JDK 源码里 remove 操作的最后一步就是elementData[--size] = null，这个细节我 3.3 节还会再展开。
3. 手写 SeqList 的完整 Java 代码与踩坑记录
下面我给你一份可以拿去直接用、也可以对照着学原理的泛型版本。它实现了顺序表最核心的增删改查，并包含扩容、缩容、越界检查等逻辑。
import java.util.Arrays; import java.util.Objects; public class SeqList<T> { private static final int DEFAULT_CAPACITY = 10; private Object[] data; private int size; public SeqList() { data = new Object[DEFAULT_CAPACITY]; size = 0; } public SeqList(int initialCapacity) { if (initialCapacity < 0) { throw new IllegalArgumentException("容量不能为负数: " + initialCapacity); } data = new Object[initialCapacity]; size = 0; } public boolean add(T element) { ensureCapacity(size + 1); data[size++] = element; return true; } public void add(int index, T element) { rangeCheckForAdd(index); ensureCapacity(size + 1); System.arraycopy(data, index, data, index + 1, size - index); data[index] = element; size++; } @SuppressWarnings("unchecked") public T get(int index) { rangeCheck(index); return (T) data[index]; } public T set(int index, T element) { rangeCheck(index); T oldValue = (T) data[index]; data[index] = element; return oldValue; } @SuppressWarnings("unchecked") public T remove(int index) { rangeCheck(index); T removed = (T) data[index]; int numMoved = size - index - 1; if (numMoved > 0) { System.arraycopy(data, index + 1, data, index, numMoved); } data[--size] = null; return removed; } public int size() { return size; } public boolean isEmpty() { return size == 0; } public void clear() { Arrays.fill(data, 0, size, null); size = 0; } private void ensureCapacity(int minCapacity) { if (minCapacity > data.length) { int newCapacity = data.length + (data.length >> 1); if (newCapacity < minCapacity) { newCapacity = minCapacity; } data = Arrays.copyOf(data, newCapacity); } } private void rangeCheck(int index) { if (index < 0 || index >= size) { throw new IndexOutOfBoundsException("索引越界: " + index + ", 当前大小: " + size); } } private void rangeCheckForAdd(int index) { if (index < 0 || index > size) { throw new IndexOutOfBoundsException("索引越界: " + index + ", 当前大小: " + size); } } @Override public String toString() { StringBuilder sb = new StringBuilder("["); for (int i = 0; i < size; i++) { sb.append(data[i]); if (i != size - 1) { sb.append(", "); } } return sb.append("]").toString(); } }3.1 这段代码里最值得琢磨的三个 API 设计
等你写完上面这份代码，再看ArrayList的 API，会发现几个有意思的对应关系：
第一，ensureCapacity。这个私有方法负责扩容判断，它的核心参数是minCapacity，也就是“这次至少需要多少容量”。如果新容量算出来还不够，就得直接用minCapacity。JDK 源码里也有同样的处理流程，就是为了防止极端情况下 1.5 倍不够用。你可能会说“这怎么可能”，但如果初始容量是 0，再加 5 个元素，1.5 倍永远是 0，就必须靠 minCapacity 兜底。
第二，remove的置空操作。方法最后一行data[--size] = null是 JDK 源码的忠实还原。这一步处理的是“游离引用”问题——数组里已经没有逻辑上的元素了，但物理引用还在，如果不清掉，size缩减后这个对象就不会被当作业务数据访问，但依然被数组引用着，垃圾回收器不会回收它。在写长连接服务、消息队列消费者这类需要长时间运行的场景里，这个小细节能避免大量无用的“老年代存货”。
第三，rangeCheckForAdd和rangeCheck是两套越界检查。add 的 index 允许等于 size（追加到末尾），而 get/remove 的 index 不允许等于 size。你如果只写一个 check，加元素时就会漏掉“末尾追加”这个合法操作。这个细节，我自己第一次写的时候就没注意到，导致add(list.size(), x)直接被误判越界。
3.2 泛型擦除留下的坑：为什么强制类型转换到处都是
上面代码里有很多(T) data[index]这种强制类型转换，因为 Java 的泛型是“伪泛型”——在编译阶段全部擦除为 Object。运行时数组里存的就是 Object 引用，取出来时只能靠你手动强转。这就是为什么 JDK 的ArrayList里elementData声明成了Object[]，而不是T[]。
有的教材会写成这样：
T[] elements = (T[]) new Object[capacity];这种写法本质上是一次性的假强转，赋值时整段数组就被标记为 T[] 了，后续 get 就不用每个元素都转。但问题在于：编译器会警告“unchecked cast”，而且如果某个调用方用反射拿这个数组当 String[] 用，运行期依然会报ClassCastException。所以不要迷信这种写法，老老实实每个元素强转反而更安全。
3.3 我在手写过程中踩过的三个坑
第一次写属于自己的 SeqList 时，我踩过几个印象深刻的坑，值得拿出来分享。
坑一：扩缩容不对称。我最初只写了扩容没写缩容，结果从一个包含 100 万元素的列表里 remove 到只剩 100 个时，底层数组还占着 100 万的空间。这是典型的“内存只借不还”。不过这事不能走极端——频繁的缩容会引发频繁的数组复制，反而更伤性能。Java 的ArrayList干脆默认不缩容，除非你手动调用trimToSize()。我的建议是：业务中有批量删除后列表长期保持小规模的场景，才需要考虑缩容，否则保持原样即可。
坑二：加元素的时候先判断再扩容。我最初把ensureCapacity(size + 1)写成了先扩容再加入，结果每次 add 都触发一次Arrays.copyOf，性能惨不忍睹。正确顺序是先判断是否需要扩容，需要才扩，不需要直接写入。这个“判断先行”的习惯，对后面看HashMap的 resize 逻辑也很有帮助。
坑三：insert 中间位置时忘了从后往前搬。在add(int index, T element)里，如果写 for 循环从 index 开始往后搬，会出现“后面的旧值覆盖掉前面的新位置”的错乱结果。正确方式是先从后往前搬：System.arraycopy(data, index, data, index + 1, size - index)内部就是从源区间的头部往尾部拷贝，天然规避了这个问题。这也是直接调用arraycopy的好处之一。
4. ArrayList 源码级拆解：JDK 对顺序表的官方实现
看完自己写的版本，再看 JDK 的ArrayList，会感觉一切都很亲切。但源码里还有一些“教科书不写”的细节。
4.1 构造函数：你都以为 new ArrayList() 创建了一个空数组，其实不是
new ArrayList<>()真的会分配Object[0]吗？不是。JDK 8 的源码里，无参构造会给你一个共享的空数组常量DEFAULTCAPACITY_EMPTY_ELEMENTDATA，这个数组长度为 0，但在第一次 add 时会扩容到默认容量 10。这个“懒加载”设计是故意的，它在大多数场景下避免了无谓的数组分配。
看一下无参构造的关键源码：
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }这样设计的好处是：你 new 一个 ArrayList 但始终没有添加元素，或者只添加几个元素就结束了，它就不会为“可能需要的容量”提前掏内存。而如果你构造时明确给了初始容量，比如new ArrayList<>(1000)，它才会立刻分配一个长度为 1000 的 Object 数组。
4.2 grow() 方法：位运算扩容和 modCount 的用途
JDK 里扩容的入口是grow(int minCapacity)，前面提过它的核心逻辑是oldCapacity + (oldCapacity >> 1)。我补充一个细节：为什么 JDK 偏爱位运算？
因为>>移位比/除法更快。虽然现代 JIT 会在热点代码里自动把除以 2 优化成右移，但在源码层面写>> 1可以让意图更明确，也避免一些旧 JVM 上的性能差异。你不需要在业务代码里到处用位运算，但读源码时要知道这些写法背后的原因。
另外，所有结构性修改方法（add、remove、clear）都会modCount++，这个字段用于快速失败（fail-fast）机制：当某个迭代器正在遍历时，如果集合结构被意外修改，modCount变了，下次next()调用就会直接抛ConcurrentModificationException。这个设计不是防止并发写，而是提醒你“别再用了，数据已经和你预期的不一致了”。这也是foreach循环里调用list.remove()会炸的原因。
4.3 get/add/remove 的时间复杂度为什么和教科书一致，但实际体验不同
教科书写着：随机访问 O(1)，尾部插入均摊 O(1)，中间插入 O(n)。这个严谨，但有个前提——你操作的是 ArrayList。真实应用里的“原因差异”主要体现在几个方面：
- 随机访问确实是 O(1)，但它还涉及一次数组边界检查和一次引用读取，现代 CPU 上这个操作会有缓存命中加持，所以 get 极快。
- 尾部 add是均摊 O(1)，但每次扩容都伴随着一次 O(n) 的数组复制，所以在批量写入大数据时，你能感受到突发的卡顿。想平滑这种卡顿，预分配容量是关键：
ArrayList<Integer> list = new ArrayList<>(预估大小)。 - remove(0)是 O(n)，因为它要把后面所有元素前移。如果你经常要删第一个元素，ArrayList 不合适，
LinkedList或者ArrayDeque才是好选择。
很多网帖喜欢说“LinkedList 插入删除比 ArrayList 快”，这是典型的以偏概全。实际做基准测试你会发现，在随机位置插入时，ArrayList 的System.arraycopy是一个非常快的内存拷贝，而 LinkedList 需要逐个节点遍历找到插入位置，这部分 O(n) 的开销并不比 ArrayList 的“搬家”小多少。数据量大、插入点靠前时，LinkedList 未必赢，甚至更慢。真正的银弹是：频繁随机插入请用CopyOnWriteArrayList（适合读多写少并发）或跳到ArrayList以外去找新结构，而不是在两者之间硬选。
5. 顺序表的性能边界：能打的地方在哪，别硬刚的地方有哪些
给顺序表做性能画像，比背“O(1)/O(n)”这种结论更有用。你要搞清楚它适合什么场景、不适合什么场景，才能在项目里做正确的结构选型。
5.1 随机访问和缓存命中：为什么顺序表遍历比链表快
顺序表遍历比链表快，不是玄学，是 CPU 缓存带来的硬件红利。CPU 读取内存时，不是一次只取一个元素，而是按“缓存行”一次性取 64 字节左右。数组里相邻元素在物理地址上连续，所以你遍历数组时，第一次读arr[0]时其实已经把arr[0]..arr[15]（假设每个元素 4 字节）都装入缓存了，后面连续读取几乎不触碰内存。链表的节点分散在堆的不同地址上，每次读下一个节点都可能缓存未命中，触发一次内存访问。
这个区别在数据量小的时候不明显，数据量达到百万级、千万级后，遍历顺序表的速度通常是链表的 3 到 5 倍。这也是为什么 Java 里很多“内存数据库”和搜索引擎的倒排索引底层用数组实现——不是图省事，是图缓存命中。
5.2 插入删除的“搬家成本”到底有多高
顺序表的中间插入删除，成本是 O(n)，但 n 的具体含义是“要搬动的元素个数”，不是整个列表长度。你在末尾插入，n=0，成本是 O(1)；你在头部插入，n=size，成本是 O(size)。所以业务上有个很实用的建议：如果你经常需要在列表头部操作，把 ArrayList 倒过来用——用add(0, e)不如反过来存，或者直接用ArrayDeque。
还有一个工程小技巧：大批量插入时，与其用循环list.add(i, element)，不如一次性构建好一个临时数组，再用System.arraycopy批量搬移。比如要把一个子列表插到主列表中间，先算好目标下标，一次性arraycopy比逐次调用 add 减少好多次整段搬移。
5.3 和 LinkedList 对比的实测倾向
网上随手能搜到很多 LinkedList vs ArrayList 的测试报告，但很多测试设计有漏洞（没有预热、没有控制 GC、没区分操作类型）。根据我的实测经验，简单概括一下不同操作的倾向：
| 操作 | ArrayList | LinkedList | 结论 |
|---|---|---|---|
| 末尾追加 | 快 | 快 | 差不多，ArrayList 略优 |
| 按下标随机访问 | O(1) | O(n) | ArrayList 完胜 |
| 按对象查找 | O(n) | O(n) | 差不多，ArrayList 因缓存更优 |
| 头部插入 | O(n)（整段搬家） | O(1)（改指针） | LinkedList 胜 |
| 中间插入 | O(n)（连续内存拷贝） | O(n)（指针定位） | 实际接近，ArrayList 往往更快 |
| 内存占用 | 有预留容量浪费 | 每个节点多 16~24 字节指针 | 数据量小时都还好，量大时 LinkedList 明显更费 |
所以，不要被“链表插入快”这个结论洗脑。真正让 LinkedList 受益的场景非常窄：要么头部高频插入删除，要么你手里已经有 Node 引用可以直接做节点级操作（但 Java 官方 LinkedList 压根没暴露这种能力）。大多数 CRUD 业务里，ArrayList 就是综合最优解。
6. 面试、复习和考试里的高频考点：这些坑别等踩了再学
顺序表是面试和笔试的“老熟人”，很多题目看起来简单，但答好的人不多。这一节我把高频考点整理一下，顺带给出答题思路。
6.1 顺序表和链表的对比，背下来不如理解
这是数据结构课和校招面试都必考的对比题。我建议你不仅仅背表格，还要能说出“为什么”：
- 存储密度：顺序表每个元素只存数据本身；链表每个节点还要存指针，紧凑度更高。
- 空间利用率：顺序表有预分配机制，可能浪费一部分容量；链表按需分配，但每个节点有指针开销。
- 访问效率：顺序表随机访问 O(1)；链表只能顺序访问 O(n)。
- 插入删除：顺序表要搬移大量元素，链表只需要改指针。但落实到工程实现里，顺序表的搬移是内存拷贝，链表的“改指针”要先遍历定位，前者未必慢。
- CPU 缓存：顺序表连续存储，缓存友好；链表随机散落，缓存不友好。
- 扩容：顺序表需要扩容搬移；链表天生支持动态增长，但这会带来频繁的内存分配。
面试官如果追问“什么时候用哪个”，你可以给出有层次的回答：读多写少、需要随机访问、追求缓存性能，用顺序表；频繁在头部插入删除、不在乎内存碎片、数据总量不可预知且节点结构复杂，可以考虑链表。如果还在用 Java 开发，除非你明确需要按节点增删，否则优先想到 ArrayList 都不会太离谱。
6.2 ArrayList 相关的高频判断题
我不给你一长串选择题，只说几个最容易让人翻车的点：
第一个坑：Arrays.asList()返回的是不可变长度列表吗？它返回的是固定大小的Arrays$ArrayList，不能 add 也不能 remove，但可以 set。很多人以为它和普通 ArrayList 一样，结果 add 的时候直接抛 UnsupportedOperationException，然后一脸懵。你要是想得到一个真正的 ArrayList，得new ArrayList<>(Arrays.asList(...))包一层。
第二个坑：ArrayList.subList()返回的是视图，不是副本。你对 subList 做结构性修改（比如 add），会直接改到原列表，并且原列表的 modCount 会变。如果你后续又去操作原列表，可能触发 ConcurrentModificationException。这是典型的“视图 vs 副本”混淆，很多工作两三年的开发也踩过。
第三个坑：用 foreach 循环删除元素。for (Integer x : list) { if (x == 3) list.remove(x); }这段代码会抛 ConcurrentModificationException，因为迭代器检测到 modCount 变化。正确的删除方式是用Iterator.remove()，或者从后往前用下标删。
第四个坑：new ArrayList<>(100)并不是直接分配 100 个元素的数组。它只是把初始容量设置为 100，size 仍然是 0。所以list.size()还是 0，list.isEmpty()是 true。初学者经常把这个和“创建包含 100 个默认值的列表”搞混。想创建包含 null 的列表，得用循环 add。
6.3 一点学习建议和一个扩展话题
如果只是为了应付考试，顺序表这一章做题就够了。但如果你想把顺序表的价值发挥到最大，我建议你做两件事：第一，对着 JDK 源码，自己把ArrayList的核心方法用自己的话讲一遍，讲不出来就回去看；第二，把顺序表作为“垫脚石”，去理解更复杂的数据结构——比如ArrayDeque怎么用循环数组实现双端队列，HashMap为什么在冲突少的时候用链表转红黑树（TREEIFY_THRESHOLD = 8），以及ArrayList的“连续内存 + 随机访问”在 JVM 内的对象布局里是怎么体现的。
扩展阅读的方向还可以是：C 语言里顺序表的实现（用结构体 +realloc）、C++ 里std::vector的扩容策略、Python 里 list 的“预分配 4 元素起步”策略。你会发现各个语言底层的顺序表实现大同小异，核心都是“连续内存 + 动态扩容 + 随机访问”。这种跨语言对比会帮助你建立真正的数据结构直觉。
最后说一点个人体会。我见过太多人用 ArrayList 用得熟，却写不出一个手写顺序表。原因很简单：用别人的封装太顺手，自己没拆过轮子。但真正到了性能排查、内存调优、设计中间件 API 的时候，你对底层数据结构理解有多深，决定了你能走多远。顺序表这一课，值得从头到尾亲手重写一遍，而且别用 IDE 的自动补全。
