CC++ & Algorithm

C++单链表与双链表 —— 像火车车厢一样一节连一节

较难31
语言版本：C++Python
概述：链表是一连串节点，每个节点存着数据和指向下一个节点的指针，可以灵活地插入和删除。

C++单链表与双链表 —— 像火车车厢一样一节连一节

什么是链表？

链表是一种存储数据的方式，它不像数组那样把所有数据挨个排在一起，而是把数据分散存放，然后用“指针”串联起来。你可以把链表想象成一列火车：

  • 每节车厢就是一个节点（Node），里面装着货物（数据）。
  • 挂钩就是指针（Pointer），用来连接下一节车厢（下一个节点）。
  • 整列火车由第一节车厢（头节点 head）开始，一直连到最后。

为什么需要链表？因为数组虽然可以随机访问（直接通过下标找第几个元素），但要在中间插入或删除一个元素时，需要移动大量元素，很麻烦。链表则不同：插入或删除只需改动几个挂钩，其他车厢不动，特别灵活。

链表分为两种：

  • 单链表：每节车厢只有向后的挂钩，你只能从车头走到车尾，不能回头。
  • 双链表：每节车厢前后都有挂钩，可以往前也可以往后走。

C++ 标准库中提供了 list（双链表）和 forward_list（单链表），但为了真正理解链表的工作原理，我们最好自己用结构体和指针来模拟。下面我们就从单链表开始学起。

一、单链表详解

1. 节点结构

每个节点包含两个部分：数据（比如一个整数）和指向下一个节点的指针。最后一个节点的指针指向空（NULL 或 nullptr），表示链表结束。

struct Node {
    int data;      // 数据，这里用整数举例
    Node* next;    // 指向下一个节点的指针
};

生活比喻：就像寻宝游戏——你手里拿着一张纸条，上面写着“宝藏藏在衣柜里”，这张纸条就是节点，纸条上的字（“藏在衣柜里”）是数据，而指向下一个地点的线索就是指针。你跟着线索找到衣柜，衣柜里又有一张纸条……直到最后一张说“宝藏就在这里”。

2. 创建节点并连接

要创建一个链表，首先要创建许多节点，然后用指针把它们串起来。下面我们手动创建三个节点，存数字 10、20、30，连成 10 -> 20 -> 30 -> NULL。

#include <iostream>
using namespace std;

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

int main() {
    // 创建三个节点，用 new 在堆上分配内存
    Node* head = new Node();   // 第一个节点（头节点）
    head->data = 10;

    Node* second = new Node(); // 第二个节点
    second->data = 20;

    Node* third = new Node();  // 第三个节点
    third->data = 30;

    // 把节点连起来：第一个节点的next指向第二个，第二个的next指向第三个
    head->next = second;
    second->next = third;
    third->next = NULL;        // 最后一个节点指向空

    // 遍历输出链表
    Node* current = head;      // 从头部开始
    while (current != NULL) {
        cout << current->data << " -> ";
        current = current->next;  // 移动到下一个节点
    }
    cout << "NULL" << endl;

    // 释放内存（实际程序中不要忘记）
    delete head;
    delete second;
    delete third;

    return 0;
}

运行结果：

10 -> 20 -> 30 -> NULL

3. 插入节点（中间插入）

要在链表中插入一个新节点，比如在 10 和 20 之间插入 15，只需要三步：

  1. 新节点的 next 指向 20。
  2. 10 的 next 指向新节点。
  3. 其他节点不用动。

下面是一个插入函数：

// 在指定节点之后插入一个新节点
void insertAfter(Node* prevNode, int newData) {
    if (prevNode == NULL) {
        cout << "前一个节点不能为空！" << endl;
        return;
    }
    Node* newNode = new Node();   // 创建新节点
    newNode->data = newData;      // 存入数据
    newNode->next = prevNode->next; // 新节点指向原来的下一个
    prevNode->next = newNode;     // 前一个节点指向新节点
}

生活例子：火车要加一节新车厢，只需在原有挂钩处拆开，挂上新车厢，再把新车厢的后挂钩连到原来的下一节车厢。不需要移动其他车厢。

4. 删除节点

删除一个节点也很简单：让前一个节点的 next 跳过当前节点，直接指向当前节点的下一个节点，然后释放当前节点的内存。

// 删除给定节点的下一个节点（注意：不能删除头节点本身）
void deleteAfter(Node* prevNode) {
    if (prevNode == NULL || prevNode->next == NULL) return;
    Node* toDelete = prevNode->next;       // 要删除的节点
    prevNode->next = toDelete->next;       // 跳过它
    delete toDelete;                       // 释放内存
}

注意：删除后要释放内存，否则会造成内存泄漏（就像垃圾堆里越堆越多的空车厢）。

二、双链表简介

双链表比单链表多了一个向前指针 prev，每个节点都知道前一个是谁。这样，你可以从后往前遍历，插入和删除也变得更方便，因为不需要再专门找前一个节点。

节点结构

struct DNode {
    int data;          // 数据
    DNode* prev;       // 指向前一个节点
    DNode* next;       // 指向后一个节点
};

双链表的创建和遍历

下面创建一个双链表 10 <-> 20 <-> 30，并双向遍历：

#include <iostream>
using namespace std;

struct DNode {
    int data;
    DNode* prev;
    DNode* next;
};

int main() {
    // 创建三个节点
    DNode* head = new DNode();
    head->data = 10;
    head->prev = NULL;  // 头节点的前驱为空

    DNode* second = new DNode();
    second->data = 20;

    DNode* third = new DNode();
    third->data = 30;
    third->next = NULL; // 尾节点的后继为空

    // 连接前后关系
    head->next = second;
    second->prev = head;
    second->next = third;
    third->prev = second;

    // 正向遍历：从头到尾
    cout << "正向：";
    DNode* cur = head;
    while (cur != NULL) {
        cout << cur->data << " <-> ";
        cur = cur->next;
    }
    cout << "NULL" << endl;

    // 反向遍历：从尾到头
    cout << "反向：";
    cur = third; // 从尾部开始
    while (cur != NULL) {
        cout << cur->data << " <-> ";
        cur = cur->prev;
    }
    cout << "NULL" << endl;

    // 释放内存（略，实际应逐个 delete）
    delete head;
    delete second;
    delete third;

    return 0;
}

运行结果：

正向：10 <-> 20 <-> 30 <-> NULL
反向：30 <-> 20 <-> 10 <-> NULL

双链表的优势：如果你想删除某个节点，直接用它自己的 prev 和 next 就能找到前后节点，不需要像单链表那样先找到前一个节点。

三、常见错误（新手别踩坑）

  1. 忘记初始化指针
    Node* ptr; 直接使用，没有指向任何地方，会导致程序崩溃。一定要先让指针指向有效节点或 NULL。

  2. 忘记把最后一个节点的 next 设为 NULL
    否则遍历时不知道何时停止，会一直访问到非法内存。

  3. 插入或删除时指针顺序搞错
    例如：先改了前一个节点的next，再改新节点的next，就会丢失后面节点的连接。正确做法：先连新节点和后面，再连前面和新节点（参考插入函数）。

  4. 忘记释放内存
    用 new 创建的节点必须用 delete 释放，否则程序会内存泄漏（占用的内存越来越多）。不过对于小练习，不释放也不影响运行，但好习惯要养成。

  5. 访问空指针的数据
    比如 current->data 但 current == NULL，会崩溃。所以遍历时一定要先判断 current != NULL。

四、完整可运行示例（单链表：插入、删除、遍历）

下面是一个完整的单链表程序，包含以下功能：

  • 在头部插入节点
  • 在尾部插入节点
  • 在指定位置插入节点
  • 删除指定值的节点
  • 打印链表

代码中每行变量都加了中文注释，方便你理解。

#include <iostream>
using namespace std;

// 定义节点结构
struct Node {
    int data;      // 数据，这里用整数
    Node* next;    // 指向下一个节点的指针
};

// 打印链表
void printList(Node* head) {
    Node* cur = head;  // 当前节点，从头部开始
    while (cur != NULL) {
        cout << cur->data << " -> ";
        cur = cur->next;  // 移动到下一个
    }
    cout << "NULL" << endl;
}

// 在头部插入新节点
void insertAtHead(Node*& head, int newData) {
    Node* newNode = new Node();  // 创建新节点
    newNode->data = newData;     // 存入数据
    newNode->next = head;        // 新节点指向原头节点
    head = newNode;              // 让新节点成为头节点
}

// 在尾部插入新节点
void insertAtTail(Node*& head, int newData) {
    Node* newNode = new Node();
    newNode->data = newData;
    newNode->next = NULL;        // 新节点将成为尾节点，next 为空

    if (head == NULL) {          // 如果链表为空
        head = newNode;
        return;
    }

    Node* cur = head;            // 找到最后一个节点
    while (cur->next != NULL) {
        cur = cur->next;
    }
    cur->next = newNode;         // 最后一个节点的 next 指向新节点
}

// 删除第一个等于某个值的节点
void deleteValue(Node*& head, int target) {
    if (head == NULL) return;    // 空链表什么都不做

    // 如果要删除的是头节点
    if (head->data == target) {
        Node* toDelete = head;   // 保存要删除的节点
        head = head->next;       // 头节点后移
        delete toDelete;         // 释放内存
        return;
    }

    // 查找要删除节点的前一个节点
    Node* prev = head;
    while (prev->next != NULL && prev->next->data != target) {
        prev = prev->next;
    }

    if (prev->next == NULL) {
        cout << "没有找到值为 " << target << " 的节点。" << endl;
        return;
    }

    Node* toDelete = prev->next;       // 要删除的节点
    prev->next = toDelete->next;       // 跳过它
    delete toDelete;
}

int main() {
    Node* head = NULL;   // 初始链表为空

    // 插入几个节点
    insertAtTail(head, 10);   // 尾部插入: 10
    insertAtTail(head, 20);   // 尾部插入: 10 -> 20
    insertAtHead(head, 5);    // 头部插入: 5 -> 10 -> 20
    insertAtTail(head, 30);   // 尾部插入: 5 -> 10 -> 20 -> 30

    cout << "当前链表：";
    printList(head);

    // 删除值为20的节点
    deleteValue(head, 20);
    cout << "删除20之后：";
    printList(head);

    // 删除不存在的值
    deleteValue(head, 99);
    // 输出提示“没有找到”

    // 释放所有节点内存（略，实际完整的程序需要逐个删除）
    // 这里为了简单，不逐一释放
    return 0;
}

运行结果：

当前链表：5 -> 10 -> 20 -> 30 -> NULL
删除20之后：5 -> 10 -> 30 -> NULL
没有找到值为 99 的节点。

五、相关指引

学完单链表和双链表，你还可以继续探索：

  • 循环链表：把最后一个节点的 next 指向头节点，形成一个圈。就像游乐园的环形小火车，可以一直转下去。
  • 使用 STL 容器：C++ 标准库中的 forward_list（单链表）和 list（双链表）可以直接使用，免去手写节点管理的麻烦。但理解底层原理能帮助你更灵活地使用它们。
  • 与数组对比：数组适合频繁读取（按下标），链表适合频繁插入删除。根据场景选择合适的工具。

链表是数据结构的基础，掌握了它，后面学习栈、队列、树都会轻松很多。加油，你一定可以像拼乐高一样自如地组装这些“数据车厢”！

例题精讲

1单选题

以下哪个是C++单链表节点的正确结构体定义？

Astruct Node { int data; Node next; };
Bstruct Node { int data; Node* next; };
Cstruct Node { int data; Node* prev; };
Dstruct Node { int data; Node* prev; Node* next; };
2单选题

在双链表中，已知节点p（非头非尾），要在p之后插入一个新节点q（已分配），需要修改多少个指针？

A2个
B3个
C4个
D5个
3判断题

在单链表中，删除头节点时，必须将头指针指向原头节点的下一个节点。

4填空题
以下代码实现单链表的遍历输出，请补全循环条件。

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

void printList(Node* head) {
    Node* cur = head;
    while ( ___) {
        cout << cur->data << " ";
        cur = cur->next;
    }
}
5填空题
以下代码在双链表中删除节点p（假设p不是头节点也不是尾节点），请补全两个缺失的语句。

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

void deleteNode(Node* p) {
    p->prev->next = p->next;
    ___(1)___;
    ___(2)___;
}