企业官网建设流程全解析

聊到数据结构，顺序表（SeqList）和 ArrayList 这对组合几乎是所有教材的起手式。很多人刚开始学的时候会想：这不就是数组吗？把代码搬出来，int[] 一套循环增删改查，好像也没啥技术含量。真等你在实际项目里处理过几万元素的列表，或者被线上 ArrayList 扩容引发的卡顿坑过一次，就会明白，顺序表不是数组的简单别名，而是用连续内存做出来的一套动态管理方案。这篇文章我想把顺序表从底层定义、手写实现，一直到 Java 的 ArrayList 源码，串起来讲清楚。准备考研 408 的读者可以当复习笔记，Java 开发可以当源码精读参考，转码新人也能从中理解为什么一个看起来最简单的容器，面试时反而能问出那么多细节。

1. 顺序表到底是什么：从一块连续内存说起

1.1 线性表与顺序存储的基本盘

线性表可以理解为 n 个同类型元素的有限序列，元素之间有“前驱—后继”关系。顺序存储就是把这一串元素按顺序放进一段地址连续的存储单元里。第 1 个放第一个位置，第 2 个紧随其后，第 i 个元素的物理地址可以直接算出来。

我习惯把它类比成“一条走廊里的连续房间”：房间号从 1 排到 n，你住 3 号房，隔壁就是 4 号房。逻辑上的前一个和后一个，在物理上必然相邻。链表不是这样，它更像是把一堆盒子用绳子串起来，盒子的实际摆放位置完全随意，每个盒子里面写着一个绳子的指向，告诉你下一个盒子在哪儿。这个差异看起来不起眼，实际上决定了随机访问的复杂度是天壤之别。

数组是编程语言提供的最基础机制，顺序表是基于数组做的一套抽象。数组一旦创建，长度固定，删掉一个元素后后面的元素不会自动往前挪；顺序表则要维护一个 size，把“有效元素个数”和“底层容量”分开管理。很多容器看着花哨，底子基本都是这么一张连续内存。理解了这张连续内存，后面再看 ArrayList、ArrayDeque 甚至 Redis 的 SDS，都会清晰很多。

1.2 随机访问为什么是 O(1)：一个公式的事

顺序表的随机访问效率来自地址计算。假设数组基地址是 base，每个元素占 ELEMENT_SIZE 个字节，那么第 index 个元素的地址就是：base + index * ELEMENT_SIZE。这个公式里没有任何循环依赖，CPU 拿到 index 直接做一次乘加就能访问内存。

所以 get(index) 是 O(1)。链表做不到这一点，因为每个节点只知道自己下一个节点的位置，想访问第 index 个节点，必须从 head 往后逐个走，平均 O(n)。这也是为什么数组天然适合“按下标取数”的场景：二分查找、排序、哈希表用数组当桶，都依赖这种瞬时定位能力。

C 语言里数组名和指针的关系就是这段公式的直接体现；Java 的 ArrayList 内部也是 Object[] elementData，get 最终就是 elementData[index]。很多人背八股文说“ArrayList get 是 O(1)”，但背不出这个公式。面试官一旦追问，靠记忆的答案很快会露馅。

1.3 连续内存的代价：插入删除为什么要搬数据

随机访问有多爽，插入和删除就有多痛。想在 index 位置插入一个元素，必须先把 index 从当前位置到末尾的所有元素整体向后挪一位，腾出一个空位，再把新元素放进去。删除正好相反，要把后面的元素整体往前挪一位，把空位填上。

平均情况下，往一个长度为 n 的顺序表里随机位置插一次，要移动 n/2 个元素；在头部插入时，最坏要移动 n 个元素。数据量一上来，一次无脑的 add(0, e) 可能比链表的 add 慢几个数量级。这就是“连续内存”的隐喻：一排书架中间塞书，后面的书全得挪，塞的位置越靠前，挪的书越多。

所以顺序表的适用场景很明确：读多写少、按下标访问多、尾部追加多。如果业务里全是中间插入、头部删除，单纯用顺序表并不合适。不过工程里的选择更复杂，因为数组还有缓存局部性优势，真到几万甚至几十万数据时，ArrayList 未必比 LinkedList 差，这一点后面源码部分再展开。

2. 手写一个顺序表：核心操作的实现细节

2.1 结构定义与初始化：容量和它为什么不是 size

如果要把顺序表封成一个通用容器，第一个问题是底层数组用什么类型。Java 泛型擦除后，运行时数组的真实类型只能是 Object[]，我们通过强转把元素转成 E。所以大部分手写代码会把成员变量声明成 Object[]，而不是 E[]。

public class MySeqList<E> { private Object[] data; private int size; private static final int DEFAULT_CAPACITY = 10; public MySeqList() { this(DEFAULT_CAPACITY); } public MySeqList(int initialCapacity) { if (initialCapacity < 0) { throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity); } data = new Object[initialCapacity]; size = 0; } }

这里最容易迷糊的是 capacity 和 size 的区别。capacity 是 data.length，表示“底层数组最多能装多少元素”；size 是“当前真正存了几个元素”。ArrayList 对外只有 size()，capacity 不暴露，但内部扩容时用的就是这两个值的关系。很多新手写顺序表，size 当 length 用，数组长度当有效个数用，边界判断必然出错。

初始容量定多少没有标准答案。ArrayList 默认 10，C++ vector 默认 0，之后按需分配。定小一点省空数组占用的内存，定大一点减少后续扩容次数。关键是这个初始容量要作为后续所有边界判断的起点，不要拍脑袋乱填。

2.2 扩容策略：翻倍还是 1.5 倍，均摊复杂度怎么算

当 size 等于底层数组长度时，再塞一个元素就放不下了。线性表最难的地方就在这：底层数组长度固定，但逻辑上它应该能动态增长。于是必须扩容：新开一块更大的连续内存，把旧元素全部复制过去，然后替换底层引用。

private void ensureCapacity(int minCap) { if (minCap > data.length) { int oldCap = data.length; int newCap = oldCap + (oldCap >> 1); if (newCap < minCap) { newCap = minCap; } data = Arrays.copyOf(data, newCap); } }

newCap 为什么往往是 oldCap + (oldCap >> 1)？右移一位就是把 oldCap 除以 2，所以结果是 1.5 倍。ArrayList 用的就是这套逻辑。那么为什么扩容要按倍数而不是固定步长？这关系到均摊复杂度。

假设每次扩容增加 k 个固定槽位，那么从 n 扩到 2n 需要扩容 n/k 次，每次都要把前面所有元素复制一遍，总共复制约 O(n²/k) 次，均摊到每次插入是 O(n)。这是灾难。如果每次扩成 2 倍，扩容后容量翻倍，复制总次数约为 1 + 2 + 4 + ... + n ≈ 2n，均摊到 n 次插入就是 O(1)。从 1.5 倍到 2 倍，都是几何级数，均摊都是 O(1)，区别只是空间利用和扩容频率。2 倍扩容内存利用率会更低，1.5 倍浪费更少但扩容次数稍多；Python 的列表甚至用到约 1.125 倍，更偏空间省。实际项目里不用纠结，跟着语言标准实现走就行。

2.3 插入、删除、查找的代码级拆解

插入的核心是搬移。先做范围检查，再扩容，然后把 index 到 size-1 的元素全部后移。

public void add(int index, E e) { if (index < 0 || index > size) { throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size); } ensureCapacity(size + 1); System.arraycopy(data, index, data, index + 1, size - index); data[index] = e; size++; }

注意 add 时 index 可以等于 size，表示尾部追加。System.arraycopy 是 native 方法，底层会做整块内存复制，比 for 循环逐个赋值快很多。删除的操作反过来：

public E remove(int index) { if (index < 0 || index >= size) { throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size); } E old = (E) data[index]; int numMoved = size - index - 1; if (numMoved > 0) { System.arraycopy(data, index + 1, data, index, numMoved); } data[--size] = null; return old; }

删除后最后一个槽位会残留一个引用。如果不把它置 null，从容器层面看这个元素已经被删了，但底层数组仍然强引用它，GC 就回收不了，这就是潜在的内存泄漏。JDK 源码里这一步写着 data[--size] = null，不是随便加的。查找一个元素的 indexOf 要遍历整个数组，用 equals 而不是 ==，而且要允许查 null，因为 ArrayList 本身是允许存 null 的。

2.4 手写实现中的常见 bug

自己写一遍顺序表，踩过的坑比看十遍书都深刻。我总结几个高频 bug：

一是边界检查混乱。get、set、remove 只允许 index 在 [0, size-1]，add 允许 [0, size]。把这两个集合搞反，要么尾部插入永远失败，要么越界访问到扩容后残留的旧数据。

二是扩容后忘了把新数组赋给成员变量。局部变量 newData 搬完就丢了，原数组还是原来那个，等于没扩容。这种 bug 在代码紧张时非常隐蔽，编译器也不报错。

三是删除元素后没有把尾部引用置空。短期看没事，长期跑缓存型容器时，对象越积越多，GC 压力飙升，最后可能 OOM。

四是无脑每次 +10 扩容。前面说过，固定步长扩容会让复制总次数变成 O(n²)，数据一多就卡死。写顺序表一定要用乘法扩容，1.5 倍是折中，2 倍更省扩容次数，看场景选。

手写实现的目的不是要造一个比 JDK 更完美的容器，而是强迫自己把数组的搬运逻辑、边界条件、内存释放这些细节全部过一遍。当我第一次把迷你顺序表写对，再回头看 ArrayList 源码，才发现 JDK 并不是用了什么高深魔法，只是把同样的逻辑做到了极致：能少访问字段就少访问，能一次搬移就不二次搬移，该置 null 就置 null。这种对底层细节的敏感，几乎决定了之后写中间件或者做性能优化时能走多远。

3. 从顺序表到 ArrayList：源码里的设计取舍

3.1 成员变量与懒加载机制

Java 开发几乎天天碰 ArrayList，但很多人没认真看过它的字段。核心是这几个：

transient Object[] elementData; private int size; protected transient int modCount = 0; private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; private static final Object[] EMPTY_ELEMENTDATA = {};

elementData 是真正的底层数组，size 是已存元素个数，modCount 是结构修改计数。有几个容易被忽略的点：

第一，new ArrayList<>() 时 elementData 并没有立刻指向 Object[10]，而是指向一个共享空数组 DEFAULTCAPACITY_EMPTY_ELEMENTDATA。只有在第一次 add 时，ArrayList 才会按 DEFAULT_CAPACITY = 10 扩容。这是懒加载，目的很单纯：很多 List 创建后根本不放数据，没必要为一个空数组准备 10 个槽位。

第二，new ArrayList<>(0) 指向的是 EMPTY_ELEMENTDATA，另一个空数组。它和 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 区分，是让源码知道“这是用户显式指定容量 0”还是“用户用了无参构造”，这样第一次 add 时扩容目标不一样。这种细微差别的背后，是 JDK 对内存的锱铢必较。

3.2 add 与扩容：每一步都在为性能着想

看最新的 ArrayList.add 源码，逻辑非常紧凑：

public boolean add(E e) { modCount++; add(e, elementData, size); return true; } private void add(E e, Object[] es, int s) { if (s == es.length) { es = grow(); } es[s] = e; size = s + 1; }

grow 方法里的扩容计算是int newCapacity = oldCapacity + (oldCapacity >> 1);。oldCapacity >> 1 就是 oldCapacity / 2，所以默认扩容 1.5 倍。为什么要加 minCapacity 判断？因为空数组时 oldCapacity 是 0，0 + 0 还是 0，必须取 minCapacity 兜底，否则第一次 add 根本没法分配空间。

这里还涉及 ArrayList 的两个上限：MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8，以及扩容后如果溢出 int，就要走 hugeCapacity。为什么减 8？有些 JVM 的数组对象头会占用一定空间，预留 8 个字节的余量，避免数组本身能分配但 JVM 内部放不下元信息导致 OOM。add(index, element) 和 add(e) 最大的不同是搬移。前者先确保容量，再 System.arraycopy，把后半段整体右移。ArrayList 的代码里对 elementData 做了很多细节处理，都是为了最后一次地址计算和赋值溅出的开销。

3.3 modCount 快速失败机制是怎么工作的

For-each 循环本质上是 Iterator。ArrayList 的迭代器在创建时会保存一个期望的修改计数 expectedModCount，之后每次调用 next()、remove() 都会先检查 expectedModCount 是否等于外部 modCount。只要容器发生了结构修改——add、remove、clear——modCount 就会变，迭代器下次操作立即抛 ConcurrentModificationException。

我之前在项目里做过一个蠢事：for-each 遍历一个 List，条件匹配时直接调用 list.remove(item)，跑着跑着就抛异常。原因就是这个检查。正确做法是用迭代器的 remove()，它内部会同步 expectedModCount；或者从后往前 for 循环 + remove(index)；或者直接用 JDK8 的 removeIf，ArrayList 对 removeIf 做了专门优化，用 BitSet 标记要删的下标，再一次性批量搬运，性能最好。

modCount 不是线程安全方案，Fail-Fast 只是“快速暴露错误”。多线程并发修改容器，该用 ConcurrentLinkedQueue、CopyOnWriteArrayList 或者加锁，别指望 modCount 帮业务兜底。这个机制也提醒我们：迭代过程中脑补“删一个应该没事”，最后大概率会被异常打脸。

3.4 ArrayList 与 LinkedList：哪种选择更合理

网上关于 ArrayList 和 LinkedList 的对比很多，结论也一致：多数业务场景选 ArrayList。原因有三个。

一是缓存局部性。ArrayList 的底层数组是连续内存，遍历时 CPU 缓存按缓存行预取，命中率高；LinkedList 每个 Node 散落在堆里，每跳一个节点大概率缓存未命中，实际遍历成本远高于理论 O(n)。

二是内存开销。LinkedList 每个元素除了存储业务数据，还要存 next、prev 两个指针。Java 对象还有头信息，同样一万个元素，LinkedList 占的内存明显更多。

三是操作复杂度要分“定位”和“删除/插入”。LinkedList 的 add(0, e) 确实是 O(1)，但 add(index, e) 得先从头遍历到 index，定位 O(n)，所以中位插入并没有优势。ArrayList 的 add(index, e) 虽然要搬移 O(n) 个元素，但这个 O(n) 是整块内存复制，实际速度往往不慢。

这个结论不是鼓励大家完全不用链表，而是说选型要结合元素数量、访问模式，不要因为教科书一句“链表插入 O(1)”就做出错误决定。真到了队列、栈这类只操作两端的场景，链表的优势才更明显，但更优的常客是 ArrayDeque，而不是 LinkedList。

4. 实战中的性能优化与常见误区

4.1 预估容量，少做搬迁

最容易被忽视的优化是初始化容量。假设业务要从数据库里取十万条记录装进 List，如果直接 new ArrayList<>()，默认容量 10，每次满了 1.5 倍扩容，大约要扩 20 多次。每一次扩容都要创建新数组并复制旧元素，累计复制次数大概是最终容量的两倍以上。十万条时 CPU 和 GC 都能感受到压力。

如果事先知道大概规模，直接 new ArrayList<>(100000) 或略大一点，一次分配到位，省掉所有搬迁。对 GC 也是一个好事，因为扩容产生的旧数组被丢弃后需要回收。反过来，如果猜的容量比实际大很多，也会白白占用内存，所以“预估容量”是通盘考虑，不是越大越好。JDK 集合框架里还有 ensureCapacity 这样的提示，但真正高效的是构造初期就给对。

4.2 批量操作要会用 addAll 与 removeIf

另一个常见误区是批量加元素时逐个 add。比如从另一个 Collection 里循环 list.add(x)，每 add 一次都可能触发容量检查，数据量大时扩容多次。addAll 则不同，它先看当前容量和要添加集合的 size，一次性扩到够用，再逐个写入。源码里 addAll 会调用 grow 到目标容量，这比循环 add 少了几十次数组拷贝。

批量删除同理。手动 for 循环删除，每次 remove 都会搬移后面的元素。比如删除一份十万元素列表中符合条件的五千个，如果每次删一个，每次搬移量都接近当前 size，总移动量非常可观。removeIf 的做法是先扫描一遍，标记要保留的元素位置，再一次性整体搬移，把多次 O(n) 搬移压缩成一次 O(n) 遍历加一次 O(n) 搬移。这个思路和算法题里的“双指针压缩数组”完全一致，值得记下来。

4.3 头部增删的替代方案

顺序表最大的软肋是头部操作。如果业务里有一个“最新消息放最前面，超过 1000 条删掉最旧”的需求，写成 list.add(0, msg) + list.remove(list.size()-1)，每来一条消息都会移动几千个元素，压力很大。我踩过这个坑，一个实时日志面板几千条时操作就开始卡，最后换了 ArrayDeque，只在两端操作，O(1) 完成，立竿见影。

ArrayDeque 名字里带 Deque，底层其实也是一块连续数组，但通过 head、tail 两个索引实现双端操作，循环利用空间，不会因为头插而搬移。它不允许 null，因为 null 被当作“槽位为空”的哨兵值。如果需要“可随机访问的双端结构”，Java 里没有标准现成品，一般用 ArrayList 配合反向索引实现。这个取舍本身就是教材说的：没有万金油的数据结构，只有结合场景的工程选择。

4.4 subList 视图陷阱与 Arrays.asList 的固定长度

subList 是 ArrayList 一个非常容易被误解的方法。它返回的是原 List 的一个视图，不是拷贝。对 subList 做 add、set、remove，会直接写回父列表；父列表一旦发生结构性修改，比如 add 或 remove，之后再操作 subList 就会抛 ConcurrentModificationException。这是因为 subList 内部维护了一个 parent 的 modCount，操作时会校验。

如果你只是想拿一段独立列表，务必 new ArrayList<>(list.subList(from, to))。Arrays.asList(T... a) 也有类似陷阱。它返回的是一个基于数组的固定长度 List，不能 add、remove，否则 UnsupportedOperationException。很多新手把它当普通 List 用，结果线上报错。想要可变列表，外面再包一层 new ArrayList<>(Arrays.asList(...))。这些坑不读源码几乎猜不到，但实际排查时往往就是它们。

5. 高频面试问题与避坑清单

5.1 面试官常问的 8 个问题

顺序表和 ArrayList 是面试高频区，绝大多数问题绕不开下面这些：

几乎每次面试都能从这几个问题延展开。比如讲扩容，面试官可能会追问均摊复杂度；讲 modCount，可能追问迭代器 remove 为什么安全；讲 subList，可能追问 CopyOnWriteArrayList 的弱一致性。这些追问的根源都在顺序表和 ArrayList 的设计取舍上，所以不要背答案，要把前面几部分的原理真正弄懂。面试不是为了考记忆，而是看你能不能说明白“为什么”，这也是数据结构这门课在工程上最值钱的部分。

5.2 新手的 5 个典型错误

排查过很多自写代码，最典型的五个错误其实很一致：

一是拿 int[] 当顺序表用，只维护 length，不维护 size。数组的 length 一旦创建就定死了，删掉元素后 length 不变，逻辑有效长度完全丢失。

二是正序遍历删除。for (int i = 0; i < list.size(); i++) 里删除元素后，后面元素整体前移，下一个待检查元素被跳过，结果漏删。正确做法是倒序遍历，或者用迭代器，但很多人图省事直接 i--，很容易绕晕。

三是直接用 == 比较字符串。int 类型没问题，String 或其他对象必须在 indexOf、contains 里用 equals。

四是删除元素后忘记把尾部槽位置 null。手写顺序表时容易犯，长期运行会让容器“幽灵引用”一堆废弃对象，GC 白打工。

五是只考虑功能不考虑扩容。大批量写入时用默认构造，内存反复搬迁，线上性能毛刺和它关系很大。这些错误单独看都很低级，但组合起来就是很多“明明逻辑对为什么这么慢”的线上事故根源。

5.3 从考研 408 到工程实践，顺序表的延伸思考

408 和期末复习里，顺序表是入门第一课，考过合并两个有序表、原地逆置、删除重复元素等。这些题目的本质都是“怎么少搬数据”。比如删除所有值为某个元素的位置，如果每删一个就搬一次，最坏 O(n²)；但用双指针把保留元素一次移动到前面，就能 O(n)。ArrayList 的 removeIf 底层优化，正是这种思想的工业实现。所以数据结构不是纸上谈兵，它直接影响批量操作效率和内存使用。

我个人这些年最大的体会是：顺序表是最简单的“动态数组”模型，但它的扩容、搬迁、视图失效、快速失败机制，几乎覆盖了后来所有复杂容器会遇到的抽象问题。你能把顺序表讲到这个深度，再去理解 Redis 的 SDS、C++ 的 vector、Go 的 slice 都不难。这些语言里的动态数组，本质上都在做同一件事——用一块连续内存，优雅地解决“长度不固定”和“访问要快”之间的矛盾。

如果你也在手写数据结构练习，我特别建议把一个迷你顺序表完整写一遍，再把“删除重复元素”“合并两个有序表”这类题目动手实现。写完再回头读 ArrayList 源码，你会突然觉得源码没那么高不可攀，每个普通方法背后的边界判断，都是前人踩坑后写下的经验。这个从“会用”到“看懂”的过程，才是学数据结构最有价值的部分。