C++自学第二课（链表）

黄昏中的落雁

2026-09-16 21:58:22

发布于：湖南

7阅读

0回复

0点赞

**链表（ $Linked List$ ）**是一种基础的数据结构，用于存储一系列元素。与数组（ $Array$ ）不同，链表中的元素在内存中不是连续存放的，而是通过“指针”或“引用”相互连接。
让我用一个比喻来给你解释解释：
想象你参加一个寻宝游戏：

你找到第一个宝箱（头节点），里面除了金币（数据），还有一张写着“下一个宝箱在花园的橡树下”的纸条（指针）。

你跑到橡树下找到第二个宝箱，里面同样有金币和下一张指向第三个宝箱的纸条。

这个过程一直持续，直到你打开一个宝箱，发现里面的纸条写着“游戏结束”（指向空值 $null$ ）。
在这个游戏里，你不需要知道所有宝箱事先放在哪里（内存不连续），你只需要从第一个宝箱开始，顺着纸条一个个找下去。
2. 链表的组成单元：节点（ $Node$ ）
链表由一个个“节点”组成。每个节点通常包含两个部分：
1.
数据域（ $Data$ ）：存储实际的数据（比如数字、字符串、对象等）。
2.
指针域（ $Next$ ）：存储下一个节点的内存地址。
3. 链表的类型（扩展）

单链表（ $Singly Linked List$ ）：就像上面的寻宝游戏，每个节点只有一个指向下一个节点的指针。只能单向遍历。

双链表（ $Doubly Linked List$ ）：每个节点有两个指针，一个指向下一个节点，另一个指向上一个节点。可以双向遍历，方便反向操作。

循环链表（ $Circular Linked List$ ）：最后一个节点的指针不是指向空，而是指回头部的第一个节点，形成一个环。
4. 优缺点总结
优点：

动态大小：不需要预先指定大小，可以根据需要动态分配内存。

高效的插入和删除：在已知要操作节点位置的情况下，插入和删除操作非常快，只需改变几个指针的指向，时间复杂度为 $O(1)$ 。
缺点：

访问速度慢：无法像数组那样通过下标直接访问元素，必须从头开始遍历，平均时间复杂度为 $O(n)$ 。

额外的内存开销：每个节点都需要额外的空间来存储指针。

缓存不友好：由于节点在内存中分散， $CPU$ 缓存的命中率低，实际性能可能不如数组。
示例（ $python$ ）

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 not self.head:
            self.head = new_node
            return
        # 遍历到链表末尾
        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node

    def print_list(self):
        """打印链表中的所有元素"""
        current_node = self.head
        while current_node:
            print(current_node.data, end=" -> ")
            current_node = current_node.next
        print("None")

# 使用示例
my_list = LinkedList()
my_list.append(10)
my_list.append(20)
my_list.append(30)
my_list.print_list()  # 输出: 10 -> 20 -> 30 -> None