今天聊聊链表（Linked List）。学这玩意儿有啥用？别急，一个经典场景马上揭晓：LRU缓存淘汰算法。它可是链表大展拳脚的舞台！
想象一下你的书架（缓存）满了，新书来了，必须扔掉一些。扔旧的（FIFO）？扔看得少的（LFU）？还是扔最近没碰过的（LRU）？这就是缓存淘汰策略！如何用链表实现高效的LRU？ 带着这个悬念，我们发车！
一、链表 vs 数组：内存里的“住法”大不同
数组：住“集体宿舍” - 要求一大片连续的内存空间。申请100MB数组？必须找到一整块100MB的空地！即使总内存够，碎片太多也可能失败。
链表：住“分散公寓” - 通过指针（地址）把零散的内存块（结点）串起来。申请100MB链表？只要零散小空间总和够100MB就行！灵活性完胜。
二、五花八门的“小火车”：链表家族秀
链表家族成员不少，重点介绍三位主角：
单链表：单向寻宝图
插入/删除：在已知位置操作，只需修改相邻结点的指针（改“藏宝图”），O(1) 搞定！超高效。（想想在火车中间加挂或摘掉一节车厢，只需改前后连接钩）
查找（访问第k个）：只能从车头开始，一节一节往后数，“藏宝图”一张一张看，O(n) 较慢。（不知道第k节在哪，只能从头数）
车头（头结点）：记录起点地址，没有宝藏（不存数据），只指向第一节载物车厢。有了它，整列火车都能找到。
车尾（尾结点）：它的“藏宝图”指向
NULL
（空地），表示终点。结构：每个“车厢”（结点）装载
数据
+ 一张指向下一个车厢的“藏宝图”（后继指针next
）。特殊车厢：
操作特点：
循环链表：首尾相接的贪吃蛇
结构：本质是单链表，但车尾的“藏宝图”不指空地，而是指向车头！ 形成一个闭环。
优势：从车尾回找车头很方便。处理环形数据（如约瑟夫问题）代码更简洁优雅。（在环上，哪都是起点也是终点）
双向链表：自带前后视镜的豪华列车 ⭐️（更常用！）
查找前驱（前一个结点）：直接通过
prev
找到！O(1)。特定场景下删除/插入效率飙升：
有序链表按值查询：可以记录上次位置，决定向前(
prev
)还是向后(next
)查找，平均只需查一半！单链表：删
q
需要知道它前一个(p
)。只能从车头遍历找p
(直到p->next == q
)，O(n)。双向链表：通过
q->prev
直接拿到前驱p
！删q
只需改p->next
和q->next->prev
(如果有)，O(1)！情景1：删除“值等于X”的结点？单/双向都得O(n)遍历找X。
情景2：删除已知指针
q
指向的结点？在已知结点前插入：同理，双向链表O(1)，单链表O(n)。
next
：指向下一个车厢。prev
：指向上一个车厢。结构：每个“车厢”升级！装载
数据
+ 两张“藏宝图”：代价：多存一个指针，占用内存稍大。
巨大优势：双向遍历能力！
✨ 设计思想点睛：空间换时间
双向链表多用内存(prev
指针)，换来了关键操作的极致速度(O(1))。缓存（Cache）本身也是“空间换时间”的典范：用宝贵的内存空间缓存数据，换取远超硬盘/网络的访问速度！开发中，内存充足时优先考虑速度；内存紧张（如单片机）则需“时间换空间”。
三、链表 vs 数组：性能擂台赛
| 随机访问 | 数组 | ||
| 插入删除 | 链表 | ||
| 内存 | 链表 | ||
| CPU缓存 | 数组 | ||
| 内存开销 | 数组 | ||
| 内存碎片 | 数组 |
📍 选型指南：
数组： 数据量已知或变化小、频繁随机访问、追求极致性能/内存效率、CPU缓存友好、多维数据直观。
链表： 数据量未知或频繁变化、频繁在已知位置插入删除、需要动态扩容。Java的
LinkedList
(双向链表),LinkedHashMap
(双向链表+哈希表)就是链表实力的体现！
四、揭秘开篇：链表实现LRU缓存淘汰
核心思路：维护一个按访问时间排序的有序链表 (越近访问的越靠头)
访问数据X：
缓存未满：直接将X新结点插入链表头部。
缓存已满：
X在链表中 (缓存命中)：
X不在链表中 (缓存未命中)：
删除链表尾结点 (最久未访问)。
将X新结点插入链表头部。
找到X对应的结点。
将它从当前位置删除。
将X结点插入链表头部。(标记为最新访问)
优点：逻辑清晰，插入/删除头部尾部都是O(1)（双向链表优势尽显）。
缺点：判断X是否在缓存（查找）需要O(n)遍历链表。
优化方向 (预告)：结合哈希表(Hash Table)，记录数据位置，可将判断存在性及定位的操作降到O(1)！这就是更完美的LRU实现（后续讲哈希表细说）。
五、思考加油站
回文链表挑战：如何判断一个存储在单链表中的字符串是否是回文（正读反读一样，如"level"）？
你的思路？ 能否在 O(n) 时间和 O(1) 额外空间 内搞定？（提示：快慢指针找中点、反转后半部分链表再比较）
时空复杂度 你的方案是多少？
结语
链表，这列由指针串联起的“内存小火车”，以其非连续的存储、动态扩容的天赋，尤其在插入删除上的高效（O(1)），成为程序员手中对抗数据流动性的利器。理解了单链表的朴素、循环链表的巧妙、特别是双向链表“空间换时间”的智慧，你就能在数组与链表的抉择中游刃有余。下次面对缓存淘汰、频繁增删的场景，别忘了这列灵活的“小火车”！快用链表，让你的代码飞驰吧！🚄
