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 NodeE { E item; // 实际存的数据 NodeE next; // 指向下一个节点 NodeE prev; // 指向前一个节点 Node(NodeE prev, E element, NodeE 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 NodeE l last; final NodeE 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)NodeE node(int index) { // 小优化index size/2 就从头部找否则从尾部找 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; } }JDK的工程师做了个小优化如果插入位置在链表前半段就从头往后找在后半段就从尾往前找。平均下来找插入点的时间复杂度仍然是O(n)只是常数项小了一半。你在中间插入一个元素真正耗时的是找到那个位置而不是插入本身。再看最终干活的linkBeforevoid 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; // succ原来是头节点现在newNode变成新头 } else { pred.next newNode; } size; modCount; }一旦你手里拿到了目标位置的节点succ插入操作本身确实只要改四处指针引用prev.next、succ.prev、newNode的prev和nextO(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(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; }顺带说一句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 测试方案设计我当时用的是JMHJava Microbenchmark Harness这是做Java微基准测试的正确姿势千万别自己用System.currentTimeMillis()在main方法里循环个几万次就下结论JIT编译、死代码消除等问题会让你得到完全错误的结果。测试场景设了四个头部插入10万次尾部插入10万次中间插入10万次位置取size/2按下标随机get 10万次结果大致如下JDK 17默认JVM参数意义看量级别纠结绝对数值操作场景ArrayListLinkedList说明头部插入10万次~2.3s每次都要System.arraycopy搬移全部元素~5msLinkedList完胜尾部插入10万次~8ms数组扩容均摊后开销很低~5ms差距很小中间插入10万次~1.1s每次搬移一半元素~430ms每次要遍历到中点LinkedList略快但远没有快两个数量级的惊艳感按下标随机get 100万次~8ms~2.1sArrayList完胜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 MyLinkedListE { private static class NodeE { E item; NodeE next; Node(E item) { this.item item; } } private NodeE head; private int size; public void addFirst(E item) { NodeE newNode new Node(item); newNode.next head; head newNode; size; } public void addLast(E item) { if (head null) { head new Node(item); } else { NodeE 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上走的其实是Iteratornext()操作只会让内部游标向后移动一次不会re-search所以整个遍历是O(n)。如果你在遍历过程中还需要删除元素那就得显式用Iterator的remove()方法或者用JDK 8之后的removeIf千万不要在foreach里直接调用list.remove(...)那会触发ConcurrentModificationException。5.2 LinkedList是隐藏的队列和栈很多人在需要用队列或栈的时候第一反应是去搜Java队列实现类搜到ArrayDeque或者PriorityQueue。但LinkedList其实就实现了Deque接口所以它天生就是双端队列完全可以当栈用DequeString stack new LinkedList(); stack.push(a); stack.push(b); String top stack.pop(); // b也能当队列用QueueString 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解决的就别自己手搓LinkedListJDK帮你做好的那些边缘情况处理自己实现很容易漏。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都再不会成为你的短板。