很多人写了好几年Java，真给他一个面试题“手写一个链表”，反而容易卡壳。平时业务代码里全是ArrayList和HashMap，链表这东西，要么是八股文里背过“增删快、查询慢”，要么是刷题网站里见过“反转链表”，真到自己动手从零实现一遍，细节问题就全冒出来了。
这个主题看起来基础，但它串起来的点其实非常多：泛型、内部类、引用传递、边界条件、迭代器、复杂度分析，全都能在里面找到落脚点。把这篇文章看完，你能从零写出一个可以增删改查的单链表，能看懂JDK里LinkedList的核心源码逻辑，还能顺手把“链表反转”“快慢指针找中间节点”这类高频面试题给过了。整个过程不依赖任何框架，干干净净的Java基础代码，跟着敲一遍，收获比看十遍八股文都大。
1. 先说清楚：为什么项目里已经有LinkedList，还要自己手写一份？
很多人的第一反应是：JDK自带的java.util.LinkedList不香吗？现实是，面试要你手写，不是因为你不会用API，而是要确认你有没有真正理解链式存储结构的内存模型和指针操作。
1.1 LinkedList的基本盘：双向链表怎么运作
JDK里的LinkedList是一个双向链表，每个节点除了存数据，还持有两个引用：一个指向前一个节点（prev），一个指向后一个节点（next）。头结点的prev是null，尾节点的next是null，链表靠这两个null作为边界。
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; } }这是LinkedList源码里的核心内部类。注意它的访问修饰符是private static class，用static修饰是因为内部类不依赖外部类的实例，用private是因为这个节点类型是LinkedList的实现细节，外部完全不需要感知。
它还有个first和last指针，分别指向头尾节点。插入和删除的时候，只需要调整相邻节点的引用，不需要像数组那样搬移元素。但“增删快”是有前提的——你得先找到位置，而查找是O(n)的。所以“LinkedList增删快”这个说法，准确讲是“在已知节点位置的情况下，增删快”，无脑在高频业务里用它替代ArrayList，往往更慢。
1.2 自己动手的价值在哪
自己实现一遍链表，至少能逼你搞清楚下面这几件事：
第一，节点和数据是分离的。数组是一整块连续内存，链表是零散节点靠引用串起来。这个差异决定了插入删除的代价完全不同。
第二，引用赋值不是“复制”。node.next = node.next.next这句话到底干了什么，很多人画图能画明白，一写代码就懵，就是因为对引用传递的理解停留在表面。
第三，边界条件必须单独处理。操作空链表、操作头节点、操作尾节点、链表只有一个节点，这些情况如果不单独处理，轻则空指针，重则直接把链表结构搞坏。
自己动手写过之后，回头再看LinkedList源码，就能看出很多设计上的讲究。比如它为了性能单独维护了first和last两个指针，比如它通过modCount实现fail-fast迭代器，这些都是在基础链表之上做的工程化优化。
2. 手写链表前的“为什么”：设计取舍与易错点
动手写代码之前，先把几个关键决策想清楚。这些决策直接影响代码的复杂度，也直接决定了你在面试时给面试官留下的印象。
2.1 从单链表入手：节点定义为什么是静态内部类
我建议先写单链表，不要一上来就怼双向链表。单链表每个节点只有一个next指针，逻辑最简单，最适合用来理解链式存储的本质。等单链表完全吃透了，再看双向链表就是多一个prev指针的事。
节点定义我用静态内部类：
public class MyLinkedList<E> { private static class Node<E> { E data; Node<E> next; Node(E data) { this.data = data; } } private Node<E> head; private int size; }用static修饰内部类，核心原因是内部类Node不需要访问外部类的成员变量。如果不加static，编译器会隐式给Node添加一个指向外部类实例的引用，意味着每创建一个Node对象都会多出一个不必要的内存占用。在链表这种高频创建小对象的场景里，这个浪费是实打实的。而且从语义上讲，一个链表节点不依赖链表对象而存在，用static更合理。
head指向第一个节点，size记录链表长度。有人喜欢再维护一个tail尾指针，让尾插变成O(1)。单链表里如果只有head，尾插必须遍历到最后一个节点，复杂度O(n)。维护tail之后，尾插直接O(1)。建议一开始只维护head，把基本操作都跑通，然后再想优化的事儿加tail，一步到位容易把自己绕晕。
2.2 对外暴露哪些方法才够用
一个“能用的链表”，至少得覆盖这几个动作：
- 插入：头插、尾插、指定位置插入
- 删除：按值删、按位置删
- 查询：按位置查、判断是否包含某值
- 修改：更新指定位置的值
- 遍历：把链表转成数组或按顺序打印
- 辅助：获取长度、判断是否为空、清空链表
别贪多。那些花里胡哨的方法背后都是同一套引用操作逻辑，把核心几个吃透，剩下的都是排列组合。
2.3 复杂度的账要算清楚
写代码的人必须能说清每个操作的复杂度，这是基本功，也是面试必问题。
| 操作 | 单链表（仅维护head） | 单链表（维护head+tail） | 说明 |
|---|---|---|---|
| 头插 | O(1) | O(1) | 只需要让新节点指向原head，再更新head |
| 尾插 | O(n) | O(1) | 只维护head时必须遍历到最后一个节点 |
| 指定位置插入 | O(n) | O(n) | 遍历到目标位置前一个节点 |
| 按值删除 | O(n) | O(n) | 需要遍历找到目标节点的前驱 |
| 按位置查询 | O(n) | O(n) | 只能从头一个个走 |
| 反转 | O(n) | O(n) | 每个节点都要改指针 |
所以当面试官问“为什么链表插入快”时，最严谨的回答是“在已知前驱节点的情况下，插入操作本身只需要常数级次数的指针操作，不需要搬移元素”，而不是简单地说“链表插入就是快”。
另一个必须注意的复杂点：对于单链表，删除任意节点的前提是找到它的前驱节点。因为你只能从head往后走，没有prev指针，无法直接拿到前驱。这就是为什么按值删除、按位置删除都是O(n)——时间主要花在“找前驱”上，真正修改指针的操作其实只涉及常数次。
3. 核心功能实现：从零写一个能用的单链表
前面的设计问题想清楚了，下面直接进入完整实现。我会把代码分成几个小块，每块配合说明为什么这么写。
3.1 骨架：成员变量、构造器、边界工具方法
public class MyLinkedList<E> { private static class Node<E> { E data; Node<E> next; Node(E data) { this.data = data; } } private Node<E> head; private int size; public MyLinkedList() { head = null; size = 0; } public int size() { return size; } public boolean isEmpty() { return size == 0; } }这里有三个细节值得注意。
第一，head = null在构造器里其实可以不写，因为成员变量默认就是null，但显式写上能让代码的意图更清楚，尤其是给初学者看的代码，最好别依赖默认值这种隐式行为。
第二，size是唯一的“数据可信来源”，遍历链表统计节点数这种事不要做。这就好比你钱包里的钱，应该以账本记录为准，而不是每次花钱都翻一遍钱包数一遍。维护好size，是所有操作正确性的基础。
第三，为了后续操作方便，我会写一个内部校验方法：
private void checkPositionIndex(int index) { if (index < 0 || index > size) { throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size); } }注意插入时index可以等于size（表示在尾部追加），但查询、删除、修改时，index必须满足0 <= index < size。这两个边界条件不一样，需要单独写校验逻辑。
3.2 插入操作：头插、尾插、指定位置插入
头插是最简单的，新节点的next指向原head，然后更新head指向新节点，size加一。
public void addFirst(E e) { Node<E> newNode = new Node<>(e); newNode.next = head; head = newNode; size++; }这里有一个新手很容易犯的错：先改head再操作newNode。如果写成head = newNode; newNode.next = oldHead;，第一步就把原来的链给丢了，oldHead都找不到了。正确的顺序一定是：先把新节点挂到原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++; }注意判断空链表的分支。如果head为null，直接让head指向新节点；如果不为空，就遍历到next为null的节点。这个遍历条件cur.next != null是关键——它保证循环结束时cur是最后一个节点。如果写成cur != null，循环结束时cur已经变成null了，没法给null的next赋值，会空指针。
指定位置插入是含金量最高的一个操作，它要求你找到目标位置的前一个节点：
public void add(int index, E e) { checkPositionIndex(index); if (index == 0) { addFirst(e); } else { Node<E> prev = head; for (int i = 0; i < index - 1; i++) { prev = prev.next; } Node<E> newNode = new Node<>(e); newNode.next = prev.next; prev.next = newNode; size++; } }为什么遍历到index - 1而不是index？因为单链表插入的核心动作是：新节点指向prev的下一个，prev指向新节点。也就是说，你手里必须有目标位置的前驱节点，才能把新节点“焊”进去。示例：要在index=2的位置插入，需要找到index=1的节点，让它的next指向新节点，同时新节点的next指向原index=2的节点。
这里同样有那个经典的顺序问题：先接新节点指向后继，再让前驱指向新节点。如果顺序颠倒，先把prev.next改成newNode，原来prev.next指向的那个节点就找不到了。这就像你要在队伍里插队，得先让新人拉住后面人的手，再让前面的人松开后面人的手，顺序错了队伍就断开了。
3.3 删除操作与数据回显
删除操作的核心同样是找前驱。按位置删除：
public E remove(int index) { checkElementIndex(index); Node<E> target; if (index == 0) { target = head; head = head.next; } else { Node<E> prev = head; for (int i = 0; i < index - 1; i++) { prev = prev.next; } target = prev.next; prev.next = target.next; } size--; return target.data; }删除头节点时直接让head指向head.next，被删除的旧节点因为没有引用指向它，会被GC自动回收。删除非头节点时，让前驱节点跳过目标节点直连后继节点。
有个问题经常被忽略：被删节点的next引用要不要置空？单链表里其实无所谓，因为没有任何引用指向这个节点了，整个节点都会被回收。但如果是双向链表删除节点，建议把node.prev、node.next都置null，一是避免“A节点虽然已在链上摘除，但还引用着链表里的节点”，二是方便GC。
按值删除需要遍历找目标，同时记录前驱：
public boolean remove(Object o) { if (head == null) { return false; } if (o == null ? head.data == null : o.equals(head.data)) { head = head.next; size--; return true; } Node<E> prev = head; while (prev.next != null) { Node<E> cur = prev.next; if (o == null ? cur.data == null : o.equals(cur.data)) { prev.next = cur.next; size--; return true; } prev = prev.next; } return false; }这个方法的健壮之处在于同时处理了o == null和o != null两种情况。链表里允许存null值，删除时不能直接用o.equals(node.data)，否则o为null时直接空指针。三元表达式o == null ? head.data == null : o.equals(head.data)就是标准解法。
查询和修改相对简单，按位置遍历就好：
public E get(int index) { checkElementIndex(index); Node<E> cur = head; for (int i = 0; i < index; i++) { cur = cur.next; } return cur.data; } public E set(int index, E element) { checkElementIndex(index); Node<E> cur = head; for (int i = 0; i < index; i++) { cur = cur.next; } E old = cur.data; cur.data = element; return old; }这个方法里的checkElementIndex和之前的checkPositionIndex不一样，因为它不允许index等于size，单独写一个：
private void checkElementIndex(int index) { if (index < 0 || index >= size) { throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size); } }最后加一个toArray方法，方便调试和验证结果：
@Override public String toString() { StringBuilder sb = new StringBuilder(); sb.append('['); Node<E> cur = head; while (cur != null) { sb.append(cur.data); if (cur.next != null) { sb.append(", "); } cur = cur.next; } sb.append(']'); return sb.toString(); }toString里用cur.next != null判断是否要加逗号，这块逻辑虽然不复杂，但新手经常写错导致多一个尾逗号或者少一个元素。
3.4 高频算法一：反转链表
手写链表最常见的算法考察就是反转。面试考这个，考察的不是你背没背过答案，而是你对指针操作的理解程度。
迭代法是最优解，三指针原地反转：
public void reverse() { Node<E> prev = null; Node<E> cur = head; while (cur != null) { Node<E> next = cur.next; // 先保存下一个节点 cur.next = prev; // 反转当前节点的next prev = cur; // 前驱指针前进 cur = next; // 当前指针前进 } head = prev; // 最后prev落在原链表的尾部，也就是新链表的头部 }这个算法的精妙之处在于next变量。如果不先把cur.next存起来，cur.next = prev执行之后，原来的后继节点就找不到了，遍历也就断了。所以循环体里的第一件事一定是保存后继。
可以这么记忆：保存、反转、前进、前进。四个动作一个都不能少，顺序也不能乱。很多人卡在“最后head应该等于什么”——循环结束时，cur已经遍历到null，prev正好指向原链表的最后一个节点，它成为新链表的头节点。
递归写法虽然看起来简洁，但面试和实际开发我都不推荐，原因在后面问题排查那一节会详细说。
3.5 高频算法二：快慢指针找中间节点
另一个高频题是“查找链表的中间节点”。思路是用两个指针同时从head出发，快指针每次走两步，慢指针每次走一步。快指针走到末尾时，慢指针正好在中间。
public E findMiddle() { if (head == null) { return null; } Node<E> slow = head; Node<E> fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } return slow.data; }循环条件fast != null && fast.next != null必须两个都判断。链表长度为奇数时，fast会走到最后一个节点（fast.next为null）；长度为偶数时，fast会走到null（fast为null）。少了任何一个判断，都会空指针。
这个算法的应用场景远不止找中间点。判断链表是否有环也是用同样的思路，快慢指针，如果快指针最终追上慢指针，说明有环。这也算链表题里最经典的“双指针”套路。
4. 优化与进阶：双向链表、哨兵节点与真正读懂LinkedList源码
单链表摸透之后，往上的路还有几条。每条路都能加深对数据结构本身的理解。
4.1 双链表实现要点
双链表只是每个节点多加一个prev引用。插入时需要同时维护prev和next两边的连接：
private static class Node<E> { E data; Node<E> prev; Node<E> next; }双向链表最大的优势是：删除节点时不需要找前驱，因为当前节点就有prev指向它。但代价是每个节点多一个引用，内存占用上升，而且所有操作都要同时维护两条链，出错几率变大。JDK的LinkedList就是双向链表，因为它需要在任意位置快速插入删除，同时要支持从尾部往前遍历。
自己实现双链表时，最核心的坑是：插入时，四根引用要全部接好。以尾部插入为例，你得处理newNode.prev = oldTail; newNode.next = null; oldTail.next = newNode; tail = newNode;，漏掉任何一个，链表结构就是坏的。
4.2 哨兵节点解法：如何避免边界判断
哨兵节点（dummy node）是一种很有意思的优化手法。它不存数据，固定在链表头部，真正的数据节点都在它后面。
private final Node<E> dummy = new Node<>(null); public void addLast(E e) { Node<E> cur = dummy; while (cur.next != null) { cur = cur.next; } cur.next = new Node<>(e); size++; }有人觉得哨兵节点多此一举，但它的好处非常实在：处理空链表时，不需要单独写if判断。有了dummy，空链表等价于dummy.next == null，插入时直接让dummy.next指向新节点即可，不需要问“head是不是null”这种问题。所有操作都统一成“在某个节点之后插入/删除节点”，边界情况自然消失。
刷题时哨兵节点更是神器。比如“删除倒数第N个节点”这类题，有了dummy，就不需要处理“删除头节点”这个特殊分支，代码统一得不得了。面试时能主动提出用哨兵节点优化，是加分项。
4.3 回到源码：LinkedList与ArrayList的选型，你真的选对了吗
聊了这么多手写，说说实际工程里的选型问题。这其实是对链表理解的一次综合检验。
很多人迷信“链表增删快”，在业务代码里无脑用LinkedList，这是最常见的误区。ArrayList是基于动态数组实现的，它的add(E)方法是均摊O(1)的——数组扩容是有代价，但扩容是偶尔发生的，平摊下来并不慢。而且ArrayList的get是O(1)，遍历时因为CPU缓存友好，实际速度往往比LinkedList快得多。
LinkedList真正有优势的场景是：你需要频繁在链表头部插入，或者你需要频繁在已知位置插入删除。如果你的代码是“查询少改，遍历多”，ArrayList基本不会输。举个例子，一个频繁在头部插入、偶尔随机访问的消息队列场景，LinkedList合适；一个以遍历和按下标访问为主的应用，ArrayList更合适。
4.4 线程安全的坑：LinkedList为什么不安全，又该怎么修
LinkedList和ArrayList一样，都不是线程安全的。并发环境下多个线程同时add，轻则数据不一致，重则直接破坏链表结构。
典型场景是：线程A正在遍历链表，线程B从尾部插入一个节点，A就可能抛出ConcurrentModificationException。这是LinkedList内部的modCount在起作用——迭代器创建时会记录当前的modCount，一旦发现迭代期间modCount被修改，立即抛异常。
解决方案有这几个层次：
第一，方法级同步：直接用synchronized包装操作，或者用Collections.synchronizedList(new LinkedList<>())。简单，但锁粒度太大，并发性能差。
第二，使用并发容器：ConcurrentLinkedQueue是一个基于CAS的无界线程安全队列，它才是真正适合高并发场景的链表实现。它的入队出队都是lock-free的，线程安全靠的是CAS操作，性能远胜于加锁方案。
第三，读写分离：如果读多写少，可以用CopyOnWriteArrayList，但它底层是数组，不是链表，只是提个思路。
知道什么时候该选哪个容器，比背下所有API都强。
5. 面试环节最容易翻车的几个点与排查思路
手写链表的代码其实就那么几十行，但能把这几十行写对、写稳、解释清楚，就是不小的本事。这一节把常见的坑和面试追问整理成速查表，方便你临阵磨枪。
5.1 问题速查表
| 场景 | 报错/症状 | 根因 | 解决方案 |
|---|---|---|---|
| 插入时先改前驱再操作新节点 | 链表断成两截，部分数据丢失 | 前驱节点原来指向的后继节点找不到了 | 先让新节点指向后继，再让前驱指向新节点 |
遍历条件写成cur != null | 操作完最后一个节点后空指针 | 循环结束时cur已经为null | 用cur.next != null，保证cur停在最后一个节点 |
| 删除时没有维护size | get/remove越界或遍历多了个元素 | size和实际节点数不一致 | 所有增删操作必须同步更新size |
| 并发add触发ConcurrentModificationException | 遍历时报错 | modCount被修改 | 用并发容器，或在迭代时避免结构性修改 |
| 递归反转大链表导致StackOverflowError | 栈溢出 | 递归深度=链表长度 | 用迭代法三指针反转 |
| 双向链表删除后节点还引用着其他节点 | 内存无法回收 | 删掉的节点仍持有引用 | 将node.prev和node.next置null |
5.2 断链为什么会发生：一次最常见的报错复盘
我说一个实际调试时最崩溃的场景。写完add(int index, E e)之后，我测试头插、尾插都没问题，一插入到中间位置，遍历打印发现链表后半段全丢了。
当时代码如下：
Node<E> newNode = new Node<>(e); prev.next = newNode; // 先改了前驱的next newNode.next = prev.next; // 再让新节点指向"原后继"第二步取prev.next的时候，它已经是newNode自己了，等于新节点指向自己，自己把自己绕成一个环，原来的后半段就丢了。这个bug根本不报错，只有遍历或get的时候发现长度不对。
所以我把这个顺序问题拔高到“手写链表第一坑”的位置。凡是插入操作，必须先接后继，再连前驱；凡是写链表相关代码，脑子里先画图，再动代码。调试的时候不要靠猜，把链表整个打印出来，一步步走，问题很快就能定位。
5.3 面试追问：从手写代码到原理深度，几个值得再深入的方向
如果面试官在你写完链表之后继续追问，大概率会往这些方向带：
追问1：“你的头插复杂度是多少？为什么是O(1)？”答：因为头插只需要新节点指向原head，然后将head更新为新节点，和链表长度无关。
追问2：“删除指定节点，但只给你这个节点的引用，不给头结点，能不能做到O(1)？”答：单链表做不到，必须找前驱。但有一个取巧的解法叫“狸猫换太子”——把后继节点的值复制到当前节点，然后删除后继节点。需要注意如果目标节点是尾节点，这个技巧会失效。面试时能说出这个解法，已经很见功力了。
追问3：“环的入口节点怎么找？”答：先用快慢指针判断是否有环，然后让一个指针从头出发，一个从相遇点出发，两个都走一步，再次相遇的位置就是环的入口。这个结论可以用数学推导出来，值得自己推一遍。
追问4：“LRU缓存淘汰算法了解过吗？”答：LRU的核心数据结构就是“哈希表+双向链表”。哈希表负责O(1)查找，双向链表负责维护访问顺序。每次访问一个节点，把它移到链表头部；缓存满时，淘汰链表尾部节点。这个组合是面试常客，手写一个LinkedHashMap版的LRU，是中级工程师的基本功。
这些方向不是我拍脑袋列的，它们都直接来自真实的Java岗位面试题库。如果你打算准备面试，链表的手写题是最适合用来建立信心的——它不像红黑树那么复杂，也不像动态规划那么烧脑，但足够考察一个人的基本代码功底。
5.4 手写代码的工程化小习惯
最后分享几个我自己的经验，都是踩坑踩出来的：
第一，不要在代码里写“能跑就行”的逻辑。链表这种基础结构，代码质量直接反映态度。变量命名做到见名知意，循环条件写清楚，这些都是基本功。
第二，每次修改链表之后，建议马上用toString()验证一下。我写链表十次有八次是在toString上发现问题——不是多了个节点，就是丢了段链。快速打印，快速定位，比对着代码干瞪眼效率高得多。
第三，边界测试要认真做。空链表增删、只有一个节点的链表删除、在末尾插入、删除头节点、删除尾节点，这五类case必须全部跑通。很多看似正确的代码，一测边界就原形毕露。
第四，手写时先自己画一张指针变化图。不需要多精美，能标清楚每一步谁指向谁就行。代码写不下去的时候，看图找问题是最高效的排查方式。
链表这个话题，代码量不大，但能讲出的深度可以一直延伸到工程选型、并发容器、算法面试。把这篇文章里的代码自己敲一遍，该踩的坑踩一遍，背后这些“为什么”想明白一遍，再去应对链表相关的面试题和日常开发，心里就会踏实很多。
