第3课 - 链表

学习目标

通过本课的学习，你将能够：

理解链表的概念、结构以及它与数组的根本区别。
掌握链表节点（Node）的定义和基本表示方法。
学会使用代码实现链表的基本操作：创建、遍历、头部插入、尾部插入和删除指定节点。
能够分析链表操作的时间复杂度。

核心概念

什么是链表？

想象一列火车。每一节车厢（节点）都连接着下一节车厢。车厢本身装着货物（数据），车厢之间通过挂钩（指针/引用）连接在一起。我们不需要知道所有车厢在轨道上的绝对位置，只要知道第一节车厢在哪里（头指针 head），就能通过“挂钩”访问到整列火车。这就是链表。

与数组最大的不同是，链表中的数据在内存中不是连续存储的。每个节点可以散落在内存的任意位置，它们通过指针“手拉手”串起来。

节点（Node）

链表的每个元素称为一个节点。一个节点包含两部分：

数据域（data）：存储实际的数据。
指针域（next）：存储指向下一个节点的内存地址（在Python等高级语言中，可以理解为存储了下一个节点对象的引用）。

代码表示一个节点：

class Node:
    def __init__(self, data):
        self.data = data # 数据域
        self.next = None # 指针域，初始指向None

可以将这个类的实例想象成一节车厢，self.data是车厢里的货物，self.next是连接下一节车厢的挂钩。

代码示例

下面我们将实现一个简单的单向链表，并演示一些基本操作。

class Node:
    """链表节点类"""
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    """链表类，管理节点"""
    def __init__(self):
        self.head = None # 初始化链表时，头指针为空

    def append(self, data):
        """在链表尾部添加一个节点"""
        new_node = Node(data)
        # 如果链表是空的，则新节点就是头节点
        if self.head is None:
            self.head = new_node
            return
        # 如果链表不为空，需要遍历到最后一个节点
        last_node = self.head
        while last_node.next: # 当下一个节点存在时
            last_node = last_node.next # 移动到下一个节点
        last_node.next = new_node # 将最后一个节点的next指向新节点

    def prepend(self, data):
        """在链表头部添加一个节点"""
        new_node = Node(data)
        new_node.next = self.head # 新节点的next指向原来的头节点
        self.head = new_node # 更新头指针，指向新节点

    def delete_node(self, key):
        """删除第一个数据域为key的节点"""
        current = self.head
        # 情况1：链表为空
        if current is None:
            return
        # 情况2：要删除的是头节点
        if current.data == key:
            self.head = current.next # 将头指针指向下一个节点
            current = None # 释放原头节点（在Python中由GC管理）
            return
        # 情况3：要删除的是中间或尾部节点
        prev = None # 用来记录前一个节点
        while current and current.data != key:
            prev = current
            current = current.next
        # 如果找到了要删除的节点
        if current:
            prev.next = current.next # 将前一个节点的next跳过当前节点，直接指向后一个节点
            current = None
        else:
            print(f"未找到值为{key}的节点")

    def print_list(self):
        """遍历并打印整个链表"""
        nodes = []
        current = self.head
        while current:
            nodes.append(str(current.data))
            current = current.next
        print(" -> ".join(nodes) + " -> None")

# === 使用链表 ===
my_list = LinkedList()

# 1. 在尾部添加元素
my_list.append(1)
my_list.append(2)
my_list.append(3)
print("尾部添加1, 2, 3后：")
my_list.print_list() # 输出：1 -> 2 -> 3 -> None

# 2. 在头部添加元素
my_list.prepend(0)
print("头部添加0后：")
my_list.print_list() # 输出：0 -> 1 -> 2 -> 3 -> None

# 3. 删除节点
my_list.delete_node(2)
print("删除数据为2的节点后：")
my_list.print_list() # 输出：0 -> 1 -> 3 -> None

my_list.delete_node(0)
print("删除数据为0的节点（头节点）后：")
my_list.print_list() # 输出：1 -> 3 -> None

实践练习

练习1：基础 - 在指定位置插入节点

在 LinkedList 类中，增加一个 insert_after_node(self, prev_node_data, new_data) 方法。该方法在第一个数据等于 prev_node_data 的节点之后，插入一个数据为 new_data 的新节点。如果找不到 prev_node_data，则打印提示信息。

要求：添加测试代码，在链表 [1, 2, 3] 中，2 后面插入 2.5，预期输出为 1 -> 2 -> 2.5 -> 3 -> None。

练习2：中等 - 反转链表

实现一个 reverse(self) 方法，将整个链表反转。例如，1 -> 2 -> 3 -> None 变为 3 -> 2 -> 1 -> None。

提示：这是链表最经典的练习之一。需要使用三个指针（prev, current, next_node）来遍历并逐步改变每个节点的 next 指向。

练习3：进阶 - 合并两个有序链表

编写一个函数 merge_sorted_lists(l1, l2)，接收两个已排序的链表（l1, l2），并返回一个新的、合并后的有序链表。不能简单地将一个链表链接到另一个后面，需要逐一比较节点值来构建新链表。

示例：l1: 1->3->5, l2: 2->4->6，结果应为 1->2->3->4->5->6。

常见错误

忘记更新头指针：在链表头部进行插入或删除操作时，必须更新 self.head 的指向，否则新链表结构会丢失。
- 错误：new_node.next = self.head (仅设置新节点的next)
- 正确：new_node.next = self.head; self.head = new_node (两步都做)
遍历时丢失引用：在删除节点时，如果没有用一个 prev 指针记录前一个节点，当你找到当前节点 (current) 想执行 prev.next = current.next 时，prev 可能根本没被定义。
- 错误：只使用 current 遍历，删除时找不到前驱节点。
- 正确：使用 prev 和 current 双指针同步遍历。
边界条件处理不全：没有考虑链表为空、只有一个节点、要删除的是头/尾节点等特殊情况。在编写任何链表操作时，首先要考虑这些边界情况。
（概念性错误）以为链表像数组一样有下标：链表无法通过索引 O(1) 直接访问中间元素。要访问第 n 个元素，必须从头开始遍历 n 次，时间复杂度为 O(n)。不要尝试写 my_list[5] 这样的代码。

小结

链表是一种通过指针将离散的节点串联起来的线性数据结构。
核心组成是 Node 类，包含 data 和 next 两个属性。
通过维护一个 head 指针来标识整个链表。
基本操作：遍历 (print_list)、尾部插入 (append)、头部插入 (prepend)、删除节点 (delete_node)。
与数组相比，链表的插入和删除操作在知道前驱节点的情况下非常高效 (O(1))，但随机访问效率很低 (O(n))。
编写链表代码时，画图可以帮助你清晰地理解指针变化，是避免错误的最佳习惯。

练习编辑器

rust