算法分析与设计

Appearance

2.3 链表 ​

学习目标 ​

学完这一节，你能：

  • 解释链表节点和指针的基本结构
  • 区分链表和数组在访问、插入、删除上的差异
  • 说清"已知节点位置"和"需要先查找节点"的复杂度差别
  • 判断 agent 什么时候误用链表
  • 用 Python 写出简单链表节点，但知道实际工程中何时不该手写链表

链表像一串线索 ​

数组像连续编号的书架。链表不要求元素连续放在一起。

链表的每个节点保存两样东西：

text
数据 + 下一个节点的位置

可以画成：

text
[A | next] -> [B | next] -> [C | next] -> None

在 Python 里可以这样表示一个节点：

python
class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

创建三个节点：

python
c = Node("C")
b = Node("B", c)
a = Node("A", b)
head = a

从 head 出发，沿着 next 一个个走，就能访问整个链表。

链表没有随机访问 ​

数组可以直接访问 items[1000]。链表不行。

如果你要找第 1000 个节点，只能从头开始走：

python
def get(head, index):
    current = head
    for _ in range(index):
        if current is None:
            raise IndexError("index out of range")
        current = current.next
    if current is None:
        raise IndexError("index out of range")
    return current.value

访问第 i 个节点需要走 i 步，最坏是 Θ(n)。

所以，"链表插入快"这句话只说了一半。链表只有在已经知道要插入或删除的位置时，改指针才快。如果还要先从头找位置，查找本身就是 Θ(n)。

在已知位置后插入 ​

假设我们已经拿到了节点 node，要在它后面插入 value：

python
def insert_after(node, value):
    new_node = Node(value, node.next)
    node.next = new_node

这只改了两个引用，是 Θ(1)。

对比数组中间插入，数组要移动后面的元素；链表只要改连接关系。这是链表的优势。

删除下一个节点 ​

如果已经拿到前驱节点 node，要删除它后面的节点：

python
def delete_after(node):
    if node.next is None:
        return
    node.next = node.next.next

这也是 Θ(1)。

但如果你只有一个值，比如要删除第一个值为 "Chen" 的节点，就要先查找：

python
def remove_first(head, target):
    dummy = Node(None, head)
    prev = dummy
    current = head

    while current is not None:
        if current.value == target:
            prev.next = current.next
            return dummy.next
        prev = current
        current = current.next

    return dummy.next

这里的查找是 Θ(n)。哨兵节点 dummy 的作用是简化删除头节点的边界情况。

单链表、双链表和循环链表 ​

本节只手写了单链表。常见变体还有：

类型结构优势代价
单链表每个节点只指向下一个简单，空间较省找前驱不方便
双链表每个节点有前后两个指针双向移动，删除当前节点方便每个节点多一个引用
循环链表尾节点指回头部适合循环处理边界更容易写错

Python 标准库里的 collections.deque 可以理解为一种高效的双端队列实现。大多数工程场景中，你不需要自己手写链表；但你需要理解链表思想，因为它解释了很多结构的底层取舍。

链表的表示不变量 ​

链表实现最容易出错的地方不是语法，而是不变量。

对一个普通单链表，至少应该保持：

text
head 要么是 None，要么指向第一个节点。
从 head 沿 next 走，应该能访问所有节点。
最后一个节点的 next 必须是 None。
除非刻意设计循环链表，否则不能形成环。

如果还维护 tail 和 size，不变量会更多：

text
size 等于从 head 能走到的节点数量。
如果 size == 0，那么 head 和 tail 都应该是 None。
如果 size > 0，那么 tail.next 应该是 None。

这些不变量让你能审查 agent 的链表代码。比如 agent 删除最后一个节点后，如果忘了更新 tail，小测试可能还过，但下一次尾部追加就可能接错位置。

链表操作复杂度表 ​

操作已知位置？单链表复杂度说明
访问第 i 个元素否Θ(i)，最坏 Θ(n)只能从头走
头部插入是Θ(1)改 head
已知节点后插入是Θ(1)改一个 next
按值查找否Θ(n)逐个比较
删除某个值否Θ(n)先找前驱
删除已知节点后一个节点是Θ(1)改前驱的 next
尾部追加有 tailΘ(1)否则要走到尾部

这张表的关键词是"已知位置"。很多错误解释都来自把"已知位置插入"偷换成"任意插入"。

链表适合什么 ​

链表适合：

  • 已经拿到节点位置，需要快速插入或删除
  • 不需要按下标随机访问
  • 需要频繁在头部插入或删除
  • 数据节点需要自然连接成序列

链表不适合：

  • 大量按下标访问
  • 大量查找某个值
  • 追求紧凑存储和缓存友好
  • 在 Python 中为了"高级"而手写普通列表替代品

尤其在 Python 中，手写链表通常比内置 list、deque 更慢、更容易出错。学习链表不是为了到处手写它，而是为了理解"指针重连"这种组织方式。

用本节知识理解：为什么“当前位置”很重要 ​

在线课堂系统里，假设老师正在浏览一个问题列表，并希望把一个补充说明插到当前问题后面。

如果系统已经拿到了"当前问题节点"，链表插入就很自然：

text
当前问题 -> 下一个问题
当前问题 -> 补充说明 -> 下一个问题

这就是链表擅长的场景：你已经站在要修改的位置上。

但如果需求是：

找到标题包含"考试"的第一个问题，在它后面插入补充说明。

那就不一样了。你必须先从头查找标题包含"考试"的问题，这一步是 Θ(n)。找到以后插入才是 Θ(1)。

所以，链表的生活类比不是"链表插入永远快"，而是：

如果你手里已经拿着那张卡片，要在它后面接一张新卡片，只要改两根线；
如果你还不知道那张卡片在哪里，就得先沿着线一张张找。

这句话能帮你反驳很多 agent 的粗糙建议：

这个需求有插入，所以用链表，插入 O(1)。

你应该追问：

text
插入位置如何得到？
是已经持有节点，还是要按值查找？
查找成本是否主导整体复杂度？

审查 agent 输出 ​

假设 agent 说：

这个任务需要频繁插入，所以应该用链表。链表插入是 O(1)。

你不能直接接受。要追问：

  1. 插入位置是否已经知道？
  2. 如果每次都要按值查找插入位置，查找成本是多少？
  3. 是否还需要按下标访问？
  4. Python 中是否有更合适的内置结构？
  5. 链表带来的额外节点对象和引用成本是否值得？

例如，要维护一个按时间排序的日志列表，每次新日志都要插入到正确位置。链表插入本身快，但找到正确位置仍然要线性扫描。这个任务未必因为"插入频繁"就适合链表。

本节要点 ​

  • 链表由节点和引用组成，元素不需要连续存放。
  • 链表不能按下标直接访问，第 i 个节点要从头走过去。
  • 已知位置后的插入和删除是 Θ(1)。
  • 按值查找再插入或删除，整体仍然可能是 Θ(n)。
  • 在 Python 中，链表更多用于理解数据结构思想；实际代码通常优先考虑 list、deque 或更高层结构。

课堂练习 ​

某 agent 推荐：

为了实现待办事项列表，应该用链表，因为用户会频繁插入和删除任务。

请先补全需求，再判断是否接受：

  1. 用户是按位置插入，还是只在末尾追加？
  2. 删除任务时是按编号、按标题，还是删除当前选中项？
  3. 是否需要快速显示第 k 个任务？
  4. 数据规模通常是多少？
  5. 在这些条件下，你会选择 list、deque、链表，还是别的结构？

课后测验 ​

📝 课后测验

得分：0 / 0

上一节：2.2 数组与动态数组

下一节：2.4 栈与队列

新时代的算法课程