链表这个数据结构说出来你可能不信我面试过的人里面十个有八个能说出“链表是由节点组成的每个节点有数据和指针”但真让他手写一个单链表反转或者解释清楚JDK里LinkedList为什么用双向链表立马就露馅了。这不是背不背的问题是压根没把链表的“链”这个字理解透。这篇文章我不打算跟你念教科书我就以Java语言为例子从底层实现原理讲到实际开发中的坑再穿插一些面试必问的算法题和蓝桥杯这类竞赛里链表的高频用法。你跟着我把代码敲一遍把图画一遍链表这块就算彻底焊死了。1. 链表的本质认知与基础分类1.1 为什么链表不是一个“数组的替代品”很多人习惯把链表和数组放在一起对比本质上它们解决的是完全不同的问题。数组是连续内存空间上存储相同类型数据的结构而链表是零散内存块通过“指针”串联起来的结构。这个区别决定了它们各自的天赋和短板。拿我最喜欢举的例子来说数组就像电影院的连排座位每个座位编号固定你知道座位号就能一步到位坐过去随机访问O(1)。链表像是一个寻宝游戏每个宝箱里除了宝物还藏着一张纸条写着下一个宝箱的位置你要找第100个宝箱只能从第一个宝箱开始一张纸条一张纸条地找随机访问O(n)。但反过来如果在电影连排座位中间插进去一个人你得把后面所有人都挪一个位置数组插入O(n)而寻宝游戏里你只需要改一下前一个宝箱里的纸条让它指向新宝箱就行链表插入O(1)。这个特性在频繁增删的场景下是碾压级的优势。Java里ArrayList和LinkedList的取舍说白了就是在“读多写少”还是“写多读少”之间做权衡。正常业务里大多数是读多写少所以ArrayList用的远比LinkedList多但这不代表链表不重要——恰恰相反链表是后续学习树、图、LRU缓存、操作系统进程调度等一系列进阶知识的地基。1.2 链表家族的三大门派单链表、双链表、循环链表链表的形态就三种理解了这三种剩下的全是变体。单链表是最朴素的形态每个节点只有一个next指针指向后继节点。它的缺点是只能单向走你想找前驱节点没门只能从头再遍历一遍。我刚才说到的寻宝游戏就是单链表。蓝桥杯里很多题目用的都是单链表因为实现最简单逻辑最清晰。双链表在单链表基础上增加了prev指针指向前驱节点相当于每个节点都能前后走。代价是每个节点多存一个指针内存开销增加每次插入删除需要多维护一个方向的指针代码复杂度上升。JDK的LinkedList就是双向链表因为Java标准库要考虑通用性双向遍历的能力太重要了。循环链表则是把尾节点的指针指向头节点单向循环或者让头节点的prev指向尾节点双向循环形成一个闭环。这东西最经典的应用是约瑟夫环问题约瑟夫问题还有操作系统的进程调度轮转法Round-Robin。循环链表的好处是从任意节点出发都能遍历整个链表不存在“到头了”的边界判断。面试时候我特别喜欢问给你一个单链表怎么判断有没有环这题的基础就是循环链表的概念——如果链表内部自己串成了一个环那么从某个节点出发就永远走不完了。2. 动手实现一个可用的单链表2.1 节点类的设计与泛型思考写链表的第一件事就是定义节点类。我自己写的时候习惯用静态内部类因为节点这个概念只属于链表没必要暴露到外部去。public class MyLinkedListE { private static class NodeE { E data; NodeE next; Node(E data) { this.data data; } } private NodeE head; private int size; public MyLinkedList() { head null; size 0; } }这里有几个设计细节值得说一下。用泛型E而不是直接用Object是为了类型安全。你可以往链表里放任意引用类型的数据但取出来的时候不需要强转。比如LinkedListString里取出来的每个元素都编译期确定是String写代码的时候省心一百倍。head指针代表链表第一个节点。这里要注意我们常说的“头节点”有两种理解方式——一种是哑元节点dummy node它不存数据只是作为哨兵另一种是直接指向第一个数据节点。这两种设计各有优劣。哑元节点的好处是当你删除第一个数据节点时不需要特殊处理head的更新坏处是遍历的时候要跳过一个无意义的节点。我习惯用哑元节点写代码时边界条件能少一大半。public class MyLinkedListE { private static class NodeE { E data; NodeE next; Node(E data) { this.data data; } } // 哑元节点不存数据简化边界处理 private final NodeE dummyHead new Node(null); private int size; public MyLinkedList() { dummyHead.next null; size 0; } // ... }2.2 核心增删改查方法的实现有了哑元节点增删逻辑就清爽了很多。以在指定索引位置插入节点为例核心步骤就两步找到前驱节点然后修改指针。public void add(int index, E element) { if (index 0 || index size) { throw new IndexOutOfBoundsException(Index: index , Size: size); } NodeE prev dummyHead; // 找到索引为 index 的节点的前驱 for (int i 0; i index; i) { prev prev.next; } NodeE newNode new Node(element); newNode.next prev.next; prev.next newNode; size; }这段代码里最关键的就是最后三行。newNode.next prev.next让新节点先接管原来前驱节点的后继prev.next newNode再让前驱节点指向新节点。顺序绝对不能反如果先执行prev.next newNode原链表就从中间断了后面的节点全部丢失。删除操作比插入还简单只需要找到目标节点的前驱然后让前驱跳过目标节点public E remove(int index) { if (index 0 || index size) { throw new IndexOutOfBoundsException(Index: index , Size: size); } NodeE prev dummyHead; for (int i 0; i index; i) { prev prev.next; } NodeE target prev.next; prev.next target.next; target.next null; // 帮助GC size--; return target.data; }注意我设置了target.next null这是一个好习惯。被删除的节点如果还持有下一个节点的引用在某些极端场景下会阻碍垃圾回收。虽然现代JVM的GC算法已经很强了但这行代码成本极低而且能防止意外引用导致的诡异问题。查找和修改就更简单了就是从头一步步走走到目标索引返回数据public E get(int index) { checkIndex(index); NodeE cur dummyHead.next; for (int i 0; i index; i) { cur cur.next; } return cur.data; } public void set(int index, E element) { checkIndex(index); NodeE cur dummyHead.next; for (int i 0; i index; i) { cur cur.next; } cur.data element; }2.3 边界条件处理的三种致命错误链表代码出bug99%出在边界条件上。我总结三种最经典的手写链表错误你在自己写的时候一定要避开。第一种空链表访问。当你调用remove(0)删除链表的第一个元素时如果链表为空prev.next就是null你接着取target.next直接抛NullPointerException。所以索引合法性检查必须放在方法的第一行不要等用到了才想起来。第二种插入位置等于size时。add(size, element)意味着在链表末尾追加元素。漏掉这个场景是新手常犯的错误否则你就得额外写一个addLast方法或者让add的判断条件变成index size就把index强制改成size。第三种遍历时移动了head指针。很多初学者喜欢直接把head当作临时变量去遍历while (head ! null) { System.out.println(head.data); head head.next; }跑完之后head变成null了链表直接废掉了。正确的做法是复制一个临时引用NodeE cur head; while (cur ! null) { System.out.println(cur.data); cur cur.next; }这一点在产品代码里尤其致命因为你可能无意中把整个链表状态搞丢了而且排查起来非常隐蔽。3. 循环单链表的实现与应用实战3.1 循环单链表的结构特点与核心操作差异循环单链表就是在单链表基础之上让尾节点的next指回头节点或者哑元节点。它的实现差异非常小但是带来的语义变化却很大。对比维度普通单链表循环单链表尾节点指针null指向head或dummyHead遍历终止判断cur ! nullcur ! dummyHead绕回起点能否从任意节点遍历完整链条否能典型应用常规存储约瑟夫环、轮转调度在Java里实现循环单链表的节点类跟普通单链表完全一样唯一区别在于初始化时dummyHead.next dummyHead这样空链表也是自循环的。插入和删除时要注意所有“走到null”的判断都要改成“走到dummyHead”。public class CircularLinkedListE { private static class NodeE { E data; NodeE next; Node(E data) { this.data data; } } private final NodeE dummyHead new Node(null); private int size; public CircularLinkedList() { dummyHead.next dummyHead; size 0; } public void addLast(E element) { NodeE newNode new Node(element); NodeE tail dummyHead; while (tail.next ! dummyHead) { tail tail.next; } newNode.next dummyHead; tail.next newNode; size; } public void display() { NodeE cur dummyHead.next; while (cur ! dummyHead) { System.out.print(cur.data ); cur cur.next; } System.out.println(); } }注意这里遍历条件是cur ! dummyHead而不是cur ! null。如果没有这个判断你会在循环链表里无限循环下去这是所有循环链表新手都容易踩的坑。3.2 约瑟夫环问题的攻击方案约瑟夫环是循环链表的经典题目它的背景是这样n个人围成一圈从第k个人开始报数报到m的人出圈然后下一个人重新从1开始报数直到剩下最后一个人。问最后剩下的是谁。用循环链表解决约瑟夫环问题简直是降维打击因为“围成一圈”这个语义天然就是循环链表。基本思路是这样的构建一个包含n个节点的循环链表找到第k个节点作为起始位置循环报数m次把当前节点从链表中移除剩余一个节点时输出该节点数据画一下图你就明白了每次删除一个节点就是把这个节点的前驱的next直接指向它的后继。在循环链表里这就特别自然因为你不需要担心删除的是头结点还是尾节点大家本来就是一圈。核心删除逻辑public int josephus(int n, int k, int m) { // 构建循环链表节点编号1~n CircularLinkedListInteger list new CircularLinkedList(); for (int i 1; i n; i) { list.addLast(i); } // 这里简化处理使用数组模拟略 // 实际代码我会用ArrayList或直接数组模拟因为循环链表的 // Java实现要获取“当前节点的前驱”需求额外维护prev指针 // 篇幅原因不在这里展开完整代码后面附面试题部分有更实用方案 return 0; }说句实话比赛里真正手写一个循环链表类再去做约瑟夫环代码量不小。我推荐你熟练掌握“使用ArrayList模拟约瑟夫环”的技巧或者用LinkedList加“索引超过size就取模”的方式模拟环形。但前提是你必须理解循环链表的工作原理因为这是底层逻辑理解它你才能写出正确的模拟方案。3.3 循环链表在操作系统调度中的应用联想抛开算法题循环链表在真实工程里的最经典场景就是操作系统进程调度里的时间片轮转。每个进程是一个节点CPU按固定时间片轮流执行链表里的进程执行完一个就把指针往后移谁轮到谁就上CPU。当一个进程被创建就插入链表尾部一个进程结束就从链表里删掉。整个过程就是一个循环链表在裸奔。做开发的时候如果你不追求极端性能LinkedHashMap的accessOrder模式、游戏里的回合制系统、播放器的循环播放列表这些场景都能看到循环链表的影子。底层原理掌握了上层应用就是一通百通。4. JDK LinkedList源码级深度解析4.1 为什么JDK选择用双向链表而不是单向java.util.LinkedList是Java工程师日常接触最多的链表实现它的底层就是双向链表。为什么JDK的工程师不选单链表核心原因就一个LinkedList要同时提供高效的头部操作和尾部操作。LinkedList实现了Deque接口意味着它要做addFirst、removeLast、getFirst这一系列操作。如果用单链表addFirst和removeFirst是O(1)但addLast得遍历到链表末尾O(n)removeLast更惨你得找到尾节点的前驱才能删掉尾节点单链表没有prev指针只能从头走到尾O(n)。这性能是完全不能接受的。所以JDK的实现里每个节点都有prev和next两个指针头节点first和尾节点last也被独立维护。这样一来双端操作全部O(1)。看源码里的节点定义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; } }Node类里有三个字段数据、前驱、后继。构造方法接收前驱、数据、后继三个参数典型的双向链表节点。4.2 源码关键方法剖析与设计哲学看linkLast方法在尾部追加节点JDK源码是这样写的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; size; modCount; }这个方法的精彩之处在于它用局部变量l保存原来的尾节点。然后把新节点的prev指向lnext置为null。接着更新last为新节点。如果原来的尾节点是null说明链表当时是空的那么新节点也是头节点更新first否则让原尾节点的next指向新节点。注意那个modCount这是AbstractList里定义的快速失败fail-fast机制字段。当你用迭代器遍历LinkedList时如果有人在遍历过程中调用了add或remove改变了链表结构modCount会变化迭代器在下一次next()时就会抛出ConcurrentModificationException。这是Java集合框架一个非常重要的设计——它保证了迭代过程中的安全性代价是一定的运行时检查开销。再看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; }这段代码里有几个细节非常值得琢磨删除节点后把被删节点的prev、next、item都置为null这是帮助垃圾回收的好习惯。然后分四种情况处理删除的是头节点、删除的是尾节点、删除的是中间节点、链表只剩一个节点。每种情况对应的指针更新逻辑都不同必须一个一个想清楚。很多人在手写双向链表删除时出错就是没有系统性地分情况讨论。4.3 LinkedList和ArrayList的选型修罗场面试的时候你肯定被问过“什么时候用LinkedList什么时候用ArrayList”这个问题的标准答案大家都知道但我今天说点不一样的。先说结论绝大多数实际场景ArrayList是更好的选择。原因有三点。第一LinkedList虽然插入删除是O(1)但这是指“在已知节点位置的情况下”。如果你只知道索引你得先找到那个节点而查找本身是O(n)。所以list.add(5, element)在LinkedList里的整体复杂度其实是O(n)而不是O(1)。这一点常常被人忽略。第二LinkedList每个节点需要额外的两个指针16字节在64位JVM上更多存储相同数据的内存开销远大于ArrayList。如果数据量大这可能是灾难性的。第三CPU缓存友好性。ArrayList底层是连续数组遍历时CPU缓存命中率极高LinkedList的节点散落在内存各个角落每次访问都可能触发缓存未命中性能反而更差。那什么时候用LinkedList如果你需要频繁在链表头部插入删除、需要一个双端队列、或者你明确持有节点的引用需要做O(1)的删除操作这时候LinkedList才有用武之地。除此之外默认选ArrayList基本不会错。5. 高频实战场景与面试必考算法5.1 链表反转的双指针法与递归法链表反转是面试手撕代码环节的“开场热身题”几乎每个面试官都会考。它的要求很简单给定单链表头节点将链表完全反转返回新头节点。迭代法的思路特别朴素遍历链表把每个节点的next指向前一个节点。但要注意你指向前一个节点之后原来的next节点就丢了所以得先用一个临时变量保存。public ListNode reverseList(ListNode head) { ListNode prev null; ListNode cur head; while (cur ! null) { ListNode next cur.next; // 先保存后继 cur.next prev; // 反转指针 prev cur; // prev前进 cur next; // cur前进 } return prev; }代码只有几行但每一步画图都能对上。我当时学的时候老师给了个口诀“先存后继再改指向然后同步后移”。这个口诀我用了五六年了到现在面试突击的时候还是这么教别人。递归法会难理解一些它的核心思想是递归反转head.next为首的子链表然后把head接到反转后的链表尾部。public ListNode reverseListRecursive(ListNode head) { if (head null || head.next null) { return head; } ListNode newHead reverseListRecursive(head.next); head.next.next head; // 把head放到反转后的链表末尾 head.next null; return newHead; }递归法理解的关键在于head.next.next head这一步相当于让当前节点的下一个节点的next指回来。递归刚返回时head.next指向的是反转后链表的尾节点我们把它指回headhead就成了新的尾节点。递归虽然代码短但是栈深度等于链表长度链表太长容易StackOverflowError。工程上我推荐迭代法。5.2 快慢指针中间节点与倒数第K个节点链表寻找中间节点是快慢指针的经典应用定义两个指针speed和slow都从头出发快指针每次走两步慢指针每次走一步。当快指针到达链表末尾时慢指针正好在链表中间。public ListNode middleNode(ListNode head) { ListNode slow head; ListNode fast head; while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; } return slow; }这个技巧的原理其实就是一个数学问题速度差是1步/轮当快指针走了2k步到末尾时慢指针走了k步正好是从头到中点的距离。快慢指针还能解决“寻找倒数第K个节点”的问题。思路是快指针先走K步然后快慢指针同步走当快指针到达末尾时慢指针刚好在倒数第K个节点。public ListNode findKthFromEnd(ListNode head, int k) { ListNode fast head; ListNode slow head; // 快指针先走k步 for (int i 0; i k; i) { if (fast null) { throw new IllegalArgumentException(k exceeds list length); } fast fast.next; } // 同步前进 while (fast ! null) { fast fast.next; slow slow.next; } return slow; }这是我面试时非常喜欢出的变形题。很多人背了快慢指针的套路但一换场景就懵了。其实核心思想都是“制造距离差”理解了这一点什么找中间节点找倒数第K节点判断环形链表”都能举一反三。5.3 环形链表检测与环入口定位判断一个链表是否有环还是在快慢指针上做文章。如果有环快指针迟早会追上慢指针两个指针会相遇——这在物理上等价于“跑圈套圈”。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; }进阶版本是“找到环的入口节点”。做法是当快慢指针第一次相遇后把快指针放回头节点然后快慢指针都以一步的速度前进。当它们再次相遇时那个点就是环的入口。这个结论的数学推导不复杂假设头节点到环入口的距离为a环入口到相遇点的距离为b相遇点再走到环入口的距离为c也就是说环的长度是bc。第一次相遇时慢指针走了ab快指针走了abcb因为快指针走得更快在环里多绕了一圈半圈的。又因为快指针速度是慢指针的两倍所以距离也是两倍2(ab) abcb解出来正好是ac。也就是说从头节点到环入口的距离等于从相遇点继续走到环入口的距离。所以快指针从头开始、慢指针从相遇点开始都以一步速度走必然在环入口相遇。我当年第一次看到这个推导的时候觉得数学真的太优雅了。这也是为什么链表算法题能成为面试标配——因为它看起来简单但背后藏着数学逻辑能考察一个人的抽象思维。5.4 链表排序归并排序的链表版本数组排序我们熟悉的是快排、归并、堆排但链表排序有一个天然限制random access是O(n)所以快排的partition操作在链表上效率很差。归并排序不需要随机访问只需要prev和next的指针操作天然适合链表。单链表归并排序的思路分三步找到链表中点把链表分成两半递归排序两半合并两个有序链表找中点就用快慢指针上一步刚讲过。合并两个有序链表也是经典题直接用一个哑元节点dummy node简化逻辑public ListNode sortList(ListNode head) { if (head null || head.next null) { return head; } // 找到中点 ListNode slow head; ListNode fast head; ListNode prev null; while (fast ! null fast.next ! null) { prev slow; slow slow.next; fast fast.next.next; } prev.next null; // 断开链表 ListNode left sortList(head); ListNode right sortList(slow); return mergeTwoLists(left, right); } public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode dummy new ListNode(0); ListNode cur dummy; while (l1 ! null l2 ! null) { if (l1.val l2.val) { cur.next l1; l1 l1.next; } else { cur.next l2; l2 l2.next; } cur cur.next; } if (l1 ! null) cur.next l1; if (l2 ! null) cur.next l2; return dummy.next; }这里我特意用了dummy节点来承接合并结果的头节点这样就不需要单独处理“第一个节点是l1还是l2”的情况。哑元节点的用处在这个场景体现得淋漓尽致。6. 手写链表过程中的血泪教训与性能优化6.1 空指针与死循环的排查心法手写链表代码最常见的报错就是NullPointerException和程序卡死不退出死循环。空指针问题的高发区访问链表当前节点的next之前没判断当前节点是否为null删除链表的最后一个节点后没有把tail或head置为null获取getFirst()或getLast()时链表为空死循环问题的高发区循环链表的遍历条件写成了while (cur ! null)结果循环链表里压根没有null反转链表时指针移动顺序错了导致cur永远前进不了合并链表时忘了更新cur cur.next导致while循环一直处理同一个节点排查思路其实就一条画图。我到现在手写链表遇到bug第一反应就是在草稿纸上画链表结构图把每个指针在每一步的状态标出来基本一眼就能看出问题在哪。不要硬读代码人脑对指针状态转化的模拟能力是很差的。6.2 手写链表时的性能优化技巧如果你在写一个高并发的链表实现或者参加算法竞赛以下几个优化点值得关注。第一减少冗余遍历。你每次get都从头遍历是O(n)但你如果只是遍历一遍处理数据就用一个循环拿next就行了不要用带索引的for循环加get——因为那会是O(n²)的时间复杂度。惰性删除。链表删除节点本身O(1)但如果目标是“按值删除”你得先找到这个值所在节点O(n)躲不掉。如果删除频率特别高可以考虑用空间换时间维护一个HashMapE, NodeE映射值直接定位到节点达到O(1)删除。第三减少对象分配。链表的每个节点都是独立对象频繁插入删除会不断创建和废弃对象给GC增加大量压力。竞赛里如果内存和时间很紧张可以考虑用数组模拟链表静态链表把所有节点放在对象数组里用int类型的next字段代替引用。这在Java里是一个极其重要的性能技巧蓝桥杯遇到大规模链表模拟题时非常实用。数组模拟链表的示意class StaticLinkedList { int[] data new int[MAX_SIZE]; int[] next new int[MAX_SIZE]; // freeList 表示空闲节点链表 int head -1; int free 0; // 类似“对象池”的思想预先分配节点空间避免频繁new }用数组模拟链表所有节点都在连续内存里缓存友好性大幅提升而且节点回收不需要GC手动维护一个空闲链表就行。这是从“面向对象思维”切换到“面向性能思维”的关键一步。6.3 蓝桥杯与竞赛场景的链表答题模板蓝桥杯这类竞赛中链表题不会让你写一个庞大的链表类而是倾向于考察你“用链表思维解决具体问题”的能力。我的建议是比赛时直接用LinkedList或者干脆用数组模拟不要现场手写链表类。手写节点类浪费时间不说还容易在边界条件上翻车。真正需要手写节点的场景是面试——面试官就是想看你处理指针的功力。如果确实需要手写链表记住这几个模板模板一遍历链表public void traverse(ListNode head) { for (ListNode cur head; cur ! null; cur cur.next) { // 处理 cur.val } }模板二删除目标节点给定前驱public void deleteAfter(ListNode prev) { if (prev.next null) return; prev.next prev.next.next; }模板三在指定节点后面插入public void insertAfter(ListNode node, int value) { ListNode newNode new ListNode(value); newNode.next node.next; node.next newNode; }这三个模板几乎可以组合出链表90%的操作。记住它们再配合上面讲到的快慢指针、翻转、归并竞赛和面试基本不会卡壳。7. 链表学习的进阶路线与扩展视野7.1 从单链表到跳表的思维跃迁如果你已经把链表吃透了我建议你了解一下跳表Skip List。跳表是在链表基础上增加了多级索引让查找从O(n)变成O(log n)。Redis里的有序集合就用了跳表。它的核心思想是用空间换时间在原始链表之上增加一层层稀疏索引查找时从最高层索引逐级向下跳过大片不需要遍历的节点。跳表是所有数据结构里“性价比”最高的一个原理不复杂实现也不难但一旦掌握你对有序数据结构的理解会上一个台阶面试聊起来也非常加分。7.2 内存层面理解链表的代价在JVM里链表节点是散布在堆内存中的对象每个对象还有对象头mark word class pointer的开销。64位JVM下一个NodeInteger对象可能占24字节甚至更多而int只有4字节。如果你要存储大量小数据链表的空间浪费是非常惊人的。这就是为什么很多高性能框架如Netty、Disruptor宁愿用预分配数组游标的方式来实现“看起来像链表”的结构也不直接使用LinkedList。理解了内存布局你才能理解工程里面那些看着很奇怪的设计。7.3 链表在LFU缓存算法中的应用LeetCode上一道经典题是LRU缓存机制146题。它的最优解是HashMap 双向链表。HashMap负责O(1)定位节点双向链表负责维护节点间的访问顺序。每次访问一个节点把它从链表中断开再移动到链表头部这样链表尾部就是最久未使用的节点淘汰时直接删尾部即可。还有一个LFU最不经常使用缓存用HashMap 多个双向链表实现每个频率对应一条链表。这种设计把“频率计数”和“访问时间”两个维度都用链表表达了。如果你能把这两道题吃透链表就算出师了。它们不仅考查链表操作还考查多个数据结构之间的协作是综合性很强的实战练习题。链表这个东西看着简单实际写起来全是细节。我在带新人的时候经常说一句话“数组是天赋链表是手艺。”数组天生支持随机访问那是语言和硬件给的链表的一切都要你自己维护一个指针错了就全盘崩溃。但也正因为如此写完一个健壮的链表结构你的逻辑思维和管理复杂状态的能力就真正上了一个台阶。别光看去敲代码。纸上画一画IDE里跑一跑这个坎过去了后面的树、图、堆你都会学得轻松得多。