企业官网建设流程全解析

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 Node<E> { E item; Node<E> next; Node<E> prev; Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; } }

注意这个构造方法把 prev、element、next 一次传进来，这种写法在 JDK 源码里到处都是，好处是创建节点的同时就把前后关系建立好了，不用先 new 出来再挨个 set。自己手写链表时也应该这样设计构造函数，省代码且不容易漏字段。

LinkedList 内部只维护了两个字段：

transient int size = 0; transient Node<E> first; transient Node<E> last;

没有下标数组，所以 LinkedList 的get(int index)只能靠遍历。JDK 在这里做了一个小优化：先判断 index 靠前半段还是后半段，如果靠后就从 last 往前遍历。这个二分查找式的遍历把最坏遍历次数从 n 降到 n/2，虽然复杂度还是 O(n)，但源码的这份细节值得学习。

2.2 add 和 remove 的核心逻辑

add(E e)默认是尾插，核心调用 linkLast：

void linkLast(E e) { final Node<E> l = last; final Node<E> newNode = new Node<>(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++; }

这段代码值得逐行读。先把旧 last 存到局部变量 l，然后创建新节点，prev 指向 l，next 指向 null。接着更新 last 为新节点。如果 l 为 null，说明链表是空的，那 first 也要指向新节点；否则让旧尾节点的 next 指向新节点。最后 size 加一，modCount 加一。

modCount是抽象类 AbstractList 里的字段，记录结构修改次数。add、remove、clear这些改变链表结构的操作都会让它自增。它存在的意义我放到后面的 fail-fast 机制里讲，这里先记住：遍历时结构不能变。

再看不带参数的remove()，它移除的是首节点：

public E removeFirst() { final Node<E> 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。

Iterator<String> 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 MyLinkedList<E> { private static class Node<E> { E item; Node<E> next; Node(E item) { this.item = item; } } private Node<E> head; private int size; public MyLinkedList() { head = null; size = 0; } }

这里不维护 tail，是因为我要演示的是一套纯单链表操作，加了 tail 很多逻辑会变简单，但也掩盖了边界处理的细节。等你把不带 tail 的写熟了，再加 tail 就是顺手的事。

3.2 头插法与尾插法的取舍

头插法最简单也最快，因为不需要遍历：

public void addFirst(E e) { Node<E> newNode = new Node<>(e); newNode.next = head; head = newNode; size++; }

注意这里有个经典错误：有人会先把 head 保存到局部变量再 new 节点，然后 head 指向新节点、新节点指向旧 head。两种写法都对，但上面这种更简洁。关键是顺序不能反：一定是先让新节点的 next 指向旧 head，再让 head 指向新节点。反过来的话，旧 head 就丢了，链表就断了。

尾插法需要遍历到最后一个节点：

public void addLast(E e) { Node<E> newNode = new Node<>(e); if (head == null) { head = newNode; } else { Node<E> 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 { Node<E> prev = node(index - 1); Node<E> newNode = new Node<>(e); newNode.next = prev.next; prev.next = newNode; size++; } } private Node<E> node(int index) { Node<E> 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; } Node<E> prev = node(index - 1); Node<E> 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() { Node<E> 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 Node<E> reverse(Node<E> head) { Node<E> prev = null; Node<E> cur = head; while (cur != null) { Node<E> next = cur.next; // 先保存下一个节点 cur.next = prev; // 当前节点指向前一个 prev = cur; // prev 前进 cur = next; // cur 前进 } return prev; // 最后 prev 就是新头 }

这里最容易被问倒的细节是：为什么需要 next 临时变量？因为当执行cur.next = prev之后，cur 原来的下一个节点就丢了，如果不提前保存，循环就没法继续。这个顺序我在纸上画过很多次，三个指针像推磨一样往前走，每次循环结束 prev 指向已经反转好的子链表的头，cur 指向还未反转部分的头。

递归法代码更短，但理解门槛高：

public Node<E> reverseRecursive(Node<E> head) { if (head == null || head.next == null) { return head; } Node<E> newHead = reverseRecursive(head.next); head.next.next = head; head.next = null; return newHead; }

递归的思路是：先反转后面的子链表，得到 newHead；然后把当前节点的下一个节点的 next 指回当前节点；最后把当前节点的 next 置空。这句“head.next.next = head”很多人想不通，我建议你在纸上画三个节点的链表，逐步展开递归栈，画一遍就懂了。需要提醒的是，链表很长时递归会导致栈溢出，生产环境我优先选迭代法。

4.2 快慢指针：找中点、判环、找相交点

快慢指针（也叫龟兔赛跑）是链表题的万金油。快指针每次走两步，慢指针每次走一步。找链表中点：快指针到底时，慢指针刚好在中点。

public Node<E> findMiddle(Node<E> head) { Node<E> slow = head; Node<E> fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } return slow; }

判环也是快慢指针的经典应用：如果有环，快指针必然会在某个时刻和慢指针相遇。

public boolean hasCycle(Node<E> head) { Node<E> slow = head; Node<E> 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(m+n)，空间 O(1)，比用哈希集合省内存，面试时更讨喜。

4.3 合并有序链表与链表排序

合并两个有序链表，标准递归解法：

public Node<Integer> merge(Node<Integer> l1, Node<Integer> 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 Node<Integer> sortList(Node<Integer> head) { if (head == null || head.next == null) return head; Node<Integer> mid = findMiddle(head); Node<Integer> rightHead = mid.next; mid.next = null; // 断开 Node<Integer> left = sortList(head); Node<Integer> right = sortList(rightHead); return merge(left, right); }

这个实现我用了很多次，注意mid.next = null那一步是切断链表的关键，很多人的归并排序写出来死循环，就是忘了在递归前把左右两半彻底分开。

5. ArrayList 与 LinkedList 选型：别再凭感觉了

5.1 复杂度对比表

面试时经常被问“ArrayList 和 LinkedList 有什么区别”，这里把复杂度整理成表，回答时直接照着说：

看到没有？add(index, e)和remove(index)两者都是 O(n)，只是 O(n) 消耗的地方不同。ArrayList 是搬移元素，LinkedList 是寻址。对于小数据集，ArrayList 因为缓存友好反而胜出。

我实际做过一个粗糙的基准测试：往一个长度 10 万的列表头部逐个插入元素，ArrayList 因为每次都要整体搬移，耗时接近 LinkedList 的几十倍；但如果是在列表中间位置插入，数据量在几万以内时，ArrayList 有时候反而更快。所以“LinkedList 适合频繁插入删除”这个结论，只适用于“你已经在目标位置，只需要做指针改动”的场景，很多网上说法是片面的。

5.2 实际场景下的真实表现

那么 LinkedList 到底该在哪里用？我的经验是三类场景。

第一类是当栈或队列用。LinkedList 实现了 Deque，push、pop、offer、poll都是 O(1)，两端操作非常顺滑。注意这里要优先用 ArrayDeque，它内存更紧凑、性能更好，LinkedList 的优势是允许 null 元素和没有容量限制。看情况选。

第二类是频繁在迭代过程中删除元素。用迭代器的 remove 方法，LinkedList 因为改的是指针，比 ArrayList 的搬移快不少。比如做一个在线用户列表，要频繁剔除超时连接，LinkedList 在中间删除时受到的影响更小。

第三类是实现 LRU 缓存。双向链表配合 HashMap，get 和 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 节点：

Node<E> dummy = new Node<>(null); dummy.next = head; Node<E> 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 的人高出好几个档次。