1. 为什么我坚持手写链表，而不是直接用 Python 列表？
你有没有在深夜调试一个性能瓶颈时，盯着timeit输出发呆：为什么这个看似简单的插入操作，数据量刚过万就慢得像卡住的电梯？或者在实现一个需要频繁在中间增删元素的缓存淘汰策略时，发现list.insert(i, x)的耗时曲线陡然上扬，而你的同事用 C 写的模块却稳如老狗？这背后，就是数组和链表两种底层内存组织逻辑的根本性撕裂。
我第一次真正“看见”这种撕裂，是在重构一个日志聚合服务的时候。原始代码用list.append()收集每条日志，再用list.insert(0, new_log)把最新日志塞到最前面——这在测试数据只有几百条时毫无压力。但当真实流量涌入，日志条目以每秒上千的速度增长，服务响应时间从 20ms 暴涨到 800ms。cProfile一跑，insert占了 73% 的总耗时。那一刻我才明白，教科书里那个“O(n) 时间复杂度”的抽象符号，落到生产环境里，就是用户手机屏幕上多出来的那几秒加载动画。
链表不是什么高深莫测的黑魔法，它就是一个非常朴素的“地址簿”思想。想象你有一本通讯录，每一页只记一个人的名字和他下一页的页码（比如“张三，下一页是第 42 页”）。你要找“李四”，就得从第 1 页开始翻，看到“张三，下一页是第 42 页”，就翻到 42 页；42 页写着“王五，下一页是第 17 页”，再翻到 17 页……直到找到“李四”。这个过程很慢，因为必须一页一页翻（O(n) 查找）。但如果你要在“张三”后面加个“赵六”，你只需要把 1 页上“张三，下一页是第 42 页”改成“张三，下一页是第 99 页”，再在第 99 页写上“赵六，下一页是第 42 页”。整个过程，你只改了两处纸上的字，完全不用把后面几十页的内容都挪一遍。这就是链表插入/删除的 O(1) 神奇之处——它不移动数据，只修改指针。
Python 的list是动态数组，它的内存是一整块连续的“大平房”。你要在中间插个新住户，就得把后面所有住户连人带家具一起搬到新盖的、更大的“大平房”里去，腾出位置。而链表是散落在城市各处的“独立小院”，每个院子有自己的门牌号（内存地址），院子里除了住客（data），还贴着一张纸条，写着隔壁院子的门牌号（next pointer）。你要加人，就买个新院子，在前一个院子的纸条上更新地址；要删人，就把前一个院子的纸条撕掉，直接写上后一个院子的地址。房子（内存）本身的位置，从来不需要动。
所以，当你看到“链表适合频繁插入删除”这句话时，请把它具象化：它适合的不是“偶尔删一个”，而是“每秒删一百个、插一百个”的高频场景；它适合的不是“数据量小”，而是“数据量不可预测，可能从 10 个暴涨到 1000 万个”的弹性场景。而它的代价，就是你永远无法像查电话号码本那样，凭空喊出“第 5000 个元素”，必须从头开始数。这就像你无法凭空知道通讯录的第 5000 页是谁，但你可以瞬间把“老板”加到“总监”后面。理解这个取舍，才是掌握链表的起点。接下来，我们就从最基础的单向链表开始，一行一行代码，亲手把这个“地址簿”搭起来。
2. 单向链表：从零构建一个可运行的“活”结构
2.1 节点（Node）：链表的原子单元
链表的一切，都始于一个微小的Node类。它看起来简单得不可思议，但正是这个简单，承载了整个数据结构的灵魂。
class Node: def __init__(self, data): self.data = data self.next = None这段代码里藏着两个关键设计决策，它们不是随意写的，而是直指链表的核心哲学：
第一，self.data = data—— 数据与逻辑的彻底解耦。data可以是任何东西：一个整数42，一个字符串"hello"，一个自定义的User对象，甚至是一个嵌套的字典{"name": "Alice", "score": 95}。Node类本身对data的类型、大小、内容一无所知，也毫不关心。它只是一个纯粹的“容器”和“连接器”。这赋予了链表无与伦比的通用性。我曾经用同一个Node类，同时管理着一个包含 10 万个传感器读数的实时流（data是float），和一个存储用户会话状态的缓存池（data是dict）。代码复用率 100%，因为Node只负责“装”和“连”，不负责“算”。
第二，self.next = None—— “终结”的明确宣告。None在这里不是一个占位符，而是一个强有力的契约。它清晰地告诉世界：“此路不通，前方已无节点”。这个设计杜绝了悬空指针（dangling pointer）的灾难。在 C 语言里，忘记初始化指针是导致段错误（Segmentation Fault）的头号元凶。而在 Python 中，None是一个安全的、明确的“空”状态。当你遍历链表时，while current is not None:这个条件判断，就是基于这个坚实的基础。它不像while current:那样隐晦（因为如果data是0或""，current本身为真，但current.data可能为假，容易引发混淆），None就是None，干净利落。
提示：初学者常犯的一个错误，是试图在
Node的__init__方法里就传入next参数，比如def __init__(self, data, next=None)。这看似更“完整”，实则破坏了封装性。Node只应负责自己的数据，它和谁连接，是LinkedList这个更高层管理者的事。让Node过早地知道“下一个是谁”，就像让一个士兵在入伍第一天就规划好整个军团的行军路线，既不必要，也容易出错。
2.2 链表（LinkedList）：管理节点的“指挥中心”
有了Node，我们就可以构建LinkedList类了。它的核心职责，就是管理所有Node的生命周期和相互关系。最关键的成员变量，只有一个：self.head。
class LinkedList: def __init__(self): self.head = Noneself.head是整个链表的“门面”和“总开关”。它不存储任何业务数据，它只是一个指向第一个Node的引用。当self.head是None时，链表为空；当self.head指向一个有效的Node时，链表就有了生命。这个设计极其精妙，因为它将“空链表”和“非空链表”的边界处理得无比优雅。所有操作，无论是插入、删除还是查找，第一步永远是检查self.head是否为None。这就像一个城市的市政厅，它自己不生产粮食，但它掌管着所有粮仓（节点）的钥匙（指针）。
现在，让我们来实现第一个核心操作：在开头插入（insertAtBeginning）。这是链表最高效的操作，也是理解其指针魔法的最佳入口。
def insertAtBeginning(self, new_data): new_node = Node(new_data) new_node.next = self.head # 关键一步：新节点的next，指向当前的head self.head = new_node # 关键一步：head，现在指向新节点让我用一个具体的例子，带你走一遍这个“指针魔术”的全过程。假设我们有一个空链表，self.head是None。
- 创建新节点：
new_node = Node("the")。此时，new_node.data = "the"，new_node.next = None。 - 建立连接：
new_node.next = self.head。因为self.head是None，所以这行代码等价于new_node.next = None。新节点的“下一页”还是空的，这完全合理，因为它是第一个。 - 更新门面：
self.head = new_node。现在，self.head不再是None，它指向了我们刚刚创建的new_node。
链表诞生了！它的结构是：head -> [data="the", next=None]。
接着，我们再插入"quick"：
- 创建
new_node = Node("quick")，new_node.next = None。 new_node.next = self.head。此时self.head指向的是"the"节点，所以这行代码让new_node.next指向了"the"节点。self.head = new_node。现在self.head指向了"quick"节点。
最终结构是：head -> [data="quick", next=→] -> [data="the", next=None]。
看到了吗？我们没有动过"the"节点本身，只是修改了"quick"节点的next指针，并把head的指向换了一下。整个过程，只涉及两次内存写入（new_node.next和self.head），时间复杂度稳定在 O(1)，与链表里已经有多少个节点完全无关。这就是链表的“轻盈”所在。
注意：
insertAtBeginning的简洁，恰恰反衬出insertAtEnd的“笨重”。后者必须从head开始，一路next下去，直到找到next为None的那个节点，才能把新节点挂上去。这个“一路找”的过程，就是 O(n) 的来源。所以，如果你的应用场景是“队列”（FIFO，先进先出），那么在开头插入、在末尾删除，或者在末尾插入、在开头删除，都是高效的；但如果你需要在末尾插入，又需要在末尾删除，那单向链表就不是最优解了，你需要考虑双向链表。
2.3 遍历与打印：让链表“开口说话”
一个不能被看见的数据结构，就像一个无法被调试的程序。printList方法，是我们观察链表内部状态的“显微镜”。
def printList(self): temp = self.head while temp: print(temp.data, end=' ') temp = temp.next print()这段代码的精妙之处在于while temp:这个循环条件。它利用了 Python 的“真值性”（truthiness）：一个对象在布尔上下文中，如果它不为None，且不是空的容器（如[],{},""），它就被认为是True。对于Node对象，只要它存在（即不是None），它就为True。所以while temp:等价于while temp is not None:，但前者更简洁、更符合 Python 的惯用法。
然而，这个简洁背后，藏着一个新手极易踩的坑：temp = temp.next的顺序绝对不能错。如果你把它写成：
# 错误示范！ while temp: print(temp.data, end=' ') temp = temp.next # 这行没问题 # ... 但如果你在这里加了其他代码，比如 break，就可能出问题这本身没错。但真正的陷阱在于，如果你在循环体里写了break，并且break发生在temp = temp.next之前，那么下一次循环开始时，temp还是上一个节点，就会造成无限循环。所以，最安全、最符合直觉的写法，是把temp = temp.next放在循环体的最后，确保每次迭代都向前推进一步。
为了让你更直观地感受链表的“生长”，我们可以写一个辅助函数，一次性插入多个元素：
def insertMultipleAtBeginning(self, data_list): """从列表末尾开始插入，保证顺序""" for data in reversed(data_list): self.insertAtBeginning(data) # 使用示例 llist = LinkedList() llist.insertMultipleAtBeginning(["the", "quick", "brown", "fox"]) llist.printList() # 输出: the quick brown fox这个insertMultipleAtBeginning函数，通过reversed()，巧妙地规避了“逆序插入”的问题。如果你直接遍历["the", "quick", "brown", "fox"]并依次插入开头，得到的会是"fox brown quick the"。而reversed让我们先插"fox"，再插"brown"，依此类推，最终head指向"the"，完美还原了语义顺序。
3. 核心操作详解：不只是代码，更是工程权衡
3.1 在末尾插入（insertAtEnd）：O(n) 的必然与优化空间
在开头插入是 O(1)，在末尾插入却是 O(n)。这个差异，是理解链表性能特性的分水岭。
def insertAtEnd(self, new_data): new_node = Node(new_data) if self.head is None: self.head = new_node return last = self.head while last.next: last = last.next last.next = new_node这段代码的逻辑非常清晰：如果链表为空，新节点就是头；否则，就从头开始，一直走到last.next为None的那个节点，然后把new_node挂上去。
但这里有一个深刻的工程权衡：我们是否应该为insertAtEnd操作维护一个tail（尾节点）指针？
答案是：视场景而定。如果你的应用中，insertAtEnd是一个高频操作（比如实现一个日志队列，所有新日志都追加到末尾），那么在LinkedList类中增加一个self.tail成员变量，并在每次插入、删除时同步更新它，是绝对值得的。这样，insertAtEnd就能从 O(n) 降为 O(1)。
# 优化版：带 tail 指针的 LinkedList class LinkedListWithTail: def __init__(self): self.head = None self.tail = None # 新增 tail 指针 def insertAtEnd(self, new_data): new_node = Node(new_data) if self.head is None: self.head = self.tail = new_node # 空链表，头尾都是新节点 else: self.tail.next = new_node # 尾节点的 next 指向新节点 self.tail = new_node # 更新 tail 指针这个优化的代价，是每次插入、删除操作都需要额外维护tail。例如，deleteFromEnd就不能再像之前那样简单地“找到倒数第二个节点”，而必须从头遍历，或者引入更复杂的逻辑来维护tail。所以，工程师的日常工作，就是在“时间复杂度”和“空间复杂度/代码复杂度”之间，寻找那个最适合当前业务场景的甜蜜点。没有银弹，只有权衡。
3.2 删除操作：从开头到末尾的“断链”艺术
删除操作，本质上就是“断开”一个节点与链表的连接。deleteFromBeginning是最简单的，因为它只需要移动head指针。
def deleteFromBeginning(self): if self.head is None: return "The list is empty" self.head = self.head.next # 断开连接，旧 head 自动被垃圾回收这里的关键洞察是：我们不需要手动“删除”旧的head节点。我们只需要让self.head指向下一个节点。一旦没有任何引用指向旧的head节点（self.head不再指向它，也没有其他变量指向它），Python 的垃圾回收机制（GC）就会自动将其内存释放。这与 C/C++ 中必须手动调用free()或delete形成鲜明对比，是 Python 作为高级语言的巨大便利。
deleteFromEnd则复杂得多，因为它需要定位到“倒数第二个”节点。
def deleteFromEnd(self): if self.head is None: return "The list is empty" if self.head.next is None: # 只有一个节点 self.head = None return temp = self.head while temp.next.next: # 循环直到 temp.next.next 为 None temp = temp.next temp.next = None # 断开倒数第二个节点与最后一个节点的连接while temp.next.next:这个条件是精髓。它确保了temp停留在倒数第二个节点上。例如，链表是A->B->C->None：
- 初始
temp = A，temp.next.next是C，为真，进入循环。 temp = B，temp.next.next是None，为假，退出循环。- 此时
temp是B，temp.next是C，我们将temp.next设为None，C就被成功移除。
实操心得：我在实现这个方法时，曾无数次被
AttributeError: 'NoneType' object has no attribute 'next'这个错误折磨。根源就在于while temp.next:和while temp.next.next:的混淆。前者会停在C（因为C.next是None，所以temp.next为假），后者才会停在B。记住这个口诀：“要删最后一个，就找倒数第二个；要找倒数第二个，就看它的‘下下个’是不是空”。
3.3 查找操作（search）：线性扫描的必然与现实妥协
链表的查找，注定是线性的。search方法的实现，就是一次标准的线性扫描。
def search(self, value): current = self.head position = 0 while current: if current.data == value: return f"Value '{value}' found at position {position}" current = current.next position += 1 return f"Value '{value}' not found in the list"这个方法的价值，远不止于“找到就返回”。它是一个绝佳的“调试探针”。在开发一个复杂的链表算法（比如合并两个有序链表）时，我习惯在每一步操作后，都调用search来验证链表的状态是否符合预期。例如，在合并后，我期望search("min_value")返回位置0，search("max_value")返回最大位置。这种即时反馈，能极大加速调试过程。
但请务必注意：search的返回值是字符串，而不是布尔值或索引。这是一个刻意的设计。在教学和调试场景中，一个描述性的字符串（如"Value 'quick' found at position 0"）比一个冰冷的True或0更有价值。它告诉你“找到了”，还告诉你“在哪里找到的”，甚至暗示了“链表当前的长度”。在生产环境中，你可能会将其改为返回索引position或None，但作为学习工具，它的信息密度更高。
4. 三种链表形态：从单向到循环，解决不同维度的问题
4.1 单向链表（Singly Linked List）：基础与局限
我们前面实现的，就是单向链表。它的优势是结构最简单，内存开销最小（每个节点只有data和next两个字段），实现和理解成本最低。它完美地解决了“在任意位置高效插入/删除”的问题。
但它的局限也同样明显：只能单向遍历。这意味着，如果你需要实现一个“撤销”（Undo）功能，用户按了 Ctrl+Z，你需要回到上一个状态。在单向链表里，你无法从当前节点“回退”到前一个节点，因为你根本没有保存那个信息。你唯一的选择是从头开始，再次遍历，直到找到前一个节点——这又是 O(n) 的开销。
另一个经典场景是“LRU 缓存”（Least Recently Used Cache）。它的核心逻辑是：当缓存满时，要删除最久未使用的那个元素。而“最久未使用”，就是那个最近一次被访问以来，时间间隔最长的元素。在单向链表中，每次访问一个元素，你都需要把它“移动”到链表头部（表示最新使用），这要求你能快速定位到它的前驱节点，以便将其“摘下来”并“挂到前面”。单向链表做不到这一点。
4.2 双向链表（Doubly Linked List）：为“回溯”而生
双向链表，就是为了解决单向链表的“回溯”难题而生的。它在每个节点中，额外增加了一个prev（前驱）指针。
class DoublyNode: def __init__(self, data): self.data = data self.next = None self.prev = None # 新增：指向前一个节点 class DoublyLinkedList: def __init__(self): self.head = None self.tail = None # 通常也会维护 tail，方便尾部操作prev指针的加入，让许多操作变得优雅而高效。以“在指定节点后插入”为例：
def insertAfter(self, prev_node, new_data): if prev_node is None: return new_node = DoublyNode(new_data) # 修改新节点的指针 new_node.next = prev_node.next new_node.prev = prev_node # 修改原链表的指针 if prev_node.next is not None: # 如果 prev_node 不是尾节点 prev_node.next.prev = new_node prev_node.next = new_node这个操作是 O(1) 的，而且逻辑清晰：新节点的next指向prev_node的下一个，prev指向prev_node；然后，把prev_node的next指向新节点，并把原来prev_node.next的prev指向新节点。整个过程，只涉及四次指针赋值。
实操心得：实现双向链表时，最大的挑战不是逻辑，而是边界条件的完备性。你必须仔细考虑四种情况：1) 在空链表中插入；2) 在只有一个节点的链表中插入（作为头或尾）；3) 在链表中间插入；4) 在链表末尾插入。每一种情况，
head、tail、prev、next四个指针的更新规则都不同。我建议在写完代码后，立刻画一个只有 2-3 个节点的草图，手动模拟每一步指针的变化，这是避免 bug 的最有效方法。
4.3 循环链表（Circular Linked List）：没有终点的旅程
循环链表，是链表家族中最富哲学意味的一种。它的尾节点的next指针，不再指向None，而是重新指向头节点，形成一个完美的闭环。
class CircularNode: def __init__(self, data): self.data = data self.next = None class CircularLinkedList: def __init__(self): self.head = None def insertAtEnd(self, new_data): new_node = CircularNode(new_data) if self.head is None: self.head = new_node new_node.next = self.head # 关键：自己指向自己 else: # 找到当前的尾节点（即 head 的前一个节点） temp = self.head while temp.next != self.head: # 循环条件变了！ temp = temp.next # 将新节点插入到尾部 temp.next = new_node new_node.next = self.head # 关键：新节点的 next 指向 head循环链表的遍历逻辑也发生了根本变化：
def printList(self): if self.head is None: return temp = self.head while True: print(temp.data, end=' ') temp = temp.next if temp == self.head: # 当我们又回到起点时，停止 break print()while True加上if temp == self.head: break，是循环链表遍历的标准范式。它不再依赖None，而是依赖“身份认同”——当一个节点再次等于head时，我们就知道，一圈走完了。
这种“无始无终”的特性，让它成为某些特定场景的天然选择：
- 轮询调度（Round-Robin Scheduling）：操作系统给每个进程分配一小段时间片，执行完后，就切换到下一个进程。循环链表的
next指针，完美地模拟了这个“下一个”的概念。 - 约瑟夫问题（Josephus Problem）：一群人围成一圈，从某个人开始报数，每报到某个数字就淘汰一人，然后从下一个人继续，直到剩下最后一人。循环链表是解决这个问题最直观的数据结构。
- 游戏开发中的玩家轮次：多人棋类游戏中，玩家 A -> B -> C -> A -> ... 的轮转，用循环链表建模，代码简洁，逻辑清晰。
注意：循环链表的
delete操作，其边界条件比单向链表更复杂。当删除的是唯一一个节点时，self.head必须被设为None，否则会陷入无限循环。当删除的是head本身时，self.head必须更新为原来的head.next，并且新的tail（即新head的前一个节点）的next必须指向新的head。这些细节，是区分一个“能跑通”的实现和一个“健壮可靠”的实现的关键。
5. 常见问题与排查技巧实录：那些年，我们一起踩过的坑
5.1 问题速查表：从报错信息反推故障点
| 报错信息 | 最可能的原因 | 排查与修复技巧 |
|---|---|---|
AttributeError: 'NoneType' object has no attribute 'xxx' | 试图在一个None值上调用属性或方法，通常是current.next或current.data。 | 第一步：在报错行的上一行，添加print(f"current is: {current}")。如果输出current is: None，说明你在while循环条件中漏掉了is not None的检查，或者循环体内的current = current.next导致了current变为None后，后续代码仍试图访问它。修复：确保所有对current.xxx的访问，都在while current is not None:的保护之下。 |
RecursionError: maximum recursion depth exceeded | 递归调用过深。虽然我们的实现是迭代的，但如果你尝试用递归方式实现（如search_recursive），且链表过长或有环，就会触发此错误。 | 第一步：检查你的递归函数是否有正确的终止条件（base case）。第二步：检查链表是否意外形成了环（例如，node1.next = node2; node2.next = node1），这会导致递归永无止境。可以用“快慢指针”法检测环。 |
UnboundLocalError: local variable 'xxx' referenced before assignment | 在一个分支中定义了变量，但在另一个分支中没有定义，然后在分支外使用了它。 | 典型场景：在insertAtEnd中，last变量只在if self.head is not None:分支内定义。如果链表为空，last就不存在，但后续代码（如last.next = new_node）仍试图使用它。修复：将last的初始化放在if语句之前，例如last = self.head，或者确保所有分支都对last进行了赋值。 |
5.2 经典陷阱：指针的“幽灵”与内存的“幻影”
陷阱一：“浅拷贝”导致的指针污染。
假设你有一个链表list_a，你想创建一个副本list_b。如果你天真地写list_b.head = list_a.head，那么恭喜你，你并没有创建副本，你只是创建了一个新的“门面”（head），它指向了和list_a完全相同的节点序列。对list_b的任何修改（比如删除一个节点），都会直接影响list_a。这就像给同一栋房子办了两张房产证。
正确做法：必须进行“深拷贝”（Deep Copy），即为每一个Node都创建一个新的实例，并复制其data，然后重新构建next指针的连接关系。
def deep_copy(self): if self.head is None: return LinkedList() new_list = LinkedList() # 先复制头节点 new_head = Node(self.head.data) new_list.head = new_head # 用两个指针同步遍历原链表和新链表 old_current = self.head.next new_current = new_head while old_current: new_node = Node(old_current.data) new_current.next = new_node new_current = new_node old_current = old_current.next return new_list陷阱二：循环引用与垃圾回收延迟。
在双向链表中，node_a.next = node_b且node_b.prev = node_a，这就形成了一个循环引用（node_a引用node_b，node_b也引用node_a）。在 Python 的早期版本中，这种循环引用可能导致内存泄漏，因为 GC 无法确定这两个对象是否真的可以被回收。
现代 Python（3.4+）的解决方案：Python 的 GC 已经非常成熟，能够自动检测和清理绝大多数循环引用。但作为一个严谨的工程师，我们仍然应该养成“及时切断引用”的好习惯。例如，在delete操作中，除了修改next和prev指针，还应该显式地将被删除节点的next和prev设为None：
def deleteNode(self, target_node): if target_node.prev: target_node.prev.next = target_node.next else: self.head = target_node.next # target_node 是 head if target_node.next: target_node.next.prev = target_node.prev else: self.tail = target_node.prev # target_node 是 tail # 关键：切断被删除节点自身的引用，帮助 GC target_node.next = None target_node.prev = None这个小小的target_node.next = None，不仅是一种礼貌，更是一种防御性编程。它确保了即使 GC 一时没来得及清理，target_node也不会再意外地参与到任何链表操作中。
5.3 性能迷思：何时链表真的比列表快？
这是一个经常被误解的问题。很多人看到“链表插入是 O(1)”就热血沸腾，立刻想用链表替代所有list。但现实是残酷的。
CPU 缓存（Cache Locality）是决定性因素。Python 的list是一块连续的内存。当你访问list[0]时，CPU 会把list[0]附近的一大片内存（一个 cache line，通常是 64 字节）都加载进高速缓存。因此，紧接着访问list[1]、list[2]时，数据很可能已经在缓存里了，速度极快。而链表的节点是随机分布在内存各处的。访问node1后，node2可能在内存的另一端，CPU 不得不发起一次昂贵的内存寻址（memory fetch），这比访问缓存慢上百倍。
所以，链表的理论优势（O(1) 插入）只在“插入/删除操作的频率远高于遍历/访问操作的频率”时才成立。例如：
- 一个任务队列，每秒接收 1000 个新任务（插入），但每分钟才被消费一次（遍历）。
- 一个编辑器的撤销栈，用户疯狂输入（在末尾插入），但撤销操作（从末尾删除）相对较少。
反之，如果你的代码是这样的：
# 场景：需要频繁按索引访问 for i in range(len(my_list)): process(my_list[i]) # O(1) 随机访问 # vs for i in range(length_of_linked_list): value = get_node_at_index(i).data # O(n) 查找，总耗时 O(n²)那么，用链表就是一场灾难。
我个人的经验是：在 Python 中，除非你有非常明确的、经过压测验证的性能瓶颈，并且这个瓶颈确实是由list的insert/pop(0)操作引起的，否则，请优先使用内置的list。它的 API 更丰富（切片、count、index），实现更成熟，且在绝大多数日常场景下，它的综合性能（考虑到缓存友好性）都优于手写的链表。链表，应该是你武器库中一把锋利的特种刀，而不是日常吃饭的勺子。
6. 实战延伸：从玩具代码到真实世界的桥梁
6.1 用链表实现一个 LRU 缓存
LRU 缓存是链表最经典的实战应用之一。它要求：
get(key): 如果 key 存在，返回 value，并将该 key 移动到“最近使用”的位置（头部）；如果不存在，返回 -1。put(key, value): 如果 key 已存在，更新 value，并移动到头部；如果不存在，插入新 key-value 对。如果容量已满，删除“最久未使用”的 key（尾部）。
这个需求，完美契合了双向链表 + 哈希表的组合。
