1. 为什么面试官总爱问LinkedList：先搞清楚链表到底是个什么结构

做Java开发的兄弟姐妹应该都有这种经历：刷面试题的时候，LinkedList和ArrayList的对比几乎是必考题，八股文里背得滚瓜烂熟——"ArrayList底层是数组，查询快增删慢；LinkedList底层是双向链表，增删快查询慢"。可真到了实际开发里，真敢在核心链路用LinkedList的人并不多，因为很多人心里清楚，自己其实没搞明白链表到底是怎么工作的，自然也就没法判断"增删快"这三个字到底什么时候成立。

先说链表最朴素的理解。数组就像一栋楼的固定房间，房间号是连续的，你拿到房号（下标）就能直接找到房间，所以查询快。但如果你要在1楼和2楼之间加一层楼（插入），整栋楼往上搬，代价很大。链表则像一列火车，每节车厢（节点）里装着两样东西：你的数据，以及下一节车厢连接处的地址（指针）。火车没有固定编号房间，你想找第100节车厢，只能从车头一节一节数过去。但如果你手里已经握着第50节车厢的把手，想在它后面挂一节新车厢，那只需要把第50节车厢的尾部连接器和第51节车厢的头部的连接器改一下就行，后面的车厢都不用动。

Java里的java.util.LinkedList就是这条"双向火车"——每个节点不只存指向下一个节点的指针，还存指向前一个节点的指针。这意味着它能从两头同时遍历，也正因如此，LinkedList不只是List，它还实现了Deque接口，可以当双端队列用。

// LinkedList内部节点结构（JDK 8/11/17 大同小异） 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源码的灵魂。理解它，你就能理解后续所有的增删改查为什么那样设计，也能理解为什么很多人说"LinkedList插入快"这句话，至少有一半场景是不成立的。

2. LinkedList源码拆解：insert和delete到底快在哪里、慢在哪里

我建议大家不要只背"增删快"这个结论，要真的去读一遍源码。JDK自带的LinkedList实现非常干净，总共没多少行核心逻辑，读一遍之后你对链表的理解会有一个质的提升。

2.1 尾插为什么是O(1)：维护了last指针

先看最基本的add(E e)方法，它默认是在尾部追加：

public boolean add(E e) { linkLast(e); return true; } 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; // 让原尾节点的next指向新节点 } size++; modCount++; }

注意这里的关键：LinkedList内部维护了first和last两个字段，所以尾插不需要从头遍历到尾部，直接就知道最后一个节点是谁，改两个指针就完事。这一点和很多人脑子里的"链表插入要遍历找到位置所以慢"其实是两回事——能不能O(1)插入，取决于你是否已经持有目标位置的节点引用。

同理，addFirst(E e)走的是linkFirst，也是O(1)。这也是LinkedList能当Deque用的底气。

2.2 按下标插入为什么通常是O(n)：一半的遍历省不了

LinkedList还有一个add(int index, E element)方法，这才是真正体现链表复杂度的操作：

public void add(int index, E element) { checkPositionIndex(index); if (index == size) { linkLast(element); } else { linkBefore(element, node(index)); } }

重点在node(int index)：

Node<E> node(int index) { // 小优化：index < size/2 就从头部找，否则从尾部找 if (index < (size >> 1)) { Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } }

JDK的工程师做了个小优化：如果插入位置在链表前半段，就从头往后找；在后半段，就从尾往前找。平均下来，找插入点的时间复杂度仍然是O(n)，只是常数项小了一半。你在中间插入一个元素，真正耗时的是"找到那个位置"，而不是"插入"本身。

再看最终干活的linkBefore：

void linkBefore(E e, Node<E> succ) { final Node<E> pred = succ.prev; final Node<E> newNode = new Node<>(pred, e, succ); succ.prev = newNode; if (pred == null) { first = newNode; // succ原来是头节点，现在newNode变成新头 } else { pred.next = newNode; } size++; modCount++; }

一旦你手里拿到了目标位置的节点succ，插入操作本身确实只要改四处指针引用（prev.next、succ.prev、newNode的prev和next），O(1)搞定。所以"LinkedList插入快"这句话精确的说法应该是：如果你已经持有某个节点的引用，在这个节点旁边插入一个新节点是O(1)的；但如果你按下标插入，寻找这个节点的过程本身是O(n)的。

这个区别极其重要，后面讲性能对比的时候你会看到，按中间下标插入，ArrayList反而经常不输LinkedList。

2.3 删除操作：同样的道理，先定位再解链

remove(int index)走的是unlink(node(index))，定位O(n)、解链O(1)。remove(Object o)则是从头到尾遍历找相等元素，找到后调用unlink。unlink做的事情就是把被删节点的前驱和后继互相连接，让被删节点彻底脱离链条：

E unlink(Node<E> x) { final E element = x.item; final Node<E> next = x.next; final Node<E> 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; }

顺带说一句，JDK在unlink里把被删节点的item置为null，是为了让GC能及时回收这个元素对象。在写自己手写链表的时候也要养成这个习惯，避免内存滞留。

2.4 get(int index)的真相：随机访问是链表最大的软肋

get(int index)调用的也是node(index)，所以时间复杂度是O(n)。这也就是那个经典结论"ArrayList查询快、LinkedList查询慢"的直接来源。但注意，这个"慢"只在按下标随机访问时成立。如果你是用迭代器从头到尾顺序遍历，LinkedList的next()每次都是O(1)，整体遍历也是O(n)，并不比ArrayList慢多少——当然，由于节点在内存里不连续，CPU缓存命中率差，实际遍历速度通常还是数组更快，但量级上是一样的。

3. LinkedList和ArrayList的真实差距：用一次基准测试说话

八股文背得再多，不如自己跑一次测试来得直观。我以前在项目里遇到过一个很有意思的性能问题，用一个固定大小的List频繁在某一位做数据插入，最开始用的是ArrayList，数据量几千的时候毫无感觉，等数据量涨到十几万，操作延迟肉眼可见地飙了上去。当时第一反应是"换成LinkedList就好了"，但换完之后性能并没有想象中提升那么大。后来做了基准测试，才发现问题没这么简单。

3.1 测试方案设计

我当时用的是JMH（Java Microbenchmark Harness），这是做Java微基准测试的正确姿势，千万别自己用System.currentTimeMillis()在main方法里循环个几万次就下结论，JIT编译、死代码消除等问题会让你得到完全错误的结果。

测试场景设了四个：

• 头部插入10万次
• 尾部插入10万次
• 中间插入10万次（位置取size/2）
• 按下标随机get 10万次

结果大致如下（JDK 17，默认JVM参数，意义看量级，别纠结绝对数值）：

3.2 为什么"中间插入"LinkedList的领先没想象中大

原因写在第二章了：按下标插入，LinkedList必须先O(n)定位。虽然双向链表做了前后半段选择，可以从中间向外扩散，但每次插入位置都是size/2时，恰好每次都先走到中点，定位成本稳定是n/2。ArrayList虽然要搬移一半数据，但这个搬移是System.arraycopy这种极其底层、经过JIT深度优化的内存拷贝操作，速度非常快。而链表的遍历是逐个节点跳转，每个节点都可能触发一次缓存未命中（cache miss），这比连续内存拷贝要贵得多。

所以这里有一个反直觉的结论：如果只是按下标在中间位置频繁插入，而且数据量在几万级别，ArrayList的表现往往不输LinkedList，甚至更好。LinkedList真正发挥优势的场景是：你手里已经握着某节点的引用（比如迭代器所在的位置），需要在它旁边反复插入、删除，也就是"局部频繁增删"的场景。

3.3 LinkedList的内存开销：一节点三对象

还有一个容易忽略的账——内存。ArrayList底层是一个连续数组，每个元素就是一个对象引用（如果是对象本身，那存的就是引用），数组本身有容量冗余，但冗余通常控制在1.5倍左右。LinkedList每个节点是独立的Node对象，除了存数据的item引用外，还有next和prev两个引用。

在64位JVM开启普通对象指针压缩（默认开启，-XX:+UseCompressedOops）的情况下，一个Node对象大致占用：对象头12字节（mark word 8字节 + klass pointer 4字节）+ item引用4字节 + next引用4字节 + prev引用4字节，再对齐到8字节，总共约32字节。而单纯一个大数组的每个槽位才占4字节（压缩引用）。也就是说，同样存100万个元素，LinkedList的纯结构性开销可能比ArrayList多出近30MB甚至更多，这还没算节点对象本身的分配与GC压力。

如果要存的是几千万量级的数据，这个差距就是几百MB级别。在内存敏感的服务里，选型时这笔账必须算。

4. 手写链表与面试高频题的应对思路

理解了源码，手写链表就变得很简单。面试官让你手写链表，考察的其实不是你会不会背API，而是你有没有真正理解指针操作。下面给出一套我自己常用的手写模板，以及三道最高频的链表算法题。

4.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 void addFirst(E item) { Node<E> newNode = new Node<>(item); newNode.next = head; head = newNode; size++; } public void addLast(E item) { if (head == null) { head = new Node<>(item); } else { Node<E> cur = head; while (cur.next != null) { cur = cur.next; } cur.next = new Node<>(item); } size++; } public E removeFirst() { if (head == null) throw new NoSuchElementException(); E value = head.item; head = head.next; size--; return value; } public int size() { return size; } }

注意这里面最容易出错的就是"头节点为空"和"只有一个节点"这两种边界状态。我见过很多人在手写时栽在removeFirst——头节点删掉之后忘了把新头节点从旧节点上解绑，或者没有处理链表变空的情况。写链表代码有一个通用心法：每次指针变动前，先问自己，如果链表为空、只有一个节点、只有两个节点，这段代码还成立吗？

4.2 反转链表：迭代法和递归法都要会

反转链表是面试链表题里出镜率最高的一道。迭代法的核心思路是三个指针：prev、cur、next，逐个把当前节点的next指向前一个节点：

public ListNode reverseList(ListNode head) { ListNode prev = null; ListNode cur = head; while (cur != null) { ListNode nextTemp = cur.next; // 先保存下一个节点，防止断链 cur.next = prev; // 掉头 prev = cur; // prev后移 cur = nextTemp; // cur后移 } return prev; }

递归法写起来更简洁，但对初学者来说也更难理解，关键是抓住"把子问题看成已经反转好的链表"这个视角：

public ListNode reverseList(ListNode head) { if (head == null || head.next == null) { return head; } ListNode newHead = reverseList(head.next); head.next.next = head; // 让下一个节点反过来指向自己 head.next = null; // 断开自己原来的next return newHead; }

如果面试时间充裕，建议两种都写一遍。面试官问你"时间复杂度多少"，两种都是O(n)；问"空间复杂度"，迭代法是O(1)，递归法是O(n)——递归栈的深度就是链表长度。这一个差异经常能决定你是否进入下一面。

4.3 检测环形链表：快慢指针为什么靠谱

判断一个链表有没有环，经典做法是快慢指针：slow每次走一步，fast每次走两步。如果链表有环，快指针最终一定会追上慢指针（想象两个人在圆形跑道上跑步，速度不同，迟早相遇）；如果没环，快指针会先到达null。

public boolean hasCycle(ListNode head) { ListNode slow = head; ListNode fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) { return true; } } return false; }

这道题我特别建议你自己动手推导一遍"为什么一定会相遇"，而不是背答案。因为面试官的追问通常很刁钻："如果快指针一次走三步，还一定会相遇吗？"答案是不一定，因为走的步长和环的长度可能出现同余的情况，导致永远错开。理解了原理，这类变形题你就能现场推理，而不是背一个结论。

4.4 删除倒数第N个节点：双指针一次遍历

要求只遍历一次链表，删除倒数第N个节点。思路是先让快指针走N步，然后快慢指针同步走，当快指针走到末尾时，慢指针恰好停在倒数第N个节点的前一个位置：

public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy = new ListNode(0); dummy.next = head; ListNode fast = dummy; ListNode slow = dummy; for (int i = 0; i < n; i++) { fast = fast.next; } while (fast.next != null) { fast = fast.next; slow = slow.next; } slow.next = slow.next.next; return dummy.next; }

这里有个实战技巧：设置dummy哑节点。因为如果要删的恰好是头节点，没有dummy的话需要单独处理"更新头节点"的逻辑，而有了dummy，一切变得统一，最后统一返回dummy.next即可。这个技巧在链表类题目里非常通用，几乎可以无脑套。

5. 实际开发中用LinkedList的几个反直觉经验

源码看完了，算法题也敲过了，最后聊点我在实际业务开发里踩过的坑和总结出来的判断标准。这些东西八股文里一般不写，但真到线上出问题了，能让你少熬几个夜。

5.1 千万别在for循环里用get(i)遍历LinkedList

这个坑我已经不止一次在同事代码里看到了：

// 错误示范：O(n²)的灾难 for (int i = 0; i < linkedList.size(); i++) { doSomething(linkedList.get(i)); }

每次get(i)都是O(n)，整个循环下来就是O(n²)。数据量一万还好说，到了十万百万，这个循环能把接口拖到秒级超时。正确姿势是用迭代器或者直接增强for循环：

for (String item : linkedList) { doSomething(item); }

增强for循环在LinkedList上走的其实是Iterator，next()操作只会让内部游标向后移动一次，不会re-search，所以整个遍历是O(n)。如果你在遍历过程中还需要删除元素，那就得显式用Iterator的remove()方法，或者用JDK 8之后的removeIf，千万不要在foreach里直接调用list.remove(...)，那会触发ConcurrentModificationException。

5.2 LinkedList是隐藏的队列和栈

很多人在需要用队列或栈的时候，第一反应是去搜"Java队列实现类"，搜到ArrayDeque或者PriorityQueue。但LinkedList其实就实现了Deque接口，所以它天生就是双端队列，完全可以当栈用：

Deque<String> stack = new LinkedList<>(); stack.push("a"); stack.push("b"); String top = stack.pop(); // b

也能当队列用：

Queue<String> queue = new LinkedList<>(); queue.offer("a"); queue.offer("b"); String head = queue.poll(); // a

这在业务代码里非常方便，不想引入额外依赖，又需要一个简单的FIFO或LIFO结构时，LinkedList一把梭。当然，如果你需要的是高并发场景下的队列，那就要考虑并发包里的ConcurrentLinkedQueue、LinkedBlockingQueue这些了，LinkedList不是线程安全的，多线程环境下并发读写必须自己做同步，否则数据错乱是必然的。

5.3 频繁在头部插入，LinkedList是王，ArrayDeque是性价比之王

如果业务场景是"需要在头部大量插入、尾部读取"这种典型的FIFO流式处理，LinkedList和ArrayDeque都能做。但实测下来，ArrayDeque因为底层是环形数组，内存紧凑、缓存友好，性能往往比LinkedList更好，而且内存占用小得多。所以如果只是当队列用，不需要按下标访问、不需要在中间插入，我的选择优先级是：ArrayDeque > LinkedList。

但如果你需要在头部插入的同时还能在中间做插入删除（比如实现一个LRU缓存改造版），那LinkedList的双向结构就派上用场了——这也是为什么LinkedHashMap实现LRU缓存的底层会有链表参与的原因。实际开发中，能用LinkedHashMap解决的就别自己手搓LinkedList，JDK帮你做好的那些边缘情况处理，自己实现很容易漏。

5.4 关于"链表适合增删"这个结论，我的最终判断标准

做了几年Java开发，踩过坑之后，我自己总结了一套简单的选型判断逻辑，分享给大家参考：

• 数据规模小（几百到几千），ArrayList和LinkedList差异可以忽略，选好维护的ArrayList，别折腾。
• 主要操作是按下标随机访问、或者需要频繁整体排序，无脑ArrayList。
• 已知某节点引用，需要在它旁边反复插入删除，LinkedList（或者更好的是java.util.concurrent包里的并发链表）。
• 需要当队列/栈用，优先ArrayDeque，除非你的元素本身是结构复杂的大对象，需要频繁删除中间节点。
• 内存敏感的大规模存储，优先ArrayList，链表的节点对象开销真的不小。

另外还有一个通用经验：不要不加测试就裸换容器。很多性能问题不是容器类型引起的，而是算法复杂度本身。比如你写了个O(n²)的遍历，换成LinkedList只会更差。先定位复杂度瓶颈，再谈选型，这才是正路。

5.5 手写链表时容易被忽略的边界条件

最后给正在准备面试或写课程作业的读者列一个边界条件自查清单，写链表代码之前先过一遍，能省掉大量debug时间：

• 链表为null时，代码是否能直接返回合理结果？
• 链表只有一个节点时，删除、反转操作是否成立？
• 删除头节点时，head引用是否正确更新？
• 删除尾节点时，前驱的next是否被置null？
• 插入到空链表时，first和last是否都被正确赋值？
• 使用亚节点时，最后返回值是否排除哑节点？
• while循环遍历时，条件是cur != null还是cur.next != null，想清楚再写。

说实话，链表这种数据结构，你光看书一百遍，不如自己在IDE里敲十遍。一个建议：把JDK的LinkedList源码从头读一遍，然后合上源码，自己照着linkLast、linkBefore、unlink各写一个方法，能一次通过，说明你是真理解了。读源码、手写、再对比源码找差距，这个循环走完，不管是面试还是实际开发，LinkedList都再不会成为你的短板。