Python链表 - CSP-J | C++ & Algorithm 编程研习社

手拉手的小朋友链——Python链表

想象你在操场上和同学们手拉手站成一排。如果老师想在你和小明之间插入一个新同学，只需要让前面的同学松开手，和新同学拉手，新同学再和后面的同学拉手——其他同学完全不用动。这就是链表（linked list）的核心思想：每个元素（节点）只记住下一个元素的位置，这样插入和删除都非常灵活。

相比之下，Python 的列表（list）就像全班同学按学号坐在座位上，如果中间插进一个新同学，后面所有人的座位都要往后挪一个，效率就很低。链表解决了这个问题，但代价是不能像列表那样直接通过下标（比如 list[2]）快速找到人，只能从头开始一个一个往后找。

在 CSP-J 考试中，链表经常和指针操作、模拟题一起出现。理解链表能帮你打下未来学习树、图等复杂数据结构的基础。

1. 链表的“积木”——节点类

链表的最小单位是节点（node）。每个节点有两个部分：

数据（data）：存放真正的内容，比如一个数字、一个名字。
指针（next）：指向下一个节点的“地址”（在 Python 里就是下一个节点的引用）。

用类来定义节点非常直观：

class Node:
    def __init__(self, data):    # 构造方法，data是传给节点的数据
        self.data = data          # 存储数据，例如整数10
        self.next = None          # 指向下一个节点的指针，初始为None

每个节点创建时，它的 next 是 None，表示暂时没有连到任何人。

2. 手动连接——创建一条简单链表

有了节点，像小朋友手拉手一样，把它们的 next 属性指向下一个节点，就形成了链表。

# 创建三个节点，分别存储10、20、30
node1 = Node(10)     # 第一个节点，数据为10
node2 = Node(20)     # 第二个节点，数据为20
node3 = Node(30)     # 第三个节点，数据为30

# 手拉手连接起来
node1.next = node2   # node1指向node2
node2.next = node3   # node2指向node3
# node3.next 仍然是None，表示链表结束

# 从第一个节点开始遍历
current = node1            # current是“当前指针”，从第一个节点出发
while current is not None: # 只要当前节点不为空
    print(current.data, end=" -> ")   # 打印节点的数据
    current = current.next             # 移动到下一个节点
print("None")
# 输出: 10 -> 20 -> 30 -> None

这个遍历过程就像你沿着队伍从排头走到排尾，每经过一个人就喊他的名字。当 current 变成 None 时，说明走到尽头。

3. 在中间插入新节点——像插队一样灵活

假设你已经有链表 10 -> 20 -> 30，现在想在 10 和 20 之间插入一个 15。只需要两步：

让新节点 15 的 next 指向 20（原来 10 指向的节点）。
让 10 的 next 指向新节点 15。

注意：顺序不能错！如果先改 10 指向新节点，就会丢失对 20 的引用，后面的节点都找不到了。

# 已有链表: 10 -> 20 -> 30
node_new = Node(15)               # 创建新节点，数据为15

# 第一步：新节点指向20
node_new.next = node1.next        # node1.next本来是node2（20）
# 第二步：让10指向新节点
node1.next = node_new

# 遍历验证
current = node1
while current is not None:
    print(current.data, end=" -> ")
    current = current.next
print("None")
# 输出: 10 -> 15 -> 20 -> 30 -> None

你看，15 成功插入，其他节点都没移动。如果是列表，插入后面所有元素都要后移一位，很麻烦。

4. 删除一个节点——直接跳过它

删除的思路更简单：让被删除节点的前一个节点直接指向被删除节点的后一个节点。比如删除刚才插入的 15：

# 现在链表是 10 -> 15 -> 20 -> 30
# 要删除 15，让 10 跳过 15 指向 20
node1.next = node_new.next        # node_new.next是node2（20）
# 此时 15 这个节点虽然还存在，但没有任何节点指向它，会被 Python 自动回收

# 遍历验证
current = node1
while current is not None:
    print(current.data, end=" -> ")
    current = current.next
print("None")
# 输出: 10 -> 20 -> 30 -> None

如果删除的是最后一个节点，只需要让前一个节点的 next 变成 None 即可。

5. 新手容易犯的错误

插入时指针赋值顺序颠倒 错误写法：
```
node1.next = node_new   # 先改了10的next，丢失了20
node_new.next = node1.next  # 这时node1.next已经是node_new了，成了自己指自己
```
结果链表变成 10 -> 15 -> 15 -> … 死循环。先连新节点到后面，再改前面节点的指向。
遍历时用 while current: 而不是 while current is not None: 两者效果一样，但显式写 is not None 更清晰，能避免把 data = 0 的情况误判为结束（虽然 0 也是真值，但用 is not None 可读性更好）。
删除节点时忘记特殊处理头节点 如果要删除第一个节点，需要单独更新链表头指针（比如 head = head.next）。上面的例子中我们直接把 node1 当作头节点，如果要删除 node1，就不能用 node1.next = … 了，而是 head = head.next。
对空链表进行操作 如果链表为空（head is None），调用 head.next 会报 AttributeError。所以一定要先检查 None。

6. 完整可运行示例——用类管理一个链表

为了方便操作，我们可以写一个简单的 LinkedList 类，包含插入、删除、遍历等常用方法。这个示例非常适合考试和练习。

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
        current = self.head
        while current.next is not None: # 找到最后一个节点
            current = current.next
        current.next = new_node        # 让最后一个节点指向新节点

    def insert_after(self, target_data, data):
        """在第一个值为target_data的节点后面插入新节点"""
        current = self.head
        while current is not None and current.data != target_data:
            current = current.next
        if current is None:            # 没找到目标
            print(f"节点 {target_data} 不存在，无法插入")
            return
        new_node = Node(data)
        new_node.next = current.next   # 新节点指向目标节点的下一个
        current.next = new_node        # 目标节点指向新节点

    def delete(self, data):
        """删除第一个值为data的节点"""
        if self.head is None:          # 空链表
            return
        # 如果要删除头节点
        if self.head.data == data:
            self.head = self.head.next
            return
        current = self.head
        while current.next is not None and current.next.data != data:
            current = current.next
        if current.next is None:       # 没找到
            print(f"节点 {data} 不存在")
            return
        current.next = current.next.next  # 跳过要删除的节点

    def display(self):
        """打印整个链表"""
        current = self.head
        while current is not None:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

# ---------- 使用示例 ----------
# 创建一个链表
my_list = LinkedList()

# 依次添加 10, 20, 30
my_list.append(10)
my_list.append(20)
my_list.append(30)
print("初始链表：")
my_list.display()   # 输出: 10 -> 20 -> 30 -> None

# 在20后面插入25
my_list.insert_after(20, 25)
print("在20后面插入25：")
my_list.display()   # 输出: 10 -> 20 -> 25 -> 30 -> None

# 删除节点25
my_list.delete(25)
print("删除25之后：")
my_list.display()   # 输出: 10 -> 20 -> 30 -> None

# 删除头节点10
my_list.delete(10)
print("删除头节点10之后：")
my_list.display()   # 输出: 20 -> 30 -> None

这个例子把常见的链表操作封装成了方法，你可以在自己的代码中直接用。考试时如果题目要求实现链表，通常写类似的类就够用了。

7. 总结与相关知识点

链表的核心优势：插入、删除快（O(1)，只要知道位置），不像列表需要移动大量元素。 主要缺点：不能随机访问（必须从头遍历），且每个节点多占一个指针的内存。

生活中类似链表的例子还有很多：火车车厢（每一节连接下一节）、贪吃蛇的身体（每一段记住下一段的位置）、音乐播放器的“下一首”列表。

在你学习了单向链表之后，可以继续了解：

双向链表：每个节点同时存前一个和后一个节点的指针，可以双向遍历。
循环链表：最后一个节点指向第一个节点，形成环。
栈和队列：可以用链表实现，比列表更高效（尤其是当频繁插入删除时）。

在 CSP-J 考试中，链表常与模拟题（如约瑟夫问题、排队问题）结合，也会出现在指针操作相关的选择题里。掌握链表的基本操作，能帮你顺利解决这类题目。如果还想深入学习，可以试试用链表实现 LRU 缓存、多项式加法等经典问题。

例题精讲