LinkedList可能是Java集合包里争议最多的类了。网上到处都是“LinkedList插入删除快、随机访问慢”的说法可真要追问一句为什么快、为什么慢、快和慢的场景到底是什么能说清楚的人就很少了。我前阵子把JDK源码里的LinkedList从头到尾逐行读了一遍边读边在笔记本上画图、做标注发现不少“常识”其实是一刀切的不准确结论。这篇文章就把我的阅读过程完整复盘一遍从数据骨架、核心方法实现细节到迭代器、队列身份、线程安全与选型尽量把每个“为什么”都拆开讲。如果你也在啃源码但总觉得枯燥、容易忘这篇也许能帮你建立一套读集合源码的姿势。1. 读LinkedList源码前先破除三个流传很广的误解1.1 “插入删除一定快”——这句话只对了一半我先说一个很多人都踩过的坑。用LinkedList做中间插入有人觉得“既然是链表只要改一下前后指针就能插入必然是O(1)嘛”。实际上LinkedList的public接口暴露的是int下标而不是节点引用。你调用list.add(100, element)它第一步要用node(100)找到第100个节点这一步本身就是O(n)的遍历真正链接新节点的那一下linkBefore确实是O(1)。所以中间插入的时间复杂度是O(n)和ArrayList的System.arraycopy移位没有本质区别甚至因为node()遍历每次都要走好几个引用常数还可能更大。我实际测试过一个场景往一个10万元素的LinkedList中间循环插入1000次耗时比同样操作的ArrayList高出不少。原因就是add(index, e)每次都从链表的一端开始走一半距离1000次就是大量次数的引用跳转而ArrayList哪怕每次搬移五万个元素System.arraycopy是底层优化过的内存拷贝速度极其快。所以以后再看到“LinkedList插入快”一定先问一句插哪如果是从头或尾插入那确实O(1)如果是中间插入别指望它比ArrayList快。删除也是一样。list.remove(index)要先node(index)定位同样O(n)。只有removeFirst和removeLast这种明确从两端删除的操作才是O(1)。看清这一点很多关于LinkedList“性能好”的讨论都可以冷静下来。1.2 “随机访问慢”——快慢要看从哪儿访问LinkedList的随机访问慢严格说是list.get(index)慢因为每一次get都要从最近的端点往中间找。JDK源码在node(int index)里做了一个方向优化如果index小于size 1就从first往后走否则从last往前走。也就是说访问下标0和下标size-1都是O(1)访问中间位置大约要n/2步。这里的size 1不是二分查找它只是选了离哪个端点更近并没有把复杂度从O(n)降下来但常数上确实省了一半。所以“随机访问慢”这个结论要修正一下准确说法是“按下标访问慢但访问首尾极快”。你在实际项目里如果确定只操作队列的两端LinkedList就没什么访问性能问题。很多技术文章把LinkedList整个打成“随机访问慢”的标签其实掩盖了它有getFirst、getLast、peekFirst、peekLast这些O(1)入口的事实。1.3 “LinkedList更省内存”——其实恰恰相反这个误解我以前也有。很多人觉得链表是“需要多少就分配多少”不像ArrayList要预留容量所以内存更省。但LinkedList每一个元素都包装在一个Node对象里一个Node至少包含三个字段item、next、prev。在64位JVM默认启用压缩指针时一个Node对象有对象头再加上三个引用字段算上对齐每个Node轻松超过24字节。而ArrayList是Object[]连续数组引用数组本身按元素数量精确增长对象头和数组头开销是一次性的。我算过一笔账存10万个元素ArrayList的Object[]大约几十万字节LinkedList除了业务对象还要额外再分配10万个Node对象每个Node至少多占用20多个字节。这一下就是若干兆级别的额外开销。在小内存场景这个问题会被放大得很明显。所以“链表省内存”只在一个特殊场景下略微成立你反复在中间插入删除导致ArrayList需要频繁扩容和搬移时的瞬时内存峰值可能更高。但从稳态内存占用看ArrayList几乎总是更省。2. 从三个字段和一个内部类看懂LinkedList的数据骨架2.1 Node内部类长什么样LinkedList不是直接继承AbstractList的随机访问结构而是自己定义了一个静态内部类Node。源码如下private static class NodeE { E item; NodeE next; NodeE prev; Node(NodeE prev, E element, NodeE next) { this.item element; this.next next; this.prev prev; } }这个类极简数据本身、前驱引用、后继引用、一个三参构造器。三参构造器把前驱、元素、后继一次性接好方便后面各种link方法直接new出一个已经串进链表骨架的节点。注意next和prev都是默认包可见的LinkedList在内部直接访问不需要getter/setter这也是JDK内部代码的一贯风格内部实现追求效率不为封装性牺牲简洁性。2.2 first、last、size三个字段LinkedList一共只有三个实例字段transient int size 0; transient NodeE first; transient NodeE last;size记录元素个数first指向头节点last指向尾节点。有趣的是这三个字段全部用transient修饰说明它们不参与默认Java序列化LinkedList自己实现了writeObject和readObject来逐节点序列化。为什么要自己做因为一个Node对象持有了前后两个引用如果直接序列化对象图会顺着next一直递归序列化出来的东西会包含大量重复的引用关系而且不同JDK版本内部结构一旦调整序列化数据也没法兼容。自己写序列化只把item按顺序写进去读回来时一个个linkLast既干净又稳定。维护first和last两个端点带来的直接好处是addLast不用遍历链表找尾addFirst也不用额外记一个哨兵节点。很多教材里写链表会说“带头节点的单链表”但JDK的LinkedList没有哨兵head而是用null代表空链表。判断空链表只看first null或者说size 0。这里有一个贯穿全部源码的实现细节值得记住链表为空时first和last都是null链表不为空时first.prev一定是nulllast.next也一定是null。这个不变量被所有增删方法维护源码里所有边界判断都在围绕它展开。2.3 为什么必须是双向链表很多人问LinkedList为什么不做成单链表那样Node还能省一个引用答案分两方面。第一Deque接口要求。LinkedList实现了Deque也就必须支持从尾部向前遍历、从尾部删除节点。如果是单链表想做removeLast必须从头走到尾找到倒数第二个节点复杂度O(n)完全违背双端队列的设计意图。双向链表让两端操作都是O(1)。第二删除任意节点时双向链表的unlink操作能直接拿到待删节点的prev和next不需要像单链表那样额外维护一个前驱指针。虽然在按index删除的场景里node(index)已经帮你走到了位置但如果代码持有某个Node引用比如迭代器内部双向删除的优势就体现出来了。2.4 字段设计带来的操作复杂度一览读到这里其实就可以把LinkedList的能力边界列出来了头插、头删、尾插、尾删O(1)按下标插入、删除、访问O(n)按值查找O(n)迭代遍历O(n)但每次next只是走一个引用跳转这张表比“插入删除快”的说法精确太多也是后面选型判断的依据。读源码时先建立这张复杂度表后面看方法实现就不会晕。3. 核心方法源码逐段拆解add、remove、get的完整链路3.1 添加方法linkFirst、linkLast与linkBefore所有添加操作最后的落点都是三个私有link方法。先看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; }linkLast的关键是先把旧last存到局部变量l里然后创建新节点新节点的prev指向旧尾next为null。接着把last更新为新节点。如果l是null说明链表本来是空的这时first也要指向新节点链表从空变成单节点否则把旧尾的next指向新节点。最后size自增modCount自增。modCount是AbstractList里定义的结构化修改计数器后面讲迭代器的时候会再提到。linkFirst完全对称只不过操作的是firstprivate void linkFirst(E e) { final NodeE f first; final NodeE newNode new Node(null, e, f); first newNode; if (f null) last newNode; else f.prev newNode; size; modCount; }linkBefore用于在指定节点succ之前插入新节点void linkBefore(E e, NodeE succ) { final NodeE pred succ.prev; final NodeE newNode new Node(pred, e, succ); succ.prev newNode; if (pred null) first newNode; else pred.next newNode; size; modCount; }这个方法的边界处理是新节点的前后分别接上succ的前驱和succ本身然后更新succ.prev如果pred为空说明succ原本是头节点新节点要顶替first否则把pred.next接到新节点。三个link方法都完美维护了“first.prev必为null、last.next必为null”的不变量。阅读源码时我建议把这三个方法并列起来看你会发现它们的结构几乎一样先读出边界节点再创建新节点再分空表和非空表两种情况修补引用。3.2 删除方法unlink的指针清理暗藏GC心思删除的统一入口是unlink(Node x)E unlink(NodeE x) { final E element x.item; final NodeE next x.next; final NodeE prev x.prev; if (prev null) { first next; } else { prev.next next; x.prev null; } if (next null) { last prev; } else { next.prev prev; x.next null; } x.item null; size--; modCount; return element; }这里很多人会忽略的细节是unlink把被删节点的prev、next、item全部置为null。从纯功能角度看引用断了链表已经不再包含这个节点即使不清null也能正常工作。为什么要清核心原因是帮助垃圾回收。如果某个业务对象被从list里remove但list内部还残留着对它的引用比如x.item还指着它那么这个对象就不会被GC回收等于变相内存泄漏。JDK开发者在这个细节上相当谨慎凡是移出容器的元素都会把容器内部的强引用断开。另一个值得体会的点是unlink的双分支写法先处理prev分支再处理next分支。当头尾边界重叠时比如链表只有一个节点prev和next都是null第一个if把first更新为next也就是null第二个if把last更新为prev也是null最终first和last双null链表回到空状态。这个写法不要试图合并成一个if拆开写反而更清楚每种边界情况都被显式照顾到了。3.3 访问方法node(int index)里的size 1按下标访问的核心是node方法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取整。这个判断决定了从头走还是从尾走。它的复杂度仍然是O(n)但平均访问路径从n缩短到n/2。比如size是100万访问index 500000时不管从哪头走都要50万步但如果经常访问靠前或靠后的数据这个优化能明显降耗时。node方法被add(index, e)、remove(index)、get(index)、set(index, e)这些所有按下标操作的方法共用所以它是LinkedList的“心脏”。看完node方法就能彻底理解为什么for循环用get(i)遍历LinkedList会出问题每次get(i)都会执行一次node(i)从链表头部重新走i步。于是for循环的总步数就是012...(n-1)约等于n²/2。10万元素就是约50亿次引用跳转不超时才怪。3.4 查找与修改indexOf与setindexOf是从头顺序比较本身没有什么花活public int indexOf(Object o) { int index 0; if (o null) { for (NodeE x first; x ! null; x x.next) { if (x.item null) return index; index; } } else { for (NodeE x first; x ! null; x x.next) { if (o.equals(x.item)) return index; index; } } return -1; }注意它对null元素单独做了一次循环避免在循环里判断“o null ? x.item null : o.equals(x.item)”这种每轮都要做的三目判断。这种把null查找和正常查找拆成两个循环的做法在JDK源码里反复出现比如ArrayList的indexOf也是这么写的。为什么这么麻烦因为内部循环短一点JIT编译后少一条分支高频场景下能省不少指令。读源码时看到这种重复代码不要觉得啰嗦这是性能抠到细节的表现。set(index, element)方法有一个容易被人忽略的副作用它会返回旧值。实现是先node(index)找到目标节点再取oldValue把item换成新值返回。有人把它当摆设其实如果业务上需要把旧值拿出来做对比或记录set返回旧值就省了额外一次get。3.5 modCount一个被大多数人忽略的计数器前面几个方法里都出现了一个modCount。modCount在AbstractList里定义记录list结构性修改的次数。结构修改指改变size的操作比如add、remove、clear而set只替换item不算结构修改不会增加modCount。迭代器创建时会记录当时的modCount为expectedModCount每次迭代前会检查两者是否一致不一致就抛ConcurrentModificationException。这个机制叫fail-fast它不是为了给多线程加锁用的并发安全机制而是在迭代过程中发现列表被结构性地改了以后尽快失败避免脏数据继续跑。读完这些核心方法建议自己脑内演算一遍一个只有3个节点的链表add(1, x)从空到1个、到两个、再到三个把边界全部走一遍。源码这东西光看不过瘾动手演算一次记忆会深得多。提示读源码时看到modCount不要直接跳过它是理解fail-fast和迭代器行为的关键。以后自己写容器类也应该在结构修改的位置维护一个类似的计数器。4. 迭代器与遍历效率为什么LinkedList的for循环成了性能陷阱4.1 ListItr的实现骨架LinkedList的迭代器是一个私有内部类ListItr实现了ListIterator。它维护三个指针private class ListItr implements ListIteratorE { private NodeE lastReturned; private NodeE next; private int nextIndex; private int expectedModCount modCount; ... }lastReturned是上一次返回的节点next是下一次即将返回的节点nextIndex是next对应的逻辑下标。迭代器的next()做的操作是先checkForComodification()检查modCount然后取出next的item把next向后挪一个节点如果next为空说明到底了再更新lastReturned。整个过程没有node(int index)的下标遍历所以迭代器遍历LinkedList的总代价是O(n)这才是遍历LinkedList正确的方式。ListIterator还提供了previous、add、set、remove这些双向迭代和就地修改能力。特别是previous它依赖prev指针这是ArrayList的迭代器做不到的。如果你需要一个前后来回都能走的list遍历器LinkedList的ListItr是明确优势。4.2 两种遍历方式的复杂度对比把两种遍历方式并排看就很明显for (int i 0; i list.size(); i) list.get(i)O(n²)for (E e : list)内部走iteratorO(n)为什么很多老代码还是写第一种因为对ArrayList来说get(i)是O(1)for循环完全没问题用户把ArrayList的遍历习惯无脑带到LinkedList上就触发了性能陷阱。这其实是一个典型的“抽象泄漏”面向接口编程时如果你只声明List却不知道实现类的遍历成本差异很容易写出在一种实现上飞快、在另一种实现上慢到无法接受的代码。如果实在要从for i风格改成iterator风格又不想大改代码最简单的做法是把LinkedList先toArray然后遍历数组。代价是一次O(n)的拷贝换来后续O(n)的遍历。某些场景下这个改法很实用尤其适合那种“逻辑不变、底层结构换了”的存量代码。4.3 实测数据同样的测试代码差距有多大我自己用JMH简单测过一轮环境是JDK 8、10万条Integer数据。结果大致是这样遍历方式ArrayList耗时LinkedList耗时for i get(i)3ms左右数秒量级foreach / iterator3-5ms5-8ms这个数据的绝对数值取决于机器不值得刻在脑子里但“数量级差异”是稳定的。LinkedList用for i方式遍历10万个元素基本要跑好几秒而用iterator遍历只要个位数毫秒。原因就是前面说的n²次引用跳转。顺带一提在纯迭代场景下LinkedList并不比ArrayList明显慢很多时候还差不多因为ArrayList需要经过边界检查访问数组元素LinkedList只是解一个引用两者常数都在纳秒级。5. Deque身份LinkedList的另一副面孔5.1 一条声明带来两种能力LinkedList的类声明是public class LinkedListE extends AbstractSequentialListE implements ListE, DequeE, Cloneable, java.io.Serializable很多教学只把它当List用忽略了它同时实现了Deque接口。这意味着LinkedList天生就是一个双端队列既可以从头部插也可以从尾部插既可以pop也可以push完全可以当栈和队列用。Deque接口里那些offerFirst、offerLast、pollFirst、pollLast、push、pop、peek等一大堆方法在LinkedList里都有一一对应的实现。实现逻辑并不复杂offerFirst封装linkFirstpollFirst封装unlinkFirstpeekFirst就是读出first.item。可以说Deque的方法本质上是把前面拆解过的link/unlink操作换了一个公开的壳。5.2 队列操作背后的指针操作以pollFirst为例public E pollFirst() { final NodeE f first; return (f null) ? null : unlinkFirst(f); }unlinkFirst和unlink的差别只在头节点的prev一定是null所以不需要处理前驱分支只需要处理后继分支private E unlinkFirst(NodeE f) { final E element f.item; final NodeE next f.next; f.item null; f.next null; first next; if (next null) last null; else next.prev null; size--; modCount; return element; }你会发现它同样把被删节点的item和next置为null帮助GC同样维护“first.prev必为null”。顺着这个思路去读removeFirst、removeLast、offerLast等等会发现彼此只是排列组合。所以读LinkedList源码不需要每个方法都背抓住link/unlink这两组私有方法其余全是它们的调度。5.3 和ArrayDeque对比LinkedList输在哪里既然能当栈和队列很多人就产生了选择困难既然LinkedList都能干为什么还要用ArrayDeque答案是ArrayDeque在几乎所有的双端操作上性能都优于LinkedList内存也更省。ArrayDeque内部是一个可变长的Object[]环形数组它没有Node对象没有每条元素的额外引用缓存局部性极好。如果你只是需要一个栈或队列不需要按下标访问、不需要中间插入ArrayDeque是最佳选择。LinkedList的Deque身份更多是一个“顺带实现”因为双向链表天然支持双端操作JDK作者顺手实现了Deque接口让它在需要List和Deque双重语义的时候能派上用场。但这种“什么都干”的类往往在任何一个维度都不是最优的。用一句话说列表操作优先ArrayList纯队列栈优先ArrayDequeLinkedList只在“需要频繁从两端操作且偶尔中间插入删除”的时候才有存在感。6. 线程安全、内存占用与真实选型6.1 线程不安全的两个层次LinkedList和ArrayList一样完全不是线程安全的。它的所有方法都没有同步保护。更隐蔽的是即便你在外部加了锁只要迭代期间有其他线程做了结构性修改fail-fast机制就会抛异常。这里要说清楚两个层次普通读写并发问题两个线程同时add可能覆盖彼此、size错乱。迭代期间并发修改抛ConcurrentModificationException这不是数据损坏而是快速失败保护。如果确实需要线程安全不要用Vector这种老古董而是在使用层加锁或者干脆换ConcurrentLinkedDeque、ConcurrentLinkedQueue这些并发容器它们才是为并发设计的。有人觉得“既然方法不是synchronized我把它包在Collections.synchronizedList里不就行了”可以但那样整个list的操作都被粗粒度锁串行化头部插入和尾部插入这种互不相关的操作也会互相阻塞。如果并发量高还是建议选专业的并发容器。这个选型逻辑和ArrayList面对的取舍一模一样并不是LinkedList独有的问题。6.2 内存计算一个Node到底多重我前面说过LinkedList更费内存这里精确算一下。假设JVM开启了压缩指针64位默认开启一个Node对象有对象头约12字节item引用4字节next引用4字节prev引用4字节合计24字节对齐后还是24字节这是Node本身的额外开销还不算item指向的业务对象。10万个节点就是约240万字节。而ArrayList存10万个元素Object[]数组的开销大概是数组对象头加对齐再加上10万乘4字节的引用总量约40万字节。这个差距接近6倍。这里还没有算ArrayList扩容时的余量但整体格局已经很明显。可以说在中等规模数据下LinkedList的内存劣势是实打实的不是网络上轻描淡写的“略有差异”。6.3 我现在的选型建议几年的实际项目做下来我的选择非常固定默认用ArrayList。数据连续、缓存友好、按下标访问O(1)、遍历快、内存省。只有当业务明确需要“高频从首尾增删且几乎不做按下标访问”时才考虑LinkedList。如果只是实现栈或队列直接上ArrayDeque不要用LinkedList和Stack。如果要存大量元素且经常中间插入删除先重新审视一下业务数据结构很多时候可以用两个ArrayList拼或用HashMap做索引整体复杂度能降一大截。举一个我印象很深的例子某个模拟项目里有一段代码用LinkedList维护一个“最近访问记录”每来一个请求就把旧记录删掉、新记录加到队尾。这个场景表面看很适合链表但数据量一上来contains、indexOf这些O(n)操作不断触发整个模块成了瓶颈。后来我把记录列表改成HashMap加一个按时间戳排序的数组结构中间删除改成逻辑删除性能瞬间就上来了。所以选型不能只看“增删快”这个单一指标要看全量操作序列的组合成本。7. 这次阅读源码我总结的几点实用方法如果你打算把LinkedList或其他集合源码啃完我可以分享几个让我少走弯路的方法。第一从字段开始读。任何类的源码先看它的实例字段再想“这些字段能支撑哪些操作是O(1)”。比如看到first、last就能推断出首尾操作快看到size就明白所有方法都会维护它。字段决定了数据结构数据结构决定了复杂度复杂度决定了选型这是一条完整的推理链。第二抓住私有方法忽略公有外壳。LinkedList真正干活的私有方法就那么几个linkFirst、linkLast、linkBefore、unlink、unlinkFirst、unlinkLast、node。公开方法只是参数校验加调用私有方法。你把这些私有方法在纸上画一遍比读两百行公开方法都管用。第三画出删除和插入的指针变化图。拿一个只有三个节点的链表手动模拟add(1, x)和remove(1)每一步都更新first、last、prev、next。画到第三遍边界条件就再也不会忘了。我自己的笔记里到现在还留着类似这样的手绘图每次看都很有收获。第四对比着读。把LinkedList和ArrayList对应的add、remove、get放在一起看你才会明白为什么接口一样但复杂度完全不同把LinkedList和ArrayDeque放在一起看你才会知道为什么队列场景要选数组。对比是读源码最有效的方式比单独顺着方法列表走一遍强得多。最后再提醒一句源码里的注释和代码风格也值得学。比如unlink这个命名虽然短但它准确表达了类的内部“解除节点连接”的统一操作读代码的人不会对意图产生歧义。我写业务代码时也开始刻意学习这种“私有方法承担单一职责、公开方法做薄壳”的组织方式代码的可读性确实好了不少。