Java LinkedList 和链表几乎是每个 Java 程序员都绕不开的话题。你刷面试题会碰到它读中间件源码会碰到它日常写队列、LRU 缓存、文件系统索引时也全是它的影子。这篇文章不打算把 LinkedList 的 API 背一遍而是从数据结构本身讲起结合 JDK 源码、手写实现和面试常考算法题把链表这个基础结构彻底吃透。适合正在准备 Java 面试的人也适合想补数据结构短板的在职开发。我会把每个结论背后的原因讲清楚你照着练完至少能在面试时把“链表为什么存在”“LinkedList 为什么有些操作反而慢”这种追问讲明白。1. 链表的基础认知与设计思路1.1 为什么面试官和源码都在盯链表面试官爱考链表核心原因有三层。第一层是链表考的是指针操作和边界思维一个节点指错了、一个空指针没判整个逻辑就崩。这比背一个排序算法更能看出候选人写代码时有没有防御意识。第二层是链表是很多高级结构的地基栈、队列、哈希桶里的拉链法、图的邻接表底层都有链表的身影。第三层是最现实的Java 的 LinkedList、ConcurrentLinkedQueue、LinkedHashMap 这些高频类内部全是链表结构你阅读源码绕不开它。实际工作中链表的变形应用也随处可见。比如用双向链表加哈希表实现 LRU 缓存这是 Redis 和很多框架都在用的经典组合再比如线程池里的阻塞队列很多实现底层也是链表节点。所以链表绝不只是面试八股理解了它你再看那些框架源码会顺畅很多。1.2 数组与链表的本质差异连续内存 vs 离散内存要理解链表最有效的方式是和数组对比。数组在内存里是一块连续空间通过首地址加下标直接算出元素位置所以任意访问的时间复杂度是 O(1)。但代价是插入和删除需要大批量搬移元素平均 O(n)而且扩容时要重新分配一整块内存。链表恰好反过来。它的节点散落在内存各处每个节点除了存数据还存了下一个节点的引用单向链表或前后两个引用双向链表。因为内存不连续它没办法随机访问想找第 n 个节点只能从头一个个跳过去所以按下标访问是 O(n)。但插入和删除只要改指针指向时间复杂度是 O(1)前提是你已经拿到了目标节点。这里我多说一句实际编程里最容易犯的错很多人以为 LinkedList 的插入删除一定比 ArrayList 快这是完全错误的。list.add(index, element)这个操作里LinkedList 要先用 O(n) 的时间遍历到 index 位置然后才 O(1) 改指针ArrayList 虽然插入时搬移元素要 O(n)但人家找位置是 O(1) 的。小数据量时二者差别微乎其微大数据量时 LinkedList 反而可能因为节点分散、CPU 缓存命中率低而更慢。这个点我后面专门用一个章节细讲。1.3 三种基础链表形态单链表、双链表、循环链表链表按形态分三种面试时经常直接问你“能不能说出它们的区别”。单链表最简单每个节点只有一个 next 指针遍历只能从头到尾想删除某个节点必须知道它的前驱节点。双链表每个节点多了 prev 指针可以双向遍历删除节点时不需要再额外找前驱。循环链表让尾节点的 next 指回头节点约瑟夫环问题就是典型应用场景。Java 的 LinkedList 是双向链表而且不是普通双链表它同时维护了 first 和 last 两个指针并且头节点的 prev 和尾节点的 next 都为 null。这个设计让它在头部和尾部操作时都是 O(1)所以它能同时作为栈和队列来用。我刚开始看源码时以为它就是简单的双向链表后来才发现 JDK 里为了性能做了很多“两端操作优化”这个思路值得写进你自己的代码里。2. Java LinkedList 源码拆解看看 JDK 是怎么实现的2.1 继承体系与节点内部类先看 LinkedList 的类声明和节点结构。它继承了 AbstractSequentialList实现了 List、Deque、Cloneable、java.io.Serializable 这几个接口。最关键的是实现了 Deque所以它同时具备双端队列的能力可以addFirst、addLast、removeFirst、removeLast还能当栈用push/pop。节点内部类是典型的双链表节点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; } }注意这个构造方法把 prev、element、next 一次传进来这种写法在 JDK 源码里到处都是好处是创建节点的同时就把前后关系建立好了不用先 new 出来再挨个 set。自己手写链表时也应该这样设计构造函数省代码且不容易漏字段。LinkedList 内部只维护了两个字段transient int size 0; transient NodeE first; transient NodeE last;没有下标数组所以 LinkedList 的get(int index)只能靠遍历。JDK 在这里做了一个小优化先判断 index 靠前半段还是后半段如果靠后就从 last 往前遍历。这个二分查找式的遍历把最坏遍历次数从 n 降到 n/2虽然复杂度还是 O(n)但源码的这份细节值得学习。2.2 add 和 remove 的核心逻辑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; }这段代码值得逐行读。先把旧 last 存到局部变量 l然后创建新节点prev 指向 lnext 指向 null。接着更新 last 为新节点。如果 l 为 null说明链表是空的那 first 也要指向新节点否则让旧尾节点的 next 指向新节点。最后 size 加一modCount 加一。modCount是抽象类 AbstractList 里的字段记录结构修改次数。add、remove、clear这些改变链表结构的操作都会让它自增。它存在的意义我放到后面的 fail-fast 机制里讲这里先记住遍历时结构不能变。再看不带参数的remove()它移除的是首节点public E removeFirst() { final NodeE f first; if (f null) throw new NoSuchElementException(); return unlinkFirst(f); }unlinkFirst 里会把首节点的 item 和 next 置为 null帮助 GC 回收。这里有一个实操启示你自己写链表时删除节点后一定要把 item 置 null否则大对象链路会导致内存无法被及时回收长连接服务里这是典型的隐性内存泄漏源。2.3 迭代器与 fail-fast 机制的坑LinkedList 的迭代器是 ListItr它继承自 AbstractList 的内部类。它除了维护 cursor下一个要返回的节点下标还有一个预期 modCount 字段初始值就是创建迭代器时的 modCount。每次调用 next 或 remove 时都会先检查final void checkForComodification() { if (modCount ! expectedModCount) throw new ConcurrentModificationException(); }这就是 fail-fast 机制在迭代过程中如果有其他线程或代码调用了 add/remove 这类结构性修改方法modCount 变了迭代器立刻抛异常而不是等遍历出诡异结果后才排查。我踩过这个坑在for (String s : list)里直接调list.remove(s)结果抛 ConcurrentModificationException。正确做法是使用迭代器的it.remove()因为迭代器的 remove 方法会同步更新 expectedModCount。IteratorString it list.iterator(); while (it.hasNext()) { String s it.next(); if (s.equals(特殊值)) { it.remove(); // 安全 } }还有一个细节list.remove(s)和it.remove()在性能上也有差别。前者会再从头部遍历找元素后者因为已经定位到了当前节点直接 unlink少一次遍历。数据量大时这个差别不能忽略。3. 手写单链表的完整实操3.1 节点定义与初始化看源码终归是输入动手写一遍才有手感。面试时手写链表经常要求在十几分钟内完成所以我这里给一套可以直接抄的骨架。先定义节点。我的习惯是使用静态内部类因为节点不需要访问外部类的实例字段静态内部类还能避免内存泄漏。注意泛型写法public class MyLinkedListE { private static class NodeE { E item; NodeE next; Node(E item) { this.item item; } } private NodeE head; private int size; public MyLinkedList() { head null; size 0; } }这里不维护 tail是因为我要演示的是一套纯单链表操作加了 tail 很多逻辑会变简单但也掩盖了边界处理的细节。等你把不带 tail 的写熟了再加 tail 就是顺手的事。3.2 头插法与尾插法的取舍头插法最简单也最快因为不需要遍历public void addFirst(E e) { NodeE newNode new Node(e); newNode.next head; head newNode; size; }注意这里有个经典错误有人会先把 head 保存到局部变量再 new 节点然后 head 指向新节点、新节点指向旧 head。两种写法都对但上面这种更简洁。关键是顺序不能反一定是先让新节点的 next 指向旧 head再让 head 指向新节点。反过来的话旧 head 就丢了链表就断了。尾插法需要遍历到最后一个节点public void addLast(E e) { NodeE newNode new Node(e); if (head null) { head newNode; } else { NodeE cur head; while (cur.next ! null) { cur cur.next; } cur.next newNode; } size; }我的实操感受是如果代码里频繁出现“遍历到尾部再插入”的场景那你应该在类里维护一个 tail 字段。尾插复杂度从 O(n) 降到 O(1)代价是删除节点、清空链表时要多处理一个指针容易漏。LeetCode 的链表题很多默认不给你 tail就是为了让你练熟遍历。3.3 在指定位置插入元素的完整代码这是热搜词里“在指定位置插入建立单链表”对应的核心操作。先看我的标准实现public void add(int index, E e) { checkPositionIndex(index); if (index 0) { addFirst(e); } else { NodeE prev node(index - 1); NodeE newNode new Node(e); newNode.next prev.next; prev.next newNode; size; } } private NodeE node(int index) { NodeE cur head; for (int i 0; i index; i) { cur cur.next; } return cur; } private void checkPositionIndex(int index) { if (index 0 || index size) { throw new IndexOutOfBoundsException(越界: index); } }核心就两句话新节点的 next 指向 prev 的下一个节点prev 的 next 指向新节点。顺序绝对不能反。如果你先执行prev.next newNode那么原来 prev 后面的整段链表就找不到了。我见过很多新手在 index 0 时也走通用逻辑结果因为 prev 是 null直接空指针。把第一个位置单独处理是最稳妥的方式这也是为什么我每次都会先判断index 0。另外node(index - 1)的遍历逻辑里循环条件是i index跳 index 次正好落在下标为 index 的节点上你自己写的时候宁可多写几个测试用例也别凭感觉。3.4 删除、遍历与清空操作的边界处理删除指定下标的节点关键同样是要拿到前驱节点public E remove(int index) { checkElementIndex(index); if (index 0) { E old head.item; head head.next; size--; return old; } NodeE prev node(index - 1); NodeE target prev.next; prev.next target.next; target.item null; // 手动释放帮助GC target.next null; size--; return target.item; }注意我这里的顺序先把 target.item 保存到 old再置空。如果先置空再返回返回值就丢了。这是调试时最容易隐蔽的 bug。还有target.next null这一步如果不做旧节点还攥着下一个节点的引用虽然 JVM 的 GC 能处理但如果你做的是长生命周期缓存还是主动断开更稳妥。遍历时我喜欢用 while 而不是 for 循环逻辑更清晰public void printAll() { NodeE cur head; while (cur ! null) { System.out.print(cur.item - ); cur cur.next; } System.out.println(null); }清空链表时有个反直觉的点直接把 head 置空size 置 0 就行了吗在纯单链表里够用因为 head 一旦为 null后面所有节点都不可达了。但在双链表里不行JDK 的 clear 方法会遍历所有节点把 prev、next、item 全部置空。为什么因为双链表的内存里每个节点还被前后引用着单单置空头节点会让所有节点成为互相引用的“孤岛”老年代清理大对象时效率下降。所以我写双链表时都会参考 JDK 的 unlink 写法。4. 链表算法题的面试实战4.1 链表反转迭代法与递归法反转链表是面试出现频率最高的链表题没有之一。迭代法的核心是三个指针prev、cur、next。public NodeE reverse(NodeE head) { NodeE prev null; NodeE cur head; while (cur ! null) { NodeE next cur.next; // 先保存下一个节点 cur.next prev; // 当前节点指向前一个 prev cur; // prev 前进 cur next; // cur 前进 } return prev; // 最后 prev 就是新头 }这里最容易被问倒的细节是为什么需要 next 临时变量因为当执行cur.next prev之后cur 原来的下一个节点就丢了如果不提前保存循环就没法继续。这个顺序我在纸上画过很多次三个指针像推磨一样往前走每次循环结束 prev 指向已经反转好的子链表的头cur 指向还未反转部分的头。递归法代码更短但理解门槛高public NodeE reverseRecursive(NodeE head) { if (head null || head.next null) { return head; } NodeE newHead reverseRecursive(head.next); head.next.next head; head.next null; return newHead; }递归的思路是先反转后面的子链表得到 newHead然后把当前节点的下一个节点的 next 指回当前节点最后把当前节点的 next 置空。这句“head.next.next head”很多人想不通我建议你在纸上画三个节点的链表逐步展开递归栈画一遍就懂了。需要提醒的是链表很长时递归会导致栈溢出生产环境我优先选迭代法。4.2 快慢指针找中点、判环、找相交点快慢指针也叫龟兔赛跑是链表题的万金油。快指针每次走两步慢指针每次走一步。找链表中点快指针到底时慢指针刚好在中点。public NodeE findMiddle(NodeE head) { NodeE slow head; NodeE fast head; while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; } return slow; }判环也是快慢指针的经典应用如果有环快指针必然会在某个时刻和慢指针相遇。public boolean hasCycle(NodeE head) { NodeE slow head; NodeE fast head; while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; if (slow fast) { return true; } } return false; }再进一步如果要求返回环的入口节点还有一个“相遇后从 head 和相遇点同步走”的技巧。原理是数学推导出来的相遇时快指针比慢指针多走了 n 圈而头节点到入口的距离等于相遇点到入口的距离在一圈之内。这个结论面试时直接能答出来就行但建议自己也推一遍。注意快慢指针的循环条件fast ! null fast.next ! null两个判断缺一不可否则快指针步长是 2很容易空指针。关于热搜词里的“3898 · 链表相交(二)”核心思路是双指针两个指针分别从链表 A 和 B 出发走到头后换到对方的链表继续走。如果两个链表相交它们会在交点相遇因为两个指针走过的总路程相等。这个解法时间 O(mn)空间 O(1)比用哈希集合省内存面试时更讨喜。4.3 合并有序链表与链表排序合并两个有序链表标准递归解法public NodeInteger merge(NodeInteger l1, NodeInteger l2) { if (l1 null) return l2; if (l2 null) return l1; if (l1.item l2.item) { l1.next merge(l1.next, l2); return l1; } else { l2.next merge(l1, l2.next); return l2; } }这里有个小细节比较用还是会影响稳定性面试时可以提一句“用 能保证相等元素的相对顺序不变归并排序的稳定性靠的就是这个”。这种主动带出的知识点会让面试官眼前一亮。链表的排序我建议掌握归并排序。因为链表不具备随机访问特性快排的 partition 在链表上实现别扭而归并排序天然适配链表的拆分合并。核心是三步找中点拆成两半、递归排序两半、合并两个有序链表。找中点就用前面的快慢指针。public NodeInteger sortList(NodeInteger head) { if (head null || head.next null) return head; NodeInteger mid findMiddle(head); NodeInteger rightHead mid.next; mid.next null; // 断开 NodeInteger left sortList(head); NodeInteger right sortList(rightHead); return merge(left, right); }这个实现我用了很多次注意mid.next null那一步是切断链表的关键很多人的归并排序写出来死循环就是忘了在递归前把左右两半彻底分开。5. ArrayList 与 LinkedList 选型别再凭感觉了5.1 复杂度对比表面试时经常被问“ArrayList 和 LinkedList 有什么区别”这里把复杂度整理成表回答时直接照着说操作ArrayListLinkedListget(int index)O(1)O(n)add(E e) 尾部追加O(1) 摊还O(1)add(int index, E e)O(n) 搬移O(n) 遍历O(1) 改指针remove(int index)O(n) 搬移O(n) 遍历O(1) 改指针remove(Object o)O(n)O(n)内存占用连续数组 预留容量节点存储前后指针约2~3倍CPU缓存友好性高低看到没有add(index, e)和remove(index)两者都是 O(n)只是 O(n) 消耗的地方不同。ArrayList 是搬移元素LinkedList 是寻址。对于小数据集ArrayList 因为缓存友好反而胜出。我实际做过一个粗糙的基准测试往一个长度 10 万的列表头部逐个插入元素ArrayList 因为每次都要整体搬移耗时接近 LinkedList 的几十倍但如果是在列表中间位置插入数据量在几万以内时ArrayList 有时候反而更快。所以“LinkedList 适合频繁插入删除”这个结论只适用于“你已经在目标位置只需要做指针改动”的场景很多网上说法是片面的。5.2 实际场景下的真实表现那么 LinkedList 到底该在哪里用我的经验是三类场景。第一类是当栈或队列用。LinkedList 实现了 Dequepush、pop、offer、poll都是 O(1)两端操作非常顺滑。注意这里要优先用 ArrayDeque它内存更紧凑、性能更好LinkedList 的优势是允许 null 元素和没有容量限制。看情况选。第二类是频繁在迭代过程中删除元素。用迭代器的 remove 方法LinkedList 因为改的是指针比 ArrayList 的搬移快不少。比如做一个在线用户列表要频繁剔除超时连接LinkedList 在中间删除时受到的影响更小。第三类是实现 LRU 缓存。双向链表配合 HashMapget 和 put 都能做到 O(1)。Java 的 LinkedHashMap 就是基于链表维护访问顺序你继承它重写 removeEldestEntry 就能得到 LRU 缓存。反过来大部分业务查询场景比如按 index 随机读取、按顺序遍历、存的数据量大且需要频繁读取ArrayList 都是更优解。我的原则是默认用 ArrayList除非明确知道要频繁操作两端或者需要在迭代中大量删除才换 LinkedList。这个原则也送给所有正在纠结选型的读者。6. 常踩的坑与排查思路6.1 空指针与哨兵节点链表题的空指针是重灾区。典型场景add(index, e)时 index 为 0 没有单独处理导致 prev 为 null然后访问prev.next直接崩。解决思路有两个一是像我前面代码那样对 index 0 分支处理二是使用哨兵节点dummy head。哨兵节点是哑节点不存有效数据next 指向真正的头节点。这样所有插入删除都可以统一走“通过 prev 操作”的逻辑不用为头节点特殊处理。LeetCode 的链表题里凡是涉及“可能删除头节点”的操作比如删除倒数第 N 个节点我都建议先搞一个 dummy 节点NodeE dummy new Node(null); dummy.next head; NodeE prev dummy; // 之后统一处理最后返回 dummy.next这个技巧我第一次用的时候瞬间就把一堆边界判断化简了。你写复杂链表操作时先用 dummy 再动手出错的概率会小很多。6.2 ConcurrentModificationException前面讲过 fail-fast 机制但实际业务中还有另一种情况疑似多线程并发修改。比如一个线程在遍历 LinkedList另一个线程在尾部 add迭代器就会抛 ConcurrentModificationException。这里我要澄清一个常见误解fail-fast 是检测机制不是并发安全机制。LinkedList 本身不是线程安全的即使你不迭代两个线程同时 add 也可能丢数据或者把链表结构改坏。需要并发场景时用 ConcurrentLinkedQueue或者用Collections.synchronizedList包一层更稳妥的做法是用 CopyOnWriteArrayList读多写少时。如果是排查线上问题我一般先看异常栈是不是 Iteration 相关的 checkForComodification是的话去日志里查这个 List 被哪些线程操作。加日志时要打印线程名顺着线程栈能快速定位到是哪个业务代码在迭代中偷偷改了结构。6.3 循环链表导致的死循环手写链表不熟练时最容易出的是死循环。最常见的成因是尾插法里忘了把新节点的 next 置空或者反转链表后没把新尾节点的 next 置为 null导致最后两个节点互相指遍历时永远跳不出来。排查死循环我有一个笨但有效的办法在遍历循环里加一个计数上限比如最多跑 100 万次就强制退出并打印当前节点地址。加上这个兜底再定位能很快发现是不是某两个节点的引用形成了环。实际上 JDK 的 debug 版本也有类似思路叫做“环形保护”。生产环境的链表遍历代码里我建议对特别大的链表也考虑这类保护避免偶发坏数据把线程拖死。另外推荐一个可视化技巧写代码时把每个节点的 next 变化在纸上画成箭头图。链表相关算法的 bug绝大多数靠画图十分钟就能定位比反复看日志盲目加打印高效得多。我在带新人时都会让他们先把图画出来再写代码这个习惯比任何调试工具都有用。6.4 内存与性能的隐性陷阱还有一类问题跟链表的内存模型有关。LinkedList 的每个节点都是一个独立对象节点里有两个引用字段再加一个 item 字段空闲对象头就有十几字节的开销。存几十万个元素时内存占用明显高于 ArrayList频繁 new 节点也会加剧 GC 压力。我在一个高并发的消息转发模块里见过这样的问题用 LinkedList 做待发送队列结果老年代频繁回收接口时延抖动。后来换成数组实现的环形队列GC 压力马上降下来了。所以内存敏感的中间件代码里我很少用 LinkedList优先用 ArrayDeque 或者直接手写一个循环数组。还有一个小技巧如果你确定要用 LinkedList并且会频繁增删可以预估容量一次性 addAll 一批元素减少节点创建的次数。虽然 LinkedList 没有扩容的概念但减少零散 new 对象对 GC 总是友好的。最后再分享一个我在实际项目中总结的经验链表能让你把“指针操作”的直觉练出来而 Java 工程师最缺的恰恰是这种底层直觉。我建议大家把 JDK 的 LinkedList 源码从头到尾读一遍然后自己手写一个不带 tail 的单链表、一个带 tail 的双链表再把 LeetCode 的反转、判环、合并、排序四道经典题各做五遍。做到能闭着眼在白板上写出无 bug 的版本面试时这块基本就稳了。这五个版本写完之后你对链表、对指针操作、对边界防御的把握绝对会比死记硬背 API 的人高出好几个档次。