聊到Java的List绕不开的就是ArrayList、LinkedList、Vector这三兄弟。很多同学面试前都会把“数组结构”“链表结构”“线程安全”这九个字背得滚瓜烂熟可真到了源码层面问一句“ArrayList扩容时数组是怎么搬家的”“LinkedList的get为什么慢”不少人就卡壳了。这篇文章我准备直接从JDK源码出发把三大List实现的字段设计、核心方法逻辑、迭代器机制、性能差异全部逐行拆开讲清楚读完你不仅能答上面试题更重要的是在写代码时能做出真正合理的选型。这篇剖析面向的是有一定Java基础、想真正理解集合底层的人不要求你之前读过源码跟着文章节奏走就行。我会把源码里的每一步逻辑换算成具体的运行过程配合时间复杂度和内存层面的分析让你知道每一个设计背后的为什么而不是停留在背结论的层面。1. 源码阅读前的关键视角三个类到底在解决什么问题1.1 从继承体系看设计意图先打开IDEA看一眼继承关系就能发现一个有意思的事实ArrayList和Vector都继承自AbstractList而LinkedList继承的是AbstractSequentialList。AbstractSequentialList继承的也是AbstractList但它在AbstractList的基础上针对“顺序访问”结构做了重写把get、add、remove等操作统一转成listIterator来实现这个设计其实是在告诉框架层“我是链式存储不适合随机访问”。而AbstractList本身是一个非常重要的骨架类它把迭代器的基本框架搭好了同时定义了modCount这个字段。modCount是整个集合快速失败机制的根源后文会重点讲。抽象类里凡是基于随机访问的实现比如get、set、add、remove都会调用abstract的get(int)和size()ArrayList实现了这些方法LinkedList直接用顺序迭代器曲线救国。这个区别直接决定了两者各自的操作成本模型必须放在一起对比着看。1.2 三者差异速览一张表建立直觉在深入源码之前先把结果摆出来。下面这张对比表不是让你背的是让你带着差异去源码里找证据看完所有细节后你会发现这张表里的每一条都能在源码里找到对应的代码位置。维度ArrayListLinkedListVector底层结构Object[]数组双向链表Node节点Object[]数组随机访问直接下标取元素O(1)从头或尾二分查找O(n)直接下标取元素O(1)头部插入整体右移O(n)修改头节点指针O(1)整体右移O(n)扩容机制1.5倍扩容自动搬移无需扩容节点动态创建可配置增量或2倍扩容线程安全不安全不安全方法级synchronized迭代器行为fail-fastfail-fastfail-fast这里面最容易被忽视的其实是Vector的扩容策略它和ArrayList同为数组结构但扩容的倍数规则不一样起因历史包袱比较多这在第2章源码拆解里会给你看得明明白白。读源码一定要带着这种对比意识单纯一个一个类读过去很难形成体系。2. 核心方法源码逐行拆解从字段到增删改查2.1 ArrayList动态数组的扩容与元素搬移ArrayList的源码在JDK 8之后保持了极高的稳定性核心字段只有两个Object[] elementData和int size。elementData是真正存数据的数组size是实际元素个数没有存储在数组全部位置时剩下的就是预留空间。这就是“动态数组”减掉“容量”和“大小”之间的差后剩下来的东西。看add方法public boolean add(E e) { ensureCapacityInternal(size 1); elementData[size] e; return true; }每次添加元素前会先确认容量够不够这个确认的逻辑藏在ensureCapacityInternal里它先算minCapacity然后调用calculateCapacity判断当前数组是不是空数组。如果是空数组会和默认容量DEFAULT_CAPACITY取较大值这个默认值是10。也就是说你new ArrayList()之后往里add第一个元素时数组直接是10的长度不是1这个细节就是你面试可以多说一句的地方。真正扩容发生在grow方法private void grow(int minCapacity) { int oldCapacity elementData.length; int newCapacity oldCapacity (oldCapacity 1); if (newCapacity - minCapacity 0) { newCapacity minCapacity; } if (newCapacity - MAX_ARRAY_SIZE 0) { newCapacity hugeCapacity(minCapacity); } elementData Arrays.copyOf(elementData, newCapacity); }oldCapacity 1就是除以2所以新容量是1.5倍旧容量。这里有一个需要算清楚的溢出问题如果oldCapacity非常大oldCapacity (oldCapacity 1)会溢出成负数这时候newCapacity反而小于minCapacity。JDK的源码在这里做了一层保护后面还有一个MAX_ARRAY_SIZE的限制MAX_ARRAY_SIZE是Integer.MAX_VALUE - 8。为什么要减8因为数组头信息在HotSpot虚拟机的对象内存布局里需要占用一小部分空间不同类型的数组头长度有差异减8是为了留出存储数组长度等信息的空间避免直接顶到Integer.MAX_VALUE时OOM的临界状态太危险。扩容不是每次add都会触发而是一批一批地触发摊还分析后单次add的均摊时间复杂度仍然是O(1)。老生常谈的“为什么不是2倍而是1.5倍”其实没有权威定论但从内存角度看1.5倍比2倍更平缓容量翻不上去之后被释放的旧数组更快能被GC回收频繁copy的内存消耗也会小一些。源代码里还体现了“复制”的高效实现Arrays.copyOf底层走System.arraycopy这是一种native的批量搬运方式比for循环逐位赋值快得多。这个特性在第4章性能分析时还要重点说。remove方法也是同理删除中间元素时调用System.arraycopy把所有后面的元素整体前移一位然后把尾部位置置空防止内存泄漏System.arraycopy(elementData, index1, elementData, index, numMoved); elementData[--size] null;注意这里的置null操作JDK 1.7之后才加上如果你在开发自定义数组容器这个习惯一定要学。2.2 LinkedList双向链表的节点操作与二分定位LinkedList的源码比ArrayList看起来要“啰嗦”一些因为链表的所有操作都在摆弄指针。它有一个内部类Node每个Node持有三个引用item本身、next下一个节点、prev上一个节点。LinkedList本身只维护first和last两个头尾指针外加size。add(E e)默认往尾部加调用的是linkLastvoid linkLast(E e) { final NodeE l last; final NodeE newNode new Node(l, e, null); last newNode; if (l null) first newNode; else l.next newNode; size; modCount; }这段代码的巧妙之处在于先把old last存下来再创建新节点两边连好最后判断链表是不是空的。这个顺序错一步就会出问题如果先改last再new newNodenewNode.prev就找不到原来的尾节点了。写这类链式操作核心原则是“先解锁旧关系再建立新关系”。LinkedList的get(int index)是全场操作成本最高的一个方法也是最容易被拿来当反面教材的方法NodeE node(int index) { if (index (size 1)) { NodeE x first; for (int i 0; i index; i) x x.next; return x; } else { NodeE x last; for (int i size - 1; i index; i--) x x.prev; return x; } }size 1就是size除以2。有一个很经典的优化细节定位时先判断index离头更近还是离尾更近选择从近的一端遍历。这个二分方向的优化说明JDK开发者在细节上非常舍得下功夫但它能改变的只是常数因子改变不了LinkedList随机访问O(n)的本质。源码里还藏着一个addAll把集合转成数组再批量link中间大量使用局部变量进行循环连接这些代码业务中基本用不到但刷一遍源码时值得留意。LinkedList同时实现了Deque接口所以还附带了addFirst、removeFirst等头尾操作它的头尾增删是真正的O(1)。基于这个特性LinkedList很适合做栈或者队列的底层结构性能比数组模拟要好得多。这也是你选型时最容易出彩的地方不是因为它“没用”而是因为它的适用场景特别窄。2.3 Vector全方法加锁与两种扩容策略Vector的结构和ArrayList几乎同源也用Object[]存数据用elementCount记录数量但它和ArrayList最大的不同是几乎所有公开方法都带synchronizedpublic synchronized boolean add(E e) { modCount; ensureCapacityHelper(elementCount 1); elementData[elementCount] e; return true; }也就是说每次add都要经历一次锁竞争、锁获取、锁释放的完整流程。在单线程环境下这纯粹是额外开销。多线程环境下它实际上也只是方法级同步两个线程同时读和写时并不能保证复合操作如“检查并放入”的原子性所以真到并发场景大家首选的是CopyOnWriteArrayList或者Collections.synchronizedList加锁策略而不是Vector。这恰恰是不少开发者误解最深的点。Vector扩容用的是ensureCapacityHelper逻辑如下int newCapacity oldCapacity ((capacityIncrement 0) ? capacityIncrement : oldCapacity);这里有个三目运算。构造Vector时可以传入capacityIncrement如果传了正数每次扩容就按这个增量加而不是倍数扩如果没传或者传的是0新容量就会变成旧容量的2倍。相比ArrayList的1.5倍Vector用完默认构造时是双倍扩容这种策略历史上是为了减少扩容次数但对内存不友好在旧JDK时代内存很金贵这个设计经常被拿出来吐槽。除了方法加锁Vector还保留了Enumeration的遍历接口这个在早期Java版本里是唯一的“轻量级伪迭代器”现在已经很少有人使用了。另外Stack继承了Vector但这其实是一个被广泛诟病的设计Stack本应是纯粹的栈语义结果继承了可随机访问可任意插入删除的Vector导致它既不是高效的栈也不是标准的集合。现代Java里一般用ArrayDeque替代Stack做栈处理从源码继承体系上就能看明白为什么不推荐旧Stack。3. 迭代器、快速失败与SubList的隐藏机制3.1 fail-fast异常到底是谁抛出来的用foreach遍历ArrayList时如果在循环里执行list.remove十有八九会遇到ConcurrentModificationException。这个异常全称是ConcurrentModificationException名字听着像并发问题其实单线程下也会抛。根源就在迭代器里的两个“版本号”字段。ArrayList内部类Itr里维护一个expectedModCount初始值等于外部ArrayList的modCount。modCount每次结构修改都会自增add、remove、clear都会动它但set不算结构修改因为set不会改变size也不会改变数组位置的数量。每次迭代器调用next时都会执行checkForComodificationfinal void checkForComodification() { if (modCount ! expectedModCount) throw new ConcurrentModificationException(); }一旦外部集合的modCount和迭代器保存的expectedModCount对不上迭代器就认为自己看到的结构已经不是开始时那个结构了继续遍历会产生错误结果所以干脆抛异常。foreach语法糖编译之后本质就是Iterator迭代因此foreach中删除元素必然踩雷。正确的遍历中删除姿势是用迭代器自己的remove方法IteratorInteger it list.iterator(); while (it.hasNext()) { if (it.next() % 2 0) { it.remove(); } }因为Itr.remove内部先调用ArrayList.this.remove(lastRet)然后重新同步expectedModCount modCount也就是说迭代器知道是自己动手干的版本号一致化之后就不会误判。JDK 8之后很多场景还可以直接用removeIf实现同样的效果底层同样通过迭代器来做代码更简洁。3.2 ListIterator与双向遍历的实现差异ArrayList和LinkedList都支持ListIterator它比普通Iterator多了hasPrevious、previous、add、set等能力。注意ListIterator.add会把新元素插入到cursor位置之前而且不会触发ConcurrentModificationException原因是它自己会调整expectedModCount。这里有一个易错点调用listIterator(index)获取反向迭代器时cursor初始值是index如果直接调用previous会得到index - 1位置的元素。很多人写倒序遍历时漏了这点提前崩溃。LinkedList因为是链式结构它的ListIterator实现起来很顺手游标移动就是节点指针切换。ArrayList的ListIterator虽然也支持但你拿它做大规模的previous操作时本质还是数组下标来回移动并没有额外损耗这点比LinkedList要舒服。面试里如果被问到“为什么ArrayList也能用ListIterator反向遍历”你可以说因为下标访问天然支持任意方向游走。3.3 SubList与视图机制对子列表修改的连锁反应SubList是ArrayList里非常容易被忽略的机制。list.subList(2, 5)返回的不是独立副本而是一个视图对象它内部持有父列表的引用parent以及offset、size两个字段。所有对subList的读操作最终通过parent.get(offset i)完成所有写操作也直接反映到父列表上。这个设计有好处可以快速对原列表的局部区域做修改而不需要复制。最经典的用法是Collections.shuffle(list.subList(1, 4))只重排子区间。但它也有一个大坑一旦subList创建后原列表的size发生任何结构性变化subList的modCount检查就会触发异常后续任何操作都会抛ConcurrentModificationException。更隐蔽的是通过subList修改元素位置比如在subList里add原列表size变别的subList全部失效。用人话说想拿subList当“切片副本”用的人会死得很惨你只是拿了个遥控器遥控器依赖电视本体。4. 性能数据的源码级推导与场景选型不再靠背结论4.1 时间复杂度每一个结论都能在源码里找到一行对应的代价ArrayList的get(int)直接return elementData[index]一次数组寻址O(1)。LinkedList的get(int)先判头尾再遍历最多走size/2步O(n)。这个对比几乎人人都知道但很多人不知道add(int index, E element)这个“中间插入”其实两者都是O(n)ArrayList要把index之后的所有元素用System.arraycopy后移一位LinkedList要先遍历到index位置再修改四个指针。常数上有区别但复杂度同阶。真正拉开差距的是头尾插入和随机访问两个维度。操作ArrayListLinkedListadd(E)尾部追加均摊O(1)可能触发扩容O(1)创建新节点addFirst / addLast数组搬移O(n)O(1)头尾指针操作get(index)O(1)下标访问O(n)二分方向遍历remove(index)O(n)数组搬移O(n)遍历改指针remove(Object)O(n)遍历搬移O(n)遍历改指针内存占用数组连续有预留容量每个节点额外两个引用System.arraycopy虽然是native方法且经过SIMD优化速度飞快但它终究要动整段内存数据量上来之后还是能感觉到明显的耗时。而LinkedList的中间遍历本身已经够慢再加上节点分散导致的缓存缺失两者实际差距比纸面复杂度更大。这里非常不建议凭感觉选LinkedList绝大多数场景ArrayList就是最优解。4.2 内存布局与缓存命中现代CPU视角下的选择数组是一段连续的内存空间ArrayList的元素在物理内存上紧挨在一起。CPU读取数据时会一次性把相邻的一整块数据加载进缓存这个机制叫缓存行。当你遍历ArrayList时大部分数据都能从L1/L2缓存里直接命中速度极快。LinkedList的每个Node是单独new出来的对象在堆上分配时位置随机节点间靠引用连接遍历时要不停地跳转内存地址几乎每一步都在等缓存miss。数据量小的时候差别不明显百万级别时差距就会达到几十倍甚至百倍。还有一个隐藏的内存问题LinkedList每个Node对象除了数据本身还有next和prev两个引用在开启压缩指针的64位JVM上一个Node大约要占24字节以上再加上对象头开销比ArrayList只存一个引用要大得多。更坑的是频繁new节点和断开节点的引用会让GC更频繁地扫描和回收对象。我之前在某个处理大量撤销历史记录的模块里用过LinkedList后来换成ArrayList之后不仅RT下降内存占用也肉眼可见地变小了这就是内存布局的威力。4.3 选型决策树一个可以直接抄作业的思路选型从来不该靠“感觉”,按下面这套决策树走基本不会出错大部分情况只有尾部追加和按下标读直接ArrayList。需要频繁在头部插入/删除而且数据量不小首选ArrayDeque只有当明确要按位置访问链表节点时才选LinkedList。多线程读多写少且只是遍历CopyOnWriteArrayList而不是Vector。频繁在List头部操作不要执着于ArrayListArrayDeque的循环数组设计把头部操作优化成了O(1)。需要栈后进先出ArrayDeque不要用Stack。对内存占用敏感且数据总量可预估ArrayList构造时传初始容量避免反复扩容。只在乎尾部操作和迭代顺序稳定性LinkedList其实也能选但收益并不比ArrayList高多少。这套决策树看下来你会发现LinkedList属于那种“知道得很多、用得极少”的类它在JDK里更多承担的是Deque接口实现者的角色。真正的开发中如果你发现自己非要用LinkedList先停下来想想是不是可以用ArrayDeque实在不行再回头用它也不迟。5. JDK版本演进对三大List的影响不能再守着老八股5.1 不可变集合的崛起从List.of到Stream.toListJDK 9引入了List.of系列静态工厂方法它们返回的不是ArrayList而是一个专门造的不可变内部类ImmutableCollections.ListN。这个类的长度固定不允许add、remove、set操作连修改都会直接抛UnsupportedOperationException。由于不可变对象天然线程安全且可以用紧凑的存储结构它的内存和性能都优于ArrayList。到了JDK 10List.copyOf进一步支持从已有集合复制一份不可变集合。JDK 16之后Stream.toList也加入了很多人喜欢用它替代collect(Collectors.toList())。Stream.toList返回的正是一个不可变列表如果后续代码想add就会报错。这个变化其实在逼着你早点想清楚你拿到的这个List是“读多”的集合还是“写多”的集合读多写少直接走不可变集合安全又省心。5.2 SequencedCollection与JDK 21的三者统一JDK 21引入了SequencedCollection接口它给List、Deque这些有序集合定义了一组统一方法getFirst、getLast、addFirst、addLast、reversed()。以前你面对这样一个困境ArrayList有get(0)但没见过getFirstLinkedList实现了Deque所以有addFirstArrayList和Vector都没有这些方法。现在List接口继承SequencedCollection之后所有List都有这6个方法了。这个变化对源码阅读的影响不大它更多是API设计的收敛让“有序集合”这个概念终于有了规范的表达。如果你用的是JDK 21操作ArrayList头部时可以直接getFirst内部实现还是基于size和下标检查不能和LinkedList的addFirst在复杂度上划等号。这一点务必注意别看了几个新API就以为底层也变了。5.3 Vector在并发编程中的真实定位Vector的synchronized是方法级别的这意味着它只能保证单个方法的原子性。两个线程同时做“判断是否为空再取出元素”这种复合操作时仍然会出问题因为判断和取出是两个独立的锁临界区。相比之下CopyOnWriteArrayList在写操作时复制底层数组读操作完全无锁读多写少的场景明显更优。而ConcurrentLinkedDeque等并发容器则在高并发栈/队列场景下更加可靠。Vector现在留下来的最大价值是历史兼容它仍然让许多老代码能平滑运行在最新JDK上但从新项目选型的角度它已经不具备优先考虑的理由了。当你看到一处代码还在用Vector优先想想是不是可以迁移到ArrayList或者CopyOnWriteArrayList大多数迁移成本都很低。6. 高频性能陷阱与问题排查实录6.1 并发修改异常与foreach里删除元素的正确姿势这个问题我在线上至少排查过十几次。最常见的现场是用户在for (Object obj : list)中执行list.remove(obj)然后秒抛CME。前面讲过快失败机制的原理这里只给结论单线程下要用迭代器删除或者用removeIf或者干脆先收集要删的数据再统一removeAll。还有一种特别隐晦的写法用list.subList返回子列表后在foreach子列表的过程中删除原列表元素也会触发CME因为subList持有的modCount是根列表的版本号。破案思路通常是翻线程栈看到checkForComodification然后马上意识到有视图没有同步。6.2 subList的脏读与视图失效问题接上面接着说一个实际案例某系统有一个按批次操作一批数据的功能开发图方便用subList(0, pageSize)做了个分页遍历拿到子列表后先对子列表做了一些计算然后回头又对originalList调用addAll添加新数据。结果再次访问子列表时直接崩了原因就是subList检测到父列表结构变化。这里的解读指向一个原则subList生命周期必须很短用完之后立刻丢弃绝不能跨多个“结构变更操作”存活。如果需要真正独立的切片必须new ArrayList(original.subList(...))完整拷一份代价是O(n)的复制但换来的是安全。6.3 扩容引起的抖动与内存峰值用构造容量治本ArrayList的扩容虽然在均摊意义上是O(1)但它有一个不可忽视的瞬时峰值扩容时要把旧数组的内容一次性复制到新数组复制期间新旧数组同时在内存中数据量大时内存占用直接翻倍。如果容量的增长次数很多频繁的大复制还会加剧GC压力。最简单的方案就是在构造时估算容量ListString list new ArrayList(预估大小);比如你知道要读大概一万条记录直接new ArrayList(10000)。不够了再让JDK自己扩但至少省了前几次搬运的损耗。如果连预估都很难可以考虑用ArrayList.ensureCapacity方法在有把握的时机主动扩容把扩容带来的卡顿控制在自己可预测的窗口内。这个方法在实时性要求高的系统中特别管用是我做性能调优时最经常用的三板斧之一。6.4 别再冤枉LinkedList的“性能好”最后给LinkedList说句公道话它的性能劣化主要集中在需要按下标随机访问的场景。如果你确实只用它作为队列、双端队列只做头尾操作那么它的表现是非常优秀的。问题在于很多人在使用场景里混进了“按位置查找并删除”这种操作导致整体复杂度升高一个量级。我有个真实案例某列表几万个元素业务逻辑循环里反复list.get(i)和list.remove(i)结果一个原本应该秒级完成的逻辑跑了三十多秒后来换成ArrayList并改用迭代器批量标记后掉到三百毫秒。相同逻辑、不同结构性能可以差出两个数量级。真到排查性能问题时如果发现热点代码用的是LinkedList先看它是否做了随机访问这是定位的黄金法则。我个人在实际开发中体会最深的就是源码不是用来背的是用来解释现象的。每次看到ConcurrentModificationException、每次发现List操作变慢、每次纠结用哪个集合回到源码里找一行判断逻辑或者一个for循环问题往往立刻就有了方向。不管JDK版本怎么迭代理解底层结构的习惯一旦养成你在集合这一块就基本不会再踩坑了。