CC++ & Algorithm

Python链表

极难5
语言版本：C++Python
概述：学习用类创建链表，像火车车厢一样连接数据，灵活地插入和删除节点。

Python链表——像火车一样灵活的数据结构

你有没有想过，如果全班同学手拉手排成一队，每人都知道后面是谁，那么要插队或者让某个人离开，只需要改变两个人的“手拉手”关系，其他人完全不用动。这就是链表干的事！链表就像一列火车：每节车厢（节点）不仅装着货物（数据），还连着下一节车厢（指针）。如果要增加或拆除一节车厢，只需要改变连接，不用移动其他车厢。这是链表和列表最大的不同：列表像一排固定座位，插入或删除时后面所有人都要移动，而链表只需要改几处连接。

链表的结构

每个节点是一个对象，包含两个部分：data（数据）和next（指向下一个节点的指针）。最后一个节点的next是None，表示后面没车厢了。整列火车由“头节点”（head）指向第一节车厢，如果火车是空的，head就是None。

生活例子：想象你每天放学排队买零食。每个人排好队，只记住后面的人是谁。如果你想插队到第一个位置，你只需要让后面的人记住你（新节点指向原队首），然后大家把队首改成你。如果中间有人离开，就让前面的人记住离开者后面的人。不需要移动其他人。

用Python创建节点

我们用class来定义节点，就像设计一节车厢的图纸：

class Node:
    def __init__(self, data):  # data 是我们要存的数据，比如名字、分数
        self.data = data       # 这节车厢里装的东西
        self.next = None       # 下一节车厢，一开始不知道是谁，设为None

常见错误1：忘记把next初始化为None，导致它指向一个随机地址，程序会出错。

创建链表类

链表类就像火车调度室，它知道第一节车厢是谁（head）。所有操作都通过它来完成。

class LinkedList:
    def __init__(self):
        self.head = None  # 链表最开始是空的，头节点是None

遍历链表——从头走到尾

遍历就是“顺着next指针，一节一节访问”。比如我们要把每个节点里的数据打印出来。

    def display(self):
        elements = []            # 存放所有数据的列表
        current = self.head      # current 表示当前走到哪节车厢
        while current:           # 只要当前车厢不是None（即没到终点）
            elements.append(str(current.data))  # 把数据变成字符串放进列表
            current = current.next               # 走到下一节
        print(" -> ".join(elements))  # 用箭头连接输出，比如 1 -> 2 -> 3

常见错误2：在循环里忘记更新current = current.next，会导致死循环。

在头部插入节点——插队到最前面

新同学想排第一个怎么办？很简单：新节点先指向原来的头节点，然后让头节点变成新节点。

    def insert_at_beginning(self, data):
        new_node = Node(data)        # 造一个新车厢
        new_node.next = self.head    # 新车厢指向原来的第一节车厢
        self.head = new_node         # 现在新车厢成了第一节

生活例子：小明的零花钱是3元，小红是2元，小刚是1元。他们按金额从大到小排好队（3->2->1）。现在小美有5元，她想插队到最前面：她先记住小明的位置，然后让队首变成她，她后面跟着小明。

删除指定值的节点——让某人离开

要删除某个数据，比如删除值为2的节点。需要找它的前一个节点，然后让前一个的next跳过它。

    def delete_value(self, value):
        current = self.head
        # 如果要删除的是头节点
        if current and current.data == value:
            self.head = current.next  # 头节点指向原来第二个节点
            return
        # 查找要删除节点的前一个节点
        prev = None
        while current and current.data != value:
            prev = current
            current = current.next
        if current is None:          # 从头找到尾都没找到
            return                   # 什么也不做
        prev.next = current.next     # 前一个节点直接连到后一个，跳过当前节点

常见错误3：忘记处理头节点的情况，直接去循环里找，会导致头节点删不掉。

常见错误4：在循环里让prev = current和current = current.next顺序写反，导致prev始终等于current，无法找到前一个节点。

完整可运行的示例

下面我们把所有功能放在一起，再增加一个“在尾部插入”的方法，更贴近生活（比如排队买饭，新同学只能排在队尾）。注意：在尾部插入需要先遍历到最后一个节点，效率不如头部插入高。

class Node:
    def __init__(self, data):  # data: 要存储的数据（如分数、名字）
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None  # 初始空链表

    # 在头部插入（插队）
    def insert_at_beginning(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    # 在尾部插入（排队）
    def insert_at_end(self, data):
        new_node = Node(data)
        if self.head is None:     # 如果链表是空的，新节点就是头
            self.head = new_node
            return
        current = self.head
        while current.next:       # 找到最后一个节点（next为None的那个）
            current = current.next
        current.next = new_node   # 最后一个节点连上新节点

    # 删除指定值的节点
    def delete_value(self, value):
        current = self.head
        # 如果要删的是头节点
        if current and current.data == value:
            self.head = current.next
            return
        prev = None
        while current and current.data != value:
            prev = current
            current = current.next
        if current is None:
            print(f"没找到值为 {value} 的节点")
            return
        prev.next = current.next

    # 显示所有数据
    def display(self):
        elements = []
        current = self.head
        while current:
            elements.append(str(current.data))
            current = current.next
        print(" -> ".join(elements) if elements else "链表为空")

# 测试一下：模拟考试成绩排名（从高到低）
scores = LinkedList()
scores.insert_at_beginning(92)   # 小明
scores.insert_at_beginning(88)   # 小红（插到前面）
scores.insert_at_end(65)         # 小刚（排在最后）
scores.insert_at_beginning(98)   # 小华（新第一名）
scores.display()                 # 输出: 98 -> 88 -> 92 -> 65

# 删除88分的人
scores.delete_value(88)
scores.display()                 # 输出: 98 -> 92 -> 65

# 删除不存在的分数
scores.delete_value(100)         # 输出提示

运行结果：

98 -> 88 -> 92 -> 65
没找到值为 100 的节点
98 -> 92 -> 65

链表的优缺点小结

优点缺点
插入和删除节点非常快（只要知道位置，O(1)时间）不能像列表那样通过下标直接访问，必须从头开始找（O(n)时间）
不需要连续内存，可以利用碎片空间每个节点需要额外空间存储指针
大小可以动态增长代码比列表复杂，容易出错

常见错误总结（新手必看）

  1. 忘记初始化next：节点创建时next不设成None，会导致指向垃圾地址。
  2. 死循环：遍历时忘记更新current = current.next。
  3. 头节点操作遗漏：删除或插入时没有单独处理头节点的情况。
  4. 逻辑顺序错误：在插入时先改了self.head，再去设置新节点的next，导致链表断开。
  5. 空链表操作：在空链表上调用delete_value或display时，要检查self.head是否为None。
  6. 引用混乱：在删除循环里，prev和current的赋值顺序要搞清楚：先保存当前节点到prev，再移动current到下一个。

接下来学什么？

链表有很多变种，可以继续学习：

  • 双向链表：每个节点既有next指针指后面，也有prev指针指前面，方便向前遍历。
  • 循环链表：最后一个节点的next指向头节点，形成环，适合做循环队列（比如轮流点名）。
  • 栈和队列：可以用链表实现，插入和删除都在两端进行。
  • 树和图：链表的指针思想是更复杂数据结构的基础。

理解链表就像掌握了一把万能钥匙——以后遇到需要频繁增删数据的场景，你都知道可以用链表来高效解决。现在你可以试着用链表做一个“学生成绩管理系统”，或者模拟游戏中的“队伍排列”，练练手吧！

例题精讲

1单选题

在Python中定义一个单链表节点类，以下哪个定义是正确的？

Aclass Node: def __init__(self, data): self.data = data; self.next = None
Bclass Node: def __init__(self, data, next=None): self.data = data; self.next = next
Cclass Node: def __init__(self): self.data = None; self.next = None
Dclass Node: def __init__(self, data): self.data = data; self.next = Node()
2判断题

在单链表中，已知待插入位置的前驱节点，插入一个新节点的时间复杂度为O(n)。

3填空题
以下代码实现单链表的尾部插入。请补充空缺部分。\nclass Node:\n    def __init__(self, data):\n        self.data = data\n        self.next = None\n\nclass LinkedList:\n    def __init__(self):\n        self.head = None\n\n    def append(self, data):\n        new_node = Node(data)\n        if self.head is None:\n            ___ = new_node\n            return\n        current = self.head\n        while current.next is not None:\n            current = current.next\n        ___.next = new_node
4单选题

在单链表中，删除节点p（已知p为待删除节点，且p不是尾节点）的正确操作是？

Ap = p.next; p = None
Bp.data = p.next.data; p.next = p.next.next
Cp.next = p.next.next; p.data = p.next.data
Dp = p.next.next
5判断题

在Python中，使用类实现的链表比使用列表（list）进行频繁插入和删除操作时效率更高。