第4课 - 双向链表与循环链表

1. 学习目标

学完本课，你将能够：

理解双向链表与单链表在结构上的区别，并说出其优势。
理解循环链表的特点及其与普通链表的不同。
掌握使用哨兵节点（Sentinel）简化链表边界操作的思路。
实现双向链表和循环链表的基本操作（插入、删除、遍历）。
分析双向链表在时间复杂度上带来的改进。

2. 核心概念

双向链表

想象一条单行道，车辆只能向前开（单向链表）。双向链表则是一条双行道，不仅允许你前往下一个节点（next），还能轻松返回到上一个节点（prev）。每个节点除了存储数据外，都包含两个指针：一个指向后继节点，另一个指向前驱节点。

优势：可以更灵活地进行遍历和操作，特别是在需要频繁查找前驱节点的场景（如删除当前节点），避免了从头再遍历一次的开销。其时间复杂度通常为 O(1)。
代价：每个节点需要额外存储一个指针，占用更多内存。

循环链表

普通的单链表或双向链表，尾部的 next 指针都指向 null。而循环链表打破了这个“终点”，它的尾部节点的 next 指针会指回头部节点，形成一个环。双向循环链表则是一个双向的环。

特点：没有明确的开始和结束，遍历时需要设置明确的条件（例如，当再次遇到头节点时停止）。
应用：常用于需要循环处理数据的场景，如操作系统中的进程调度轮询、音乐播放器的“循环播放”模式。

哨兵节点（Sentinel）

这是一种编程技巧。我们创建一个特殊的、不存储实际数据的节点，作为链表的“守卫”。它通常位于链表的头部（有时也用于尾部）。

作用：它像一道屏障，统一了链表为空和只有一个元素时的操作逻辑，从而减少了代码中大量的 if-else 边界判断，使插入和删除操作的代码更简洁、不易出错。
实现：在双向链表中，哨兵节点的 prev 指向自身，next 也指向自身，代表一个空的链表。

3. 代码示例

下面我们将用 Python 实现一个带哨兵节点的双向链表，并演示一个简单的循环链表概念。

示例1：带哨兵节点的双向链表

class Node:
    """双向链表节点"""
    def __init__(self, data):
        self.data = data
        self.prev = None  # 指向前一个节点
        self.next = None  # 指向后一个节点

class DoublyLinkedList:
    def __init__(self):
        # 创建哨兵节点，并自我循环
        self.sentinel = Node(None)
        self.sentinel.next = self.sentinel
        self.sentinel.prev = self.sentinel

    def append(self, data):
        """在链表尾部追加节点"""
        new_node = Node(data)
        # 找到当前的最后一个节点（即哨兵节点的前一个节点）
        last_node = self.sentinel.prev
        
        # 新节点的 `next` 指向哨兵（因为要放在最后）
        new_node.next = self.sentinel
        # 新节点的 `prev` 指向原来的最后一个节点
        new_node.prev = last_node
        
        # 更新原最后节点的 `next` 指向新节点
        last_node.next = new_node
        # 更新哨兵节点的 `prev` 指向新节点（新节点成为新的“最后”节点）
        self.sentinel.prev = new_node
        print(f"追加节点: {data}")

    def delete(self, node):
        """删除指定节点"""
        if node is self.sentinel:
            print("错误：不能删除哨兵节点！")
            return
        
        # 将前驱节点和后继节点直接连接起来，跳过要删除的节点
        prev_node = node.prev
        next_node = node.next
        
        prev_node.next = next_node
        next_node.prev = prev_node
        
        print(f"删除节点: {node.data}")
        # 释放节点（在Python中由垃圾回收处理）
        del node

    def traverse_forward(self):
        """正向遍历链表"""
        current = self.sentinel.next
        elements = []
        # 当回到哨兵节点时停止
        while current is not self.sentinel:
            elements.append(str(current.data))
            current = current.next
        print("正向遍历: ", " <-> ".join(elements) if elements else "空链表")

    def traverse_backward(self):
        """反向遍历链表"""
        current = self.sentinel.prev
        elements = []
        while current is not self.sentinel:
            elements.append(str(current.data))
            current = current.prev
        print("反向遍历: ", " <-> ".join(elements) if elements else "空链表")

# 测试双向链表
dll = DoublyLinkedList()
dll.traverse_forward()  # 输出: 正向遍历:  空链表

dll.append(10)
dll.append(20)
dll.append(30)
dll.traverse_forward()  # 输出: 正向遍历: 10 <-> 20 <-> 30
dll.traverse_backward() # 输出: 反向遍历: 30 <-> 20 <-> 10

# 删除中间节点
node_to_delete = dll.sentinel.next.next # 假设我们要删除值为20的节点
dll.delete(node_to_delete)
dll.traverse_forward()  # 输出: 正向遍历: 10 <-> 30

示例2：简单的循环链表遍历逻辑

class CircularNode:
    """循环链表节点（单向）"""
    def __init__(self, data):
        self.data = data
        self.next = None

def create_circular_list():
    """创建一个简单的循环链表 A -> B -> C -> A"""
    node_a = CircularNode('A')
    node_b = CircularNode('B')
    node_c = CircularNode('C')
    
    # 建立循环连接
    node_a.next = node_b
    node_b.next = node_c
    node_c.next = node_a  # 关键：尾指向头，形成环
    
    return node_a  # 返回头节点作为入口

def traverse_circular_list(head):
    """遍历循环链表，再次遇到头节点时停止"""
    if head is None:
        return
    
    current = head
    elements = []
    while True:
        elements.append(str(current.data))
        current = current.next
        # 当再次回到起点时，退出循环
        if current is head:
            break
    print("循环链表遍历: ", " -> ".join(elements))

# 测试循环链表
circular_head = create_circular_list()
traverse_circular_list(circular_head) # 输出: 循环链表遍历: A -> B -> C -> A

4. 实践练习

练习1：基础双向链表操作

基于上面的 DoublyLinkedList 类，实现一个 prepend(data) 方法，用于在链表头部（哨兵节点之后）插入一个新节点。

# 测试代码
dll = DoublyLinkedList()
dll.append(20)
dll.append(30)
dll.prepend(10) # 新方法
dll.traverse_forward() # 预期输出: 正向遍历: 10 <-> 20 <-> 30

练习2：循环链表中查找

给定一个循环链表的头节点和一个目标值，写一个函数 find_in_circular(head, target)，如果找到目标值返回 True，否则返回 False。注意处理链表为空的情况。

# 测试代码
head = create_circular_list() # 包含 A, B, C
print(find_in_circular(head, 'B')) # 预期输出: True
print(find_in_circular(head, 'D')) # 预期输出: False
print(find_in_circular(None, 'A')) # 预期输出: False

练习3：综合挑战 - 双向循环链表

尝试实现一个双向循环链表的类 DoublyCircularLinkedList。它没有哨兵节点，但需要满足：

头节点的 prev 指向尾节点。
尾节点的 next 指向头节点。
实现 append(data) 和 display() 方法。display() 方法应能正确遍历并打印出环形结构。

# 测试代码
dcll = DoublyCircularLinkedList()
dcll.append(1)
dcll.append(2)
dcll.append(3)
dcll.display() # 预期输出: 正向环形: 1 <-> 2 <-> 3 <-> (回到1)

5. 常见错误

忘记更新两个方向的指针：在双向链表中插入或删除节点时，必须同时更新 prev 和 next 指针。例如，删除一个节点 X 时，既要让 X.prev.next = X.next，也要让 X.next.prev = X.prev。漏掉任何一步都会导致链表断裂。
循环链表遍历条件错误：遍历循环链表时，使用 while current.next is not head 的条件会在遍历最后一个节点后退出，导致最后一个节点的数据没有被处理。正确的做法是先处理当前节点，再移动，并在移动后检查是否回到起点。
混淆哨兵节点与第一个数据节点：在使用哨兵节点的链表中，哨兵节点不存储有效数据。遍历时应从 sentinel.next 开始。初学者容易错误地将哨兵节点作为第一个数据节点处理。
内存泄漏（在某些语言中）：在C/C++等语言中，删除节点后需要手动 free 或 delete 内存。在Python中，垃圾回收机制会处理，但良好的习惯是将被删除节点的指针设为 None，以断开引用。

6. 小结

双向链表通过为每个节点增加 prev 指针，实现了高效的双向遍历，使得删除、查找前驱等操作的时间复杂度降为 O(1)，代价是增加了内存开销。
循环链表通过让尾节点指向头节点，形成了一个没有自然终点的环状结构，非常适合需要周期性处理数据的应用场景。
哨兵节点是一个强大的编程技巧，它充当链表的“守护者”，通过消除对空链表或边界情况的特殊判断，显著简化了插入和删除操作的代码逻辑，提高了代码的可读性和健壮性。
链表（单、双、循环）是构建栈、队列、哈希表等更复杂数据结构的基础，深入理解它们的变体对于后续学习至关重要。

练习编辑器

rust