05　链表

链表由一个个节点组成。每个节点保存数据，并保存指向下一个节点的引用。

数组依靠连续存储和下标访问元素；链表则依靠节点之间的链接，把可以分散在内存中的对象组织起来。

原书中的链表用 C 语言指针来实现。Python 不要求我们手动操作内存地址，而是使用对象引用；但 node.next 所表达的“指向下一个节点”的关系完全相同。

链表牺牲随机访问速度，换取了更灵活的插入、删除和拼接能力。

1. 单向链表的基本结构

一个单向链表可以表示为：

head
  ↓
[10 | next] → [20 | next] → [30 | None]

最后一个节点的 next 为 None，表示链表结束。

在 Python 中，可以定义一个节点类：

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


head = None  # 空链表

创建一条链表：

head = Node(10, Node(20, Node(30)))

print(head.value)            # 10
print(head.next.value)       # 20
print(head.next.next.value)  # 30

head 保存第一个节点。只要从 head 出发，就可以沿着 next 访问整条链表。

2. 遍历链表

链表没有数组下标。要访问第 k 个元素，必须从头节点开始，沿着 next 走 k 步。

def to_list(head):
    values = []
    current = head

    while current is not None:
        values.append(current.value)
        current = current.next

    return values


head = Node(10, Node(20, Node(30)))
print(to_list(head))  # [10, 20, 30]

如果链表有 n 个节点，完整遍历的复杂度是 O(n)。

访问第一个节点是 O(1)，但访问第 k 个节点通常是 O(k)；如果只知道链表长度而不知道目标位置，通常按最坏情况记为 O(n)。

3. 创建节点和 Python 的内存管理

在 C 语言中，链表节点通常需要动态分配，并在删除后手动 free。Python 会自动管理对象的生命周期：

node = Node(10)
another = node

del node
print(another.value)  # 10

del node 只是删除变量名；因为 another 仍然引用同一个对象，所以节点还存在。当一个节点不再被任何对象引用时，Python 才会自动回收它。

因此，Python 链表实现不需要手动释放节点，但仍然要正确修改链接：

• 从链表中删除节点；
• 不要让链表继续指向已经不需要的节点；
• 不要在结构被破坏后继续沿着旧引用遍历。

4. 在链表头部插入

头部插入不需要移动其他节点：

插入前：head → [20] → [30]
插入10：
         [10] → [20] → [30]
          ↑
         head

在 Python 中，函数可以返回新的头节点：

def push_front(head, value):
    return Node(value, head)


head = Node(20, Node(30))
head = push_front(head, 10)

print(to_list(head))  # [10, 20, 30]

头部插入只创建一个节点并修改一个引用，复杂度是 O(1)。

这和 C 语言中需要通过二级指针修改头指针的原因不同：Python 直接返回新的 head，调用者重新接收即可。

5. 在指定节点之后插入

假设要在节点 x 后面插入新节点：

插入前：x → y
插入后：x → new → y

Python 实现如下：

def insert_after(node, value):
    if node is None:
        raise ValueError("目标节点不能为空")

    new_node = Node(value, node.next)
    node.next = new_node


head = Node(10, Node(30))
insert_after(head, 20)

print(to_list(head))  # [10, 20, 30]

引用修改顺序很重要：

1. 先让新节点指向原来的后继节点；
2. 再让 node 指向新节点。

如果先覆盖 node.next，就可能丢失原来的后继节点。

如果已经有目标节点的引用，插入是 O(1)；如果只有头节点，需要先遍历找到目标节点，整体成本就是 O(n)。

6. 删除节点

在单向链表中，要删除节点 p，通常需要知道它的前驱节点 prev：

删除前：prev → p → next
删除后：prev ─────────→ next

def delete_after(previous):
    if previous is None or previous.next is None:
        raise ValueError("没有可以删除的后继节点")

    target = previous.next
    previous.next = target.next

    # 断开 target，帮助读者明确它已经不在链表中
    target.next = None
    return target.value


head = Node(10, Node(20, Node(30)))
print(delete_after(head))  # 20
print(to_list(head))       # [10, 30]

删除头节点需要返回新的头节点：

def pop_front(head):
    if head is None:
        raise IndexError("链表为空")

    removed_value = head.value
    new_head = head.next
    head.next = None
    return new_head, removed_value


head = Node(10, Node(20))
head, removed = pop_front(head)

print(removed)       # 10
print(to_list(head)) # [20]

如果已经知道前驱节点，删除是 O(1)；如果需要先搜索目标节点或前驱节点，整体通常是 O(n)。

7. 哨兵节点与边界条件

直接使用头指针时，以下情况需要分别处理：

• 空链表；
• 删除头节点；
• 在头节点之前插入；
• 删除最后一个节点；
• 只有一个节点的链表。

一种简化方法是使用哨兵节点。哨兵节点不保存真正的数据，只作为固定起点：

sentinel → [10] → [20] → None

例如，删除第一个真实节点时，可以统一使用“删除某个节点之后的节点”的逻辑：

def remove_first_with_sentinel(head):
    dummy = Node(None, head)

    if dummy.next is None:
        raise IndexError("链表为空")

    target = dummy.next
    dummy.next = target.next
    target.next = None

    return dummy.next, target.value


head = Node(10, Node(20))
head, removed = remove_first_with_sentinel(head)

print(removed)       # 10
print(to_list(head)) # [20]

哨兵节点不是必须的，但在实现复杂链表时，常常能减少对头节点的特殊判断。

8. 链表的基本复杂度

链表的“插入和删除快”有一个前提：必须已经定位到相关节点。

9. 尾引用与链表拼接

如果链表只保存 head，要在末尾追加元素，就必须从头走到尾。

如果同时保存 head 和 tail，就能把新节点直接接到末尾：

class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def append(self, value):
        node = Node(value)

        if self.head is None:
            self.head = node
            self.tail = node
            return

        self.tail.next = node
        self.tail = node

    def to_list(self):
        return to_list(self.head)


numbers = LinkedList()
numbers.append(10)
numbers.append(20)
numbers.append(30)

print(numbers.to_list())  # [10, 20, 30]

维护 tail 会增加一点状态管理，但能把尾部追加从 O(n) 优化到 O(1)。

拼接两个链表时，也可以直接让第一个链表的 tail.next 指向第二个链表的 head。如果还要让第一个链表独立拥有一份数据，则需要复制节点，成本会变成 O(n)。

10. 循环链表

普通链表的尾节点指向 None；循环链表的尾节点指回头节点：

      ┌──────────────────────┐
      ↓                      │
head [10] → [20] → [30] ─────┘

循环链表没有天然的 None 终点，因此遍历时必须记录起点：

def circular_to_list(head):
    if head is None:
        return []

    values = []
    current = head

    while True:
        values.append(current.value)
        current = current.next

        if current is head:
            break

    return values


head = Node(10, Node(20, Node(30)))
head.next.next.next = head

print(circular_to_list(head))  # [10, 20, 30]

循环链表适合表示：

• 轮流调度；
• 环形缓冲区；
• 重复播放的任务序列；
• 需要从尾部回到头部的结构。

循环链表最容易出现的错误是把它当普通链表处理，继续等待 None，从而造成无限循环。

11. 双向链表

双向链表的每个节点同时保存前驱和后继引用：

None ← [prev | 10 | next] ⇄ [prev | 20 | next] → None

Python 实现：

class DNode:
    def __init__(self, value, prev=None, next_node=None):
        self.value = value
        self.prev = prev
        self.next = next_node


def remove_node(head, node):
    if node is None:
        return head

    if node.prev is None:
        head = node.next
    else:
        node.prev.next = node.next

    if node.next is not None:
        node.next.prev = node.prev

    node.prev = None
    node.next = None
    return head

删除一个已经定位的节点时，不需要再寻找它的前驱。代价是每个节点多保存一个引用，插入和删除时也要维护更多链接。

12. 链表与 Python list 的比较

不要简单地认为链表一定比 list 更适合插入。实际运行中，Python list 的连续访问通常很快；如果程序主要做遍历和随机读取，列表往往更合适。

13. 常见错误

丢失后继节点

修改链接前没有保存原来的 next，会导致剩余链表无法访问。插入时应先完成：

def link_new_node(node, new_node):
    new_node.next = node.next
    node.next = new_node

只修改了局部变量

如果函数需要改变头节点，必须返回新的头节点，并在调用处接收：

head = push_front(head, 10)

以为断开节点就等于立即释放

Python 会自动管理内存，不需要手动 free。但从链表中断开节点仍然很重要，因为它决定了结构是否正确；如果外部还有引用，被删除节点也可能继续存在。

循环链表无限遍历

普通链表可以用 current is not None 作为结束条件；循环链表必须记录起点，或维护节点数量。

把“已定位”忽略掉

链表插入和删除只有在已经知道相关节点时才是 O(1)。寻找节点的过程仍然可能需要 O(n)。

14. 按键有序地插入单链表

若希望链表保持升序，先寻找插入位置再改链接。可以用一个局部哨兵统一头部插入：

def insert_sorted(head, value):
    dummy = Node(None)
    dummy.next = head
    prev = dummy
    while prev.next is not None and prev.next.value <= value:
        prev = prev.next
    node = Node(value)
    node.next = prev.next
    prev.next = node
    return dummy.next

这里使用本章的 Node 类，重复值插到已有相等项之后。找位置最坏 O(n)，实际接入链接 O(1)；函数返回值可能是新 head，调用者应接收它。

15. 小结

• 链表由节点和引用组成，节点不要求连续存储；
• 链表按位置访问较慢，但已定位后的插入和删除很灵活；
• Python 用对象引用表达 C 语言中的指针关系；
• 修改头节点时，通常返回新的 head；
• 尾引用可以把尾部追加和链表拼接优化到 O(1)；
• 循环链表没有 None 终点，遍历必须显式判断；
• 双向链表便于向前和向后移动，但每个节点需要更多空间；
• 选择列表还是链表，要看访问模式，而不能只看某一个操作的复杂度。