CC++ & Algorithm

链表的概念与实现

较难11
语言版本：通用
概述：链表像一列手拉手的朋友，每个节点拉着下一个，插入和删除非常灵活，但查找需要从头一个个找。

链表：像手拉手接龙一样灵活的数据结构

想象一下，课间活动时，小朋友们一个接一个拉着前面同学的衣服，连成一列长长的“火车”。第一个小朋友没有拉任何人，最后一个小朋友后面没有人。如果你想加入一个新小朋友，只需要让他拉住前一个小朋友的衣服，再让后面小朋友拉住他——完全不需要所有人都重新排队。这和数组的“搬动整个储物柜”相比，是不是方便多了？

在计算机里，这种结构就叫 链表（Linked List） 。它是一群 节点（Node） 手拉手串起来的序列。每个节点有两个“口袋”：一个装自己的数据，另一个装一个 指针，指向下一个节点。最后一个节点的指针指向“空”（NULL 或 None），表示后面没人了。

链表的示意图（单向链表）：

     Head
       |
       v
    +------+      +------+      +------+
    | 10   |      | 20   |      | 30   |
    | next |---->| next |---->| next |----> NULL
    +------+      +------+      +------+

头指针 指向第一个节点，就像整列火车的“车头”，通过它我们能访问整条链。

为什么叫“链表”？——比数组“自由”在哪？

对比项数组链表
存储方式内存中连续一块节点分散在各处，靠指针连接
大小固定创建时定死，扩容麻烦动态增长，随时插入新节点
随机访问直接通过下标取，O(1)必须从头一个一个找，O(n)
插入/删除（已知位置）需要移动后面所有元素，O(n)只改相邻指针，O(1)
额外内存几乎没有每个节点多一个指针（双向链表两个）

生活的例子：如果你想在课间操队形中间加一个人，

  • 用数组：所有人后退一步，空出位置 → 大家都要动。
  • 用链表：让新同学拉住前面同学，后面的同学再拉住新同学 → 只动三个人。

链表的“骨骼”：节点和指针

每个节点像一块乐高积木，有两个部分：

  • data：存放实际数据，可以是数字、文字、甚至一个对象。
  • next：存放指向下一个节点的“箭头”（指针）。

在代码中，我们会先定义节点结构（C++ 用 struct 或 class，Python 用 class）。

生活中的比喻：节点就像火车车厢，data 是车厢里装的货物，next 是连接下一节车厢的挂钩。挂钩只能指向下一节，不能往回指（单向链表）。

链表的三种常见“队形”

  • 单向链表：每个节点只有指向下一个的指针。查找只能从头到尾。
  • 双向链表：每个节点有两个指针，一个指向前一个，一个指向后一个。可以双向查找，但每个节点多占一个指针空间。
  • 循环链表：最后一个节点的 next 指向第一个节点，形成一个环。常用来实现“轮询”任务。

本文重点讲最基础的 单向链表。

链表的“体操”：基本操作详解

1. 创建链表——从空集开始

一开始，链表是空的——头指针指向 NULL。我们要往里面加节点。

2. 插入节点——学会三个位置

头部插入： 新节点变成新的头，它的 next 指向原来的头。

尾部插入： 需要先找到最后一个节点（它的 next 是 NULL），然后让最后一个节点的 next 指向新节点。

中间插入： 比如要在节点B和C之间插入新节点X，需要先找到B，然后让 X 的 next 指向 C，再让 B 的 next 指向 X。顺序很重要！ 如果先改了 B 的 next，就找不到 C 了。

3. 删除节点——断开“挂钩”

删除头部： 直接把头指针指向第二个节点，再释放原来的头节点。

删除中间或尾部： 需要找到要删除节点的前一个节点，让它跳过要删除的节点，直接指向后一个节点。然后释放被删除的节点（C++ 中手动 delete，Python 自动回收）。

4. 遍历与查找——一步一步走

从 head 开始，用一个指针 cur 依次指向每个节点，直到 cur 为 NULL。查找某个值也是同样的方式，一边走一边比较。

新手常犯的“坑”

  1. 忘记更新指针导致链表断裂
    比如在中间插入时，如果先改了前一个节点的 next，后面的节点就找不到了。正确顺序：先设置新节点的 next 指向后一个节点，再改前一个节点的 next。

  2. 头指针丢失
    如果在插入或删除头部时，没有正确更新 head，整个链表就丢了。比如在 Python 中插入头部要返回新 head，否则外面还是旧的 head。

  3. 空指针访问
    比如遍历到最后一个节点后，你还想访问 cur->next，但 cur 是 NULL，程序会崩溃。务必先判断是否为 NULL。

  4. 内存泄漏（C++）
    用 new 创建的节点，不再使用时必须 delete。否则程序运行久了，内存越占越多。

  5. 死循环
    如果某个节点的 next 不小心指向了前面节点，遍历时会永远跑不完。检查代码，确保不会形成意外的环。

完整可运行的代码示例

下面用 C++ 和 Python 分别实现完整的链表操作，包含所有主要功能，代码中每行变量定义都有中文注释。

C++ 完整代码

#include <iostream>
using namespace std;

// 定义节点结构体
struct Node {
    int data;   // 数据域，存放数值（比如考试成绩：95分）
    Node* next; // 指针域，指向下一个节点（像挂钩）
    
    // 构造函数，方便创建节点时赋初值
    Node(int val) : data(val), next(nullptr) {}
};

// 打印链表：从头开始输出每个节点的值
void printList(Node* head) {
    Node* cur = head;  // cur 是当前遍历到的节点指针
    while (cur != nullptr) {
        cout << cur->data << " -> ";
        cur = cur->next;
    }
    cout << "nullptr" << endl;
}

// 在链表头部插入新节点（新同学插到第一个位置）
void insertAtHead(Node* &head, int val) {
    Node* newNode = new Node(val);  // 新建一个节点，数据为 val
    newNode->next = head;           // 新节点的 next 指向原来的头
    head = newNode;                 // 头指针更新为新节点
}

// 在链表尾部插入新节点（新同学站到队伍最后）
void insertAtTail(Node* &head, int val) {
    Node* newNode = new Node(val);  // 新建节点
    if (head == nullptr) {          // 如果链表是空的
        head = newNode;             // 新节点就是头节点
        return;
    }
    Node* cur = head;               // 从头开始找最后一个节点
    while (cur->next != nullptr) {  // 只要还有下一个节点就继续
        cur = cur->next;
    }
    cur->next = newNode;            // 最后一个节点的 next 指向新节点
}

// 删除链表中第一个值等于 val 的节点
void deleteValue(Node* &head, int val) {
    if (head == nullptr) return;    // 空链表，没东西可删
    
    if (head->data == val) {        // 要删除的是头节点
        Node* temp = head;          // 暂存旧头节点地址
        head = head->next;          // 头指针后移
        delete temp;                // 释放旧头节点内存
        return;
    }
    
    // 找要删除节点的前一个节点
    Node* cur = head;               // cur 从头开始
    while (cur->next != nullptr && cur->next->data != val) {
        cur = cur->next;            // 一直走到要删除节点的前一个
    }
    if (cur->next != nullptr) {     // 说明找到了那个节点
        Node* toDelete = cur->next; // toDelete 指向要删除的节点
        cur->next = cur->next->next;// 前一个节点跳过被删节点，连到后一个
        delete toDelete;            // 释放被删节点内存
    }
    // 如果没找到，什么也不做
}

// 释放整个链表（防止内存泄漏）
void deleteList(Node* head) {
    Node* cur = head;
    while (cur != nullptr) {
        Node* temp = cur;
        cur = cur->next;
        delete temp;
    }
}

int main() {
    Node* head = nullptr;  // 一开始是空链表，头指针指向空
    
    // 插入几个节点：10, 20, 30 依次加到尾部
    insertAtTail(head, 10);
    insertAtTail(head, 20);
    insertAtTail(head, 30);
    // 在头部插入 5
    insertAtHead(head, 5);
    
    cout << "链表：";
    printList(head);  // 输出：5 -> 10 -> 20 -> 30 -> nullptr
    
    // 删除值为 20 的节点
    deleteValue(head, 20);
    cout << "删除20后：";
    printList(head);  // 输出：5 -> 10 -> 30 -> nullptr
    
    // 程序结束前释放所有节点，养成良好的习惯
    deleteList(head);
    head = nullptr;
    return 0;
}

Python 完整代码

# 定义节点类
class Node:
    def __init__(self, data):
        self.data = data      # 数据域，比如存放零食数量：5包
        self.next = None      # 指针域，初始化为空

# 打印链表
def print_list(head):
    cur = head                # cur 指向当前节点
    while cur:                # 只要不是 None 就继续
        print(cur.data, end=" -> ")
        cur = cur.next        # 移动到下一个节点
    print("None")

# 头部插入（新同学站第一个）
def insert_at_head(head, val):
    new_node = Node(val)      # 创建一个新节点
    new_node.next = head      # 新节点指向原来的头
    return new_node           # 返回新头节点（注意：原 head 已变）

# 尾部插入（新同学站最后）
def insert_at_tail(head, val):
    new_node = Node(val)      # 创建新节点
    if head is None:          # 如果链表为空
        return new_node       # 新节点就是头节点
    cur = head
    while cur.next:           # 走到最后一个节点
        cur = cur.next
    cur.next = new_node       # 最后一个节点指向新节点
    return head               # 头节点没变，返回原头

# 删除第一个值为 val 的节点
def delete_value(head, val):
    if head is None:          # 空链表直接返回
        return None
    if head.data == val:      # 如果要删的是头节点
        return head.next      # 新头就是原头的下一个
    cur = head
    # 找到要删节点的前一个节点
    while cur.next and cur.next.data != val:
        cur = cur.next
    if cur.next:              # 找到了
        cur.next = cur.next.next  # 跳过要删的节点
    return head               # 头节点没变，返回原头

# 测试
head = None
head = insert_at_tail(head, 10)
head = insert_at_tail(head, 20)
head = insert_at_tail(head, 30)
head = insert_at_head(head, 5)

print("链表：", end="")
print_list(head)  # 5 -> 10 -> 20 -> 30 -> None

head = delete_value(head, 20)
print("删除20后：", end="")
print_list(head)  # 5 -> 10 -> 30 -> None

Python 中，每个变量都是对象的引用，“指针”实际上就是引用。不需要手动释放内存，Python 的垃圾回收会自动处理。但注意，函数返回新头节点时，外部一定要用返回值更新 head。

链表在生活中的应用

  • 音乐播放列表：上一曲、下一曲很自然用双向链表实现。
  • 浏览器前进/后退：浏览记录可以用链表（或双向链表）实现。
  • 操作系统的任务调度：使用循环链表实现时间片轮转。
  • 游戏中的组合技：例如格斗游戏中的“连招”序列，可以用链表存储一连串动作。
  • 在线排队系统：新人加入队伍末尾（尾部插入），排到的人离开（头部删除）。

总结要点

  • 链表由节点组成，节点包含数据和一个（或多个）指针。
  • 插入和删除节点只需要修改指针，时间复杂度 O(1)（已知位置的前提下）。
  • 随机访问必须从头遍历，时间复杂度 O(n)。
  • 链表克服了数组大小固定和插入删除效率低的缺点，但牺牲了快速访问的能力。
  • 每个节点多存储一个指针，内存开销比数组大。
  • 编程时要小心指针操作：避免丢失节点、形成死循环、内存泄漏。

链表是很多高级数据结构（如栈、队列、图）的基础。学会了链表，你就能自己动手实现更多有意思的结构啦！

接下来可以学习什么？

  • 动态数组（ArrayList / vector）：它结合了数组的快速访问和链表的灵活扩展。
  • 双向链表：可以向前向后走，操作更灵活。
  • 循环链表：特别适合做“轮播”或“循环队列”。
  • 栈和队列：可以用链表轻松实现。

加油，你的数据结构和算法之路会越走越宽！

例题精讲

1单选题

下列关于链表和数组的说法，正确的是？

A链表支持随机访问，访问任意元素的时间复杂度为O(1)
B数组在内存中连续存储，有利于插入和删除操作
C链表在插入和删除操作上通常比数组更灵活，时间复杂度更低
D数组的缓存局部性不如链表好
2判断题

在单链表中，若已知待删除节点的指针p，且p指向的不是尾节点，则可以在O(1)时间内删除该节点。

3填空题
以下函数实现在给定节点 after 之后插入一个新节点 new_node。请补全代码。

struct Node {
    int data;
    struct Node* next;
};

void insertAfter(struct Node* after, struct Node* new_node) {
    if (after == NULL || new_node == NULL) return;
    new_node->next = after->next;
    after->next = ___;
}
4单选题

判断一个单链表是否有环，最优的时间复杂度为？

AO(n)，使用哈希表记录已访问节点
BO(n)，使用快慢指针，快指针每次走两步，慢指针每次走一步
CO(n^2)，使用双重循环遍历
DO(n log n)，使用排序后比较
5填空题
以下函数实现反转单链表，返回新头指针。请补全代码。

struct Node* reverseList(struct Node* head) {
    struct Node* prev = NULL;
    struct Node* curr = head;
    struct Node* next = NULL;
    while (curr != NULL) {
        next = curr->next;
        curr->next = ___;
        prev = curr;
        curr = next;
    }
    return prev;
}