聊到数据结构顺序表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[] elementDataget 最终就是 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 MySeqListE { 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 默认 10C 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 是 00 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 的 removeIfArrayList 对 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 是面试高频区绝大多数问题绕不开下面这些问题核心回答ArrayList 默认容量是多少无参构造时逻辑默认容量是 10但懒加载首次 add 才分配扩容一次扩多少旧容量 旧容量右移一位即 1.5 倍为什么扩容是 1.5 倍不是 2 倍几何级数保证均摊 O(1)1.5 比 2 更省空间get 为什么 O(1)连续数组直接通过基地址 index × 元素大小计算地址允许存 null 吗允许为什么 for-each 删除会抛异常Iterator 的 fail-fast 机制expectedModCount 和 modCount 不一致subList 是副本吗不是是视图父列表结构修改后 subList 失效ArrayList 线程安全吗不安全多线程需要 Vector 或 CopyOnWriteArrayList几乎每次面试都能从这几个问题延展开。比如讲扩容面试官可能会追问均摊复杂度讲 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 源码你会突然觉得源码没那么高不可攀每个普通方法背后的边界判断都是前人踩坑后写下的经验。这个从“会用”到“看懂”的过程才是学数据结构最有价值的部分。