如果你在大学修过《数据结构》这门课或者正在准备考研、期末复习又或者才学Java没多久就撞上了ArrayList那么这篇内容你大概率能看下去。顺序表SeqList几乎是所有《数据结构》教材第一个认真讲透的线性结构而 Java 里天天用的ArrayList就是它在 JDK 里的工业级实现。很多人把这两件事分开学结果就是笔试会画扩容流程真到项目里却不知道ArrayList底层在干什么遇到并发修改异常还一脸懵。这篇文章我把它们放在一起揉碎了讲从手写一个迷你顺序表开始一路扒到ArrayList源码再聊性能、避坑和算法题套路希望能帮你把这块地基彻底打牢。1. 为什么几乎所有教材都把顺序表放在线性结构第一课1.1 数组的“不够用”和链表的“过拟合”先看最原始的数组。C 语言里你写int arr[100];Java 里写new int[100];一旦确定长度就改不了了。真实业务里大多数数据量是逐渐长起来的日志一批批进来、配置文件一行行读、用户操作一条条记录你根本不知道上限在哪。开小了频繁溢出开大了白白占着一大块连续内存。这就是静态数组的尴尬。链表能动态伸缩每个节点现用现分配听着很完美。但它的代价一样很实在想取第 50 个元素你必须从head节点一个个往后走O(n) 的时间跑不掉每个节点除了数据还得存一个指针内存开销凭空多出 8 字节JVM 里引用还要看压缩指针情况节点在内存里东一个西一个遍历的时候 CPU 缓存基本派不上用场数据量大时性能肉眼可见地拉胯。顺序表就是在这两者之间找了个平衡点。它用一块连续内存存储元素再配一个“当前用了多少个”的计数器。找第 i 个元素直接按地址算首地址 i * 元素大小这就是 O(1) 随机访问尾部追加在容量够的时候也是 O(1)。中间插入确实要挪数据但底层可以用memcpy/System.arraycopy这种高度优化的批量拷贝去扛效率并不差。用生活类比就是数组像一根固定长度的书架链表像每个同学把书放在自己家、再给你一张地址清单而顺序表是图书馆里那一排排连续编号的书架——既能按编号秒找也能动态扩建新书架。1.2 所谓顺序表就是“数组 一个计数器”对新手来说直接把顺序表理解成“数组 size”就够了。但严谨一点讲一个完整的动态顺序表需要管四样东西真正存放元素的数组引用、当前有效元素个数、当前容量、扩容规则。逻辑上元素是线性排布的物理上它们也存在连续地址里下标既是逻辑位置也是物理偏移这两者的统一正是顺序表好用的根源。这里还得分清静态顺序表和动态顺序表。教科书上 C 语言版的顺序表很多是定长的结构体数组容量写死而带扩容能力的版本才是工程里真正在用的。Java 的ArrayList就是动态顺序表的典型代表。理解这一点很重要以后你看 Python 的 list、C 的 vector会发现它们全是同一套思路换个语言换个名字而已。数据结构真正值钱的不是背代码而是这套底层模型。2. 手写一个顺序表从零实现的过程与关键决策2.1 先定骨架容量、大小、存储数组源码这东西自己写一遍胜过读十遍。我们来实现一个简化版MyArrayList核心字段就三个public class MyArrayListE { private Object[] elementData; private int size; public MyArrayList() { // 先给一个很小的初始容量避免一上来就浪费内存 elementData new Object[10]; } public MyArrayList(int initialCapacity) { if (initialCapacity 0) { throw new IllegalArgumentException(容量不合法: initialCapacity); } elementData new Object[initialCapacity]; } public int size() { return size; } public boolean isEmpty() { return size 0; } }我故意先用Object[]而不是E[]因为 Java 泛型在运行时会被擦除直接new E[10]会编译报错。等取元素时再做强转(E) elementData[index]。这个细节几乎每个手写容器都会遇到先有个印象后面看ArrayList源码它也是这么干的。动手写的时候最容易忽略的是“容量和大小是两回事”。size是逻辑上有效的元素个数elementData.length是物理容量。面试里常问的“ArrayList 初始容量是多少”很多人张口就答 10——其实 JDK 是懒加载的真正 new 出 10 容量是在第一次 add 时这个后面细说。2.2 扩容为什么按1.5倍走而不是固定加10接下来是动态顺序表的核心动作扩容。当size elementData.length时再追加元素就必须换一个更大的数组然后把旧数据搬到新家。新数组多大两种思路最常见一种是固定加 N比如每次加 10 个一种是按比例扩容比如 1.5 倍、2 倍。固定加 N 的问题在于一旦数据量大扩容次数太多每次都要全量复制旧数据总代价是 O(n²) 级别。按比例扩容总复制次数会收敛到 O(n) 级别均摊到每次 add 上就是 O(1)。这就是为什么工程实现清一色选比例扩容。那为什么选 1.5 倍而不是 2 倍2 倍扩容的实现是newCapacity oldCapacity 1简单粗暴但 1.5 倍更省内存。举例从 10 开始2 倍策略是 10 → 20 → 40 → 80你每次扩容后都浪费掉将近一倍的空间1.5 倍是 10 → 15 → 22 → 33增长平缓得多。JDK 选 1.5 倍本质是在“扩容次数”和“空间浪费”之间取了个均衡点。我自己写代码时也踩过这个坑早期工具类里图省事用 2 倍扩容跑一个百万级数据的批处理内存占用直接多出小两百兆换成 1.5 倍后明显好转。private void grow(int minCapacity) { int oldCapacity elementData.length; int newCapacity oldCapacity (oldCapacity 1); // 相当于 oldCapacity * 1.5 if (newCapacity minCapacity) { newCapacity minCapacity; } elementData Arrays.copyOf(elementData, newCapacity); }注意我这里的oldCapacity 1就是除以 2所以oldCapacity (oldCapacity 1)就是 1.5 倍比写* 3 / 2更符合位运算习惯JDK 源码也是这么写的。2.3 增删查改的实现细节与边界检查顺序表的增删查改表面简单真正写对细节的人不多。看核心的 add 和 removepublic void add(int index, E element) { if (index 0 || index size) { throw new IndexOutOfBoundsException(index: index , size: size); } ensureCapacity(size 1); // 把 index 及其后面的元素整体右移一位 System.arraycopy(elementData, index, elementData, index 1, size - index); elementData[index] element; size; } public E remove(int index) { if (index 0 || index size) { throw new IndexOutOfBoundsException(index: index , size: size); } E oldValue (E) elementData[index]; int numMoved size - index - 1; if (numMoved 0) { System.arraycopy(elementData, index 1, elementData, index, numMoved); } elementData[--size] null; // 让 GC 可以回收避免对象滞留 return oldValue; }三个细节值得说。第一add允许index size因为那属于尾部追加不允许index sizeremove则必须index size删不存在的空位是非法操作。第二System.arraycopy是 Native 方法JVM 层面会对它做优化很多场景下比手写 for 循环快得多这也是为什么顺序表中间插入虽然理论 O(n)但实际常数很小。第三remove 之后把末尾置 null这一步叫“防止对象游离”不然数组里还剩着指向已删除对象的引用GC 没法回收它大量删除场景下会引发内存泄漏。查和改相对简单get(index)和set(index, element)都要先检查边界然后直接操作数组下标。contains则要遍历数组用equals判断所以如果你往 ArrayList 里放的是自定义对象记得重写equals否则比较的是引用地址而不是业务内容。这个坑我在后文还会提。3. 扒开 ArrayList 源码看工业级实现3.1 懒加载为什么无参构造没有直接new一个length10的数组很多人以为new ArrayList()当场就分配了一个容量 10 的数组。看过源码后你就会发现无参构造只做了一件事this.elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATA;也就是把 elementData 指向一个共享的空数组。真正的做法是第一次调用add时ensureCapacityInternal才会去计算最小容量发现 elementData 还是那个空数组就取max(DEFAULT_CAPACITY, minCapacity)也就是至少 10这才真正 new 出容量 10 的数组。这个设计的意图很简单省内存。你如果只是new ArrayList()而不往里加任何东西就不应该占用任何数组空间。JVM 里每个数组对象都有对象头开销容量再小也占内存能省则省。我第一次看这段源码时有被这种“斤斤计较”震撼到工业级代码连一个只声明不使用的对象都要优化到位。这也提醒我们写工具类时要考虑真实使用场景而不是机械地初始化。3.2 扩容逻辑逐段拆解grow和hugeCapacity我们直接看 JDK 17 里ArrayList.grow的相关代码private Object[] grow(int minCapacity) { int oldCapacity elementData.length; if (oldCapacity 0 || elementData ! DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { int newCapacity ArraysSupport.newLength(oldCapacity, minCapacity - oldCapacity, oldCapacity 1); return elementData Arrays.copyOf(elementData, newCapacity); } else { return elementData new Object[Math.max(DEFAULT_CAPACITY, minCapacity)]; } }ArraysSupport.newLength做的事就是新容量 旧容量 max(增量, 旧容量/2)也就是至少 1.5 倍同时不小于你实际需要的minCapacity。还有一个上限判断if (newCapacity MAX_ARRAY_SIZE) { // 如果连 Integer.MAX_VALUE - 8 都不够就尝试 Integer.MAX_VALUE newCapacity hugeCapacity(minCapacity); }MAX_ARRAY_SIZE Integer.MAX_VALUE - 8留 8 个字节是为了给数组对象头和一些 JVM 元数据腾位置。超过这个值之后能不能继续扩容取决于 JVM 实现和物理内存真到这一步基本离 OutOfMemoryError 不远了。这个 1.5 倍 最大容量限制的组合是 JDK 开发者反复权衡后的结果。我们在自己设计容器时也应该抄这个套路扩容不能无限涨必须设上限否则恶意输入能把内存直接打爆。3.3 fail-fastmodCount在防什么foreach里remove为什么会炸ArrayList里有一个transient int modCount字段它记录的是“结构性修改”的次数。什么叫结构性修改改变列表大小的操作都算比如add、remove、clear而set只是替换已有元素的值不改变大小所以不算。迭代器内部会保存一个expectedModCount初始值和modCount相等。每次调用next()或remove()时迭代器都会检查modCount ! expectedModCount一旦不等立刻抛出ConcurrentModificationException。这个机制叫 fail-fast用意是既然列表结构已经被外部改动了迭代器内部的状态可能已经错乱与其继续瞎跑给出错误结果不如直接失败。很多新手在foreach循环里写了list.remove(item)然后一脸懵地看着程序抛异常。原因就是foreach底层的迭代器感知到了这个修改。正确的做法是用迭代器自己的remove()方法IteratorString it list.iterator(); while (it.hasNext()) { String s it.next(); if (需要删除的条件) { it.remove(); // 迭代器内部会同步 expectedModCount } }这里要再往下挖一层为什么迭代器的remove()就合法因为它不仅会调ArrayList.this.remove(lastRet)去删元素还会把expectedModCount同步成新的modCount。也就是说它一边改结构、一边更新自己的预期值自然就不会误报了。这个设计思路在各类 Java 集合里都通用理解了它后面看HashMap的迭代器也会轻松很多。3.4 容易翻车的subList和toArray先说subList。list.subList(from, to)返回的并不是一个独立的新列表而是原列表的一个视图。它内部持有原 ArrayList 的引用对子列表的结构性修改add、remove会直接反映到原列表上同时原列表的modCount也会变化。更坑的是如果你先拿到 subList再去修改原列表那么之后任何对 subList 的操作都可能因为 modCount 不一致抛出ConcurrentModificationException。ListString list new ArrayList(List.of(A, B, C)); ListString sub list.subList(0, 2); list.add(D); // 修改了原列表 sub.size(); // 这里可能抛 ConcurrentModificationException我实际项目里就遇到过这种 bug一个工具方法内部用 subList 截取数据做批量删除传入的 list 在外面又被其他地方同时 add 了元素结果方法执行到一半炸了。最后改成让调用方保证期间不改原列表或者直接复制一份子列表new ArrayList(list.subList(...))才消停。再看toArray。list.toArray()返回的是Object[]你不能强转成String[]会抛ClassCastException。正确姿势是传入一个类型数组list.toArray(new String[0])。JDK 源码里对传入数组长度为 0 的情况有专门优化会直接以调用方传入类型 new 一个数组并拷贝所以写new String[0]比new String[list.size()]在某些版本更快这也是个反常识的优化点。4. 性能画像什么时候该用ArrayList4.1 复杂度结论背后的原因表格是死的背后的原因才是活的。我把核心操作列在下面但更重要的是理解每一行是怎么来的。操作ArrayListLinkedListget(i) 随机访问O(1)O(n)add(e) 尾部追加均摊 O(1)O(1)add(0, e) 头部插入O(n)O(1)add(i, e) 中间插入O(n)O(n)先走到 i 再插入remove(i)O(n)O(n)同样要找到 i遍历全部元素O(n)缓存友好O(n)缓存不友好ArrayList的随机访问是真正的“算地址直接取”因为底层是连续数组一次内存寻址就能拿到元素。LinkedList的get(i)要么从头往后数、要么从尾往前数找 5000 号元素就是 5000 次指针跳转。而LinkedList的头插 O(1) 是因为它有first和last两个哨兵节点头部插入只改引用即可。但注意它的中间插入并没有想象中那么快先得从 head 或 tail 走到目标位置这一步已经是 O(n)所以“LinkedList 插入快”是有条件的。还有一个常被忽略的点顺序表遍历非常吃 CPU 缓存。数组元素在内存里一个挨一个加载一个缓存行就能顺便加载后面好几个元素链表节点零散分布每次跳转都可能触发一次缓存未命中。所以即使两者都是 O(n) 的遍历实际跑起来ArrayList往往能快一个数量级。4.2 ArrayList和LinkedList的选型之争网上经常有人争论两者谁更好。我的结论很简单没有特殊理由就选ArrayList。这不是情怀而是实测结果。社交软件消息列表、日志存储、排行榜快照、配置项读取绝大多数场景都是“写一次、读很多次”顺序表的局部性优势体现得淋漓尽致。就算偶尔需要头部插入只要数据量不超过几万ArrayList的System.arraycopy也能轻松扛住未必比 LinkedList 慢。真正该用 LinkedList 的场景很窄你确定需要大量在列表头部或任意位置增删且列表规模非常大且删除后不依赖随机访问。比如实现一个 LRU 队列雏形、维护一个频繁淘汰的缓冲区。JDK 的LinkedList还实现了Deque接口可以当双端队列用这是它的一大价值addFirst/removeLast这种双端操作都是 O(1)。所以在“需要双端操作”这一点上用 LinkedList 是名正言顺的。另外一个鲜为人知的点是ArrayList扩容到很大之后即使你把元素删掉大半底层数组也不会自动缩容。比如一个曾经塞了 1000 万元素的列表删到只剩 10 个内存里那个大数组依然被引用着。这时候如果确认不会再有大容量需求可以主动trimToSize()把容量压缩到与 size 一致释放多余内存。4.3 两个能省出肉眼可见性能的操作习惯第一个习惯是预估容量。凡是能大致估算规模的场景创建时就传初始容量ListString list new ArrayList(10000);这省掉的不是一次两次复制而是整条扩容链。从 10 涨到 100001.5 倍策略要扩容十几次每次都会触达数组拷贝。数据量大时这个差距可能从“秒级”变成“毫秒级”。批量添加时也是同理addAll之前如果能知道对方列表大小ArrayList源码里会直接按size 对方size扩容避免多次中间扩容。第二个习惯是避免在循环里做频繁的remove(0)或contains。remove(0)每次都要把后面所有元素往前挪循环 n 次就是 O(n²)。处理批量删除时优先考虑倒序遍历删除或者用removeIflist.removeIf(item - 应该删除的条件);removeIf在 JDK 8 的实现里是边遍历边把要保留的元素往前压缩最后一次性清掉尾部整体只需要 O(n)。我接手过一个老系统原本用 for 循环逐个 remove几百万数据跑了十几秒换成 removeIf 后不到一秒钟这就是“常数优化”变“复杂度优化”的实例。5. 真实项目中踩过的坑与排查记录5.1 并发修改的两种表现和正确姿势除了 foreach 里 remove 会抛异常还有一种隐蔽场景多个线程同时操作同一个 ArrayList。一个线程在读另一个线程在 add前者可能抛出ConcurrentModificationException也可能读到半个列表——因为 ArrayList 的size字段不是线程安全的一个线程改了size另一个线程可能看到不一致的值甚至数组越界。这种问题排查起来最恶心因为它是间歇性的跟线程调度时机强相关。我见过一个线上服务每天固定报一次ArrayIndexOutOfBoundsException日志里却没有对应的业务上下文最后定位到是某个全局缓存列表被后台定时任务和请求线程并发读写。解决方案并不是把读的地方加锁就完事而是要看整体数据流。如果容器本身允许副本替换最快的方案是频繁读、偶尔写时直接换引用。写时构造一个新 ArrayList读时不加锁访问旧引用。如果写频繁就得上同步手段。这个坑的关键是先判断你的数据是“读多写少”还是“写多读少”再选容器。5.2 线程安全ArrayList不是线程安全的代名词这里要澄清一个常见误解线程安全的“官方替代”不是Vector。Vector确实每个方法都加了synchronized但它是方法级锁粒度过粗多线程竞争激烈时性能很差且迭代仍然不是线程安全的。更关键的是Vector是 JDK 1.0 时代的遗留类官方注释都不建议新代码使用。真正要根据场景选只有当列表很小、操作很快时Collections.synchronizedList(new ArrayList())才够用它把每个方法都包裹了一层同步。读多写少的场景CopyOnWriteArrayList非常合适。它每次写操作都会复制整个底层数组读操作完全不加锁。代价是写开销大不适合频繁写。适合注册中心列表、白名单、配置快照这类“低频更新、高频查询”的数据。有复杂复合操作先判断再插入、批量删除时任何单方法同步都不够必须自己在外层加锁或改用其他并发容器。我之前做一个广告投放系统的黑白名单模块更新的频率大概每分钟几次查询频率是每秒几万次用的就是CopyOnWriteArrayList。上线后 QPS 轻松跑满写更新的延迟也完全可接受。选型选对代码都好写很多。5.3 元素移位、null值和equals带来的隐性Bug顺序表最容易被忽略的是“删除是物理移位”。你 remove 掉 index 1 的元素index 2 的元素会补到 index 1。如果你一边用原始索引一边删很容易跳过元素。比如for (int i 0; i list.size(); i) { if (满足条件) list.remove(i); }删掉当前位置后后面的元素全部往前挪了i 自增后会直接跳过原来紧挨着的新元素。不少“为什么删不干净”的 bug 就是这么来的。正确做法要么倒着删要么用迭代器。ArrayList允许存 null这本身没什么问题但如果你用remove(null)去删它会匹配到第一个 null 并删除只删一个不是全部。如果业务里 null 值得被当作非法数据在源头就该过滤掉而不是等进了列表再跟它纠缠。还有equals的坑。contains、indexOf、remove(Object)这三个方法内部的判断心里全是equals。自定义实体类不重写equals/hashCode时比较的是引用哪怕两个对象字段完全一样也会判为不相等。我见过初学者往 List 里存了一堆用户对象然后用一个字段相同、引用不同的对象去 remove结果删不掉。重写 equals 时顺手把 hashCode 一起重写了这是 Java 基本功但很多人栽在这里。另外一个容易忽略的点是ArrayList的subList修改会反映到原列表但它对子列表做add/remove时原列表的modCount也会变。这个我前面已经讲过实战中它造成的 bug 往往是“偶发、不确定、不好复现”排查成本极高。6. 从顺序表走向算法题与应试实战6.1 三个高频数组题的解法模板面试和笔试里顺序表最常考的其实是数组题核心套路不外乎双指针和临时数组。我整理三个出现频率极高的题目代码可以直接背下来再理解。第一个是合并两个有序数组这也是“顺序表并集”问题的底层操作public static int[] merge(int[] a, int[] b) { int[] c new int[a.length b.length]; int i 0, j 0, k 0; while (i a.length j b.length) { c[k] a[i] b[j] ? a[i] : b[j]; } while (i a.length) c[k] a[i]; while (j b.length) c[k] b[j]; return c; }核心思想是两个指针各自扫描谁小谁进结果数组剩下的直接补尾。合并完如果再去重就得到两个集合的并集如果要求元素不重复只需在合并时额外判断c[k - 1] 当前值就跳过。这道题的价值在于它把“顺序表有序性”和“双指针归并”两个核心点串了起来。第二个是删除有序数组中的重复项原地操作public static int removeDuplicates(int[] nums) { int slow 0; for (int fast 1; fast nums.length; fast) { if (nums[fast] ! nums[slow]) { nums[slow] nums[fast]; } } return slow 1; }快指针负责扫描慢指针负责标记“已去过重的最后一个位置”。所有元素只扫描一遍空间 O(1)。这种快慢指针写法在考研 408 的算法题里很讨喜因为阅卷看重“时间 O(n)、空间 O(1)”的设计思路。第三个是任意位置插入元素的手写实现讲究的是“从后往前搬移避免覆盖”public static void insert(int[] arr, int size, int index, int value) { if (size arr.length || index 0 || index size) return; for (int i size; i index; i--) { arr[i] arr[i - 1]; } arr[index] value; }代码不难但画内存图才能真懂先把最后一个元素往后挪再倒数第二个依此类推最后空出的位置正好是 index。考试时这么写逻辑直观且不易出错。6.2 从顺序表衍生出的结构栈、队列、循环队列顺序表不只是线性表本身它还是一大批数据结构的“地基”。用 ArrayList 当栈用只需要add和remove(size - 1)尾部就是栈顶用头插尾部删又能实现一个队列雏形只不过中间插入效率差。真正复杂的衍生是循环队列用数组 head 和 tail 两个游标解决顺序队列“假溢出”问题。假溢出的意思是数组前面还有空位但 tail 已经走到末尾正常判断会让队列看起来满了。循环队列通过取模运算绕回去(tail 1) % capacity这是数组类结构里非常经典的技巧。双端队列Deque也是同样的思路两端都能进出。Java 的ArrayDeque底层就是循环数组官方推荐用它替代Stack和作为队列实现。很多热词里提到“数据结构 双端队列”其实关键就是游标两端移动 扩容。理解了顺序表的连续存储和扩容机制这些衍生结构的源码你都能很快看懂因为它们骨架完全一样。另外优先队列从概念上看像树但堆的实现本质也是数组父子节点下标有精确的数学关系parent (i - 1) / 2。堆排序、Dijkstra 算法里那个优先队列底层全是数组无一例外。所以说顺序表不只是线性表的地基还是很多非线性结构的物理载体这点值得反复强调。6.3 给准备考研、期末和面试的人一点复习路径建议如果你在准备 408 考研或期末考我的建议是别光看按这个顺序走一遍第一手写一个动态顺序表包括扩容和缩容逻辑把每个边界条件想清楚第二把数组题里“双指针”和“逆序移动”两类模板各刷十道形成肌肉记忆第三画一画数组在内存里的布局图搞清楚为什么随机访问是 O(1)、为什么插入删除要挪元素第四把ArrayList源码过一遍重点看grow、remove、iterator三块。这套组合下来无论笔试考代码还是面试考原理你都能稳住。很多人在线做题平台比如头歌这类实验环境上卡壳问题往往不在算法本身而是输入输出处理和边界条件判断。比如题目给了“n 个整数要求在第 k 个位置插入一个数”你至少要处理三种情况k 等于 0头插、k 等于 n尾插、k 超出范围非法。把边界列出来再写代码一次过题的概率会高很多。我个人偏好的复习资料是《大话数据结构》入门配合《数据结构与算法分析》里的“摊还分析”理论章节去理解扩容为什么均摊 O(1)。数学证明很严谨但理解后对设计容器的眼界提升巨大。考研的话《王道》的章节配套题要反复做顺序表这一章的代码题基本就是基于数组的双指针操作分值性价比很高。写到这里差不多该收尾了。我在早期带团队的时候发现一个现象很多开发写了三四年 Java天天用 ArrayList却答不清扩容倍数是多少、subList 能不能独立修改、foreach 里删除为什么会抛异常。这些东西不是“冷知识”而是真实项目里每天都在接触的行为。尤其是中间插入删除的复杂度、扩容的均摊分析、迭代器 fast-fail 的机制都属于“面试八股”但也是排查线上问题的钥匙。建议你把文中的手写版和源码对照着读一遍有条件就在 IDE 里跑一下那几个会抛异常的示例踩过一次坑比看十遍文档都管用。顺序表这块地基稳了后面学链表、栈、队列、树和图都会顺很多。