C++链表详解：从基础概念到高级应用

链表是计算机科学中最基础也是最重要的数据结构之一，它在内存管理、算法实现和实际应用中扮演着关键角色。本文将详细介绍链表的概念、类型、C++实现以及实际应用场景，帮助读者全面理解这一重要的数据结构。

1. 链表的基本概念

链表是一种线性数据结构，它由一系列节点组成，每个节点包含两个部分：数据部分和指针部分。与数组不同，链表中的元素在内存中不是连续存储的，而是通过指针连接在一起。这种结构允许在不移动其他元素的情况下进行高效的插入和删除操作。

如上图所示，链表由一系列节点组成，每个节点包含数据和指向下一个节点的指针。链表的第一个节点称为头节点（HEAD），最后一个节点的指针指向NULL，表示链表的结束。

链表的核心特点

1. 动态数据结构：链表可以根据需要动态增长和缩小，不需要预先分配固定大小的内存。

2. 非连续内存分配：链表中的节点可以存储在内存的任何位置，通过指针相互连接。

3. 插入和删除效率高：在已知位置插入或删除节点的时间复杂度为O(1)，而不需要像数组那样移动其他元素。

4. 随机访问效率低：访问链表中的第n个元素需要从头开始遍历，时间复杂度为O(n)。

5. 额外的内存开销：每个节点除了存储数据外，还需要存储指向其他节点的指针。

2. 链表的类型

链表根据节点之间的连接方式，可以分为四种主要类型：单向链表、双向链表、循环链表和双向循环链表。

2.1 单向链表

单向链表是最基本的链表形式，每个节点包含数据和一个指向下一个节点的指针。链表的最后一个节点的指针指向NULL，表示链表的结束。

特点：

• 只能从头到尾遍历
• 每个节点只有一个指针
• 只能访问当前节点的下一个节点
• 内存开销较小

C++节点定义：

struct Node {int data;       // 数据域，存储节点的值Node* next;     // 指针域，指向下一个节点
};

2.2 双向链表

双向链表中的每个节点包含数据和两个指针：一个指向前一个节点，一个指向后一个节点。链表的第一个节点的prev指针和最后一个节点的next指针都指向NULL。

特点：

• 可以双向遍历（从头到尾或从尾到头）
• 每个节点有两个指针
• 可以访问当前节点的前一个和后一个节点
• 内存开销较大
• 插入和删除操作更灵活

结构示意图：

NULL ← [prev|数据|next] ⇄ [prev|数据|next] ⇄ [prev|数据|next] → NULL↑head

C++节点定义：

struct Node {int data;       // 数据域，存储节点的值Node* prev;     // 前驱指针，指向前一个节点Node* next;     // 后继指针，指向后一个节点
};

2.3 循环链表

循环链表是单向链表的变体，其中最后一个节点的指针不是指向NULL，而是指向链表的第一个节点，形成一个环。

特点：

• 没有明确的结束点
• 可以从任何节点开始遍历整个链表
• 适用于需要循环处理的场景，如轮询调度

结构示意图：

    ┌───────────────────────────┐↓                           |
head → [数据|next] → [数据|next] → [数据|next]

C++节点定义：

struct Node {int data;       // 数据域，存储节点的值Node* next;     // 指针域，指向下一个节点
};

2.4 双向循环链表

双向循环链表结合了双向链表和循环链表的特点。第一个节点的prev指针指向最后一个节点，最后一个节点的next指针指向第一个节点。

特点：

• 可以双向循环遍历
• 每个节点都可以访问其前一个和后一个节点
• 没有明确的开始和结束点
• 内存开销最大
• 最灵活的链表结构

结构示意图：

    ┌─────────────────────────────────────┐|                                     |↓                                     ↑
[prev|数据|next] ⇄ [prev|数据|next] ⇄ [prev|数据|next]↑                                     |└─────────────────────────────────────┘

C++节点定义：

struct Node {int data;       // 数据域，存储节点的值Node* prev;     // 前驱指针，指向前一个节点Node* next;     // 后继指针，指向后一个节点
};

3. C++中的链表实现

在C++中，我们可以使用结构体或类来实现链表。下面将详细介绍各种链表的C++实现。

3.1 节点结构定义

链表的基本组成单位是节点，我们首先需要定义节点的结构：

// 单向链表节点结构
struct Node {int data;       // 数据域，存储节点的值Node* next;     // 指针域，指向下一个节点// 默认构造函数Node() : data(0), next(nullptr) {}// 带参数的构造函数Node(int val) : data(val), next(nullptr) {}
};// 双向链表节点结构
struct DNode {int data;       // 数据域，存储节点的值DNode* prev;    // 前驱指针，指向前一个节点DNode* next;    // 后继指针，指向后一个节点// 默认构造函数DNode() : data(0), prev(nullptr), next(nullptr) {}// 带参数的构造函数DNode(int val) : data(val), prev(nullptr), next(nullptr) {}
};

3.2 单向链表实现

下面是一个完整的单向链表类实现，包括常见的操作如插入、删除、遍历等：

// 单向链表类
class SinglyLinkedList {
private:Node* head;     // 头指针，指向链表的第一个节点public:// 构造函数SinglyLinkedList() : head(nullptr) {}// 析构函数，释放所有节点内存~SinglyLinkedList() {Node* current = head;while (current != nullptr) {Node* temp = current;current = current->next;delete temp;}head = nullptr;}// 在链表头部插入节点void insertAtHead(int value) {// 创建新节点Node* newNode = new Node(value);// 如果链表为空，新节点就是头节点if (head == nullptr) {head = newNode;return;}// 否则，将新节点插入到头部newNode->next = head;head = newNode;}// 在链表尾部插入节点void insertAtTail(int value) {// 创建新节点Node* newNode = new Node(value);// 如果链表为空，新节点就是头节点if (head == nullptr) {head = newNode;return;}// 找到链表的最后一个节点Node* current = head;while (current->next != nullptr) {current = current->next;}// 将新节点连接到最后一个节点current->next = newNode;}// 在指定位置插入节点void insertAtPosition(int position, int value) {// 如果位置为0，相当于在头部插入if (position == 0) {insertAtHead(value);return;}// 创建新节点Node* newNode = new Node(value);// 找到要插入位置的前一个节点Node* current = head;for (int i = 0; i < position - 1 && current != nullptr; i++) {current = current->next;}// 如果位置超出链表长度，或链表为空if (current == nullptr) {std::cout << "位置无效" << std::endl;delete newNode;return;}// 插入新节点newNode->next = current->next;current->next = newNode;}// 删除头部节点void deleteFromHead() {// 如果链表为空，无法删除if (head == nullptr) {std::cout << "链表为空，无法删除" << std::endl;return;}// 保存头节点Node* temp = head;// 更新头指针head = head->next;// 释放原头节点的内存delete temp;}// 删除尾部节点void deleteFromTail() {// 如果链表为空，无法删除if (head == nullptr) {std::cout << "链表为空，无法删除" << std::endl;return;}// 如果链表只有一个节点if (head->next == nullptr) {delete head;head = nullptr;return;}// 找到倒数第二个节点Node* current = head;while (current->next->next != nullptr) {current = current->next;}// 删除最后一个节点delete current->next;current->next = nullptr;}// 删除指定位置的节点void deleteFromPosition(int position) {// 如果链表为空，无法删除if (head == nullptr) {std::cout << "链表为空，无法删除" << std::endl;return;}// 如果要删除头节点if (position == 0) {deleteFromHead();return;}// 找到要删除位置的前一个节点Node* current = head;for (int i = 0; i < position - 1 && current != nullptr && current->next != nullptr; i++) {current = current->next;}// 如果位置无效if (current == nullptr || current->next == nullptr) {std::cout << "位置无效" << std::endl;return;}// 保存要删除的节点Node* temp = current->next;// 更新链接current->next = temp->next;// 释放节点内存delete temp;}// 打印链表void display() {Node* current = head;if (current == nullptr) {std::cout << "链表为空" << std::endl;return;}std::cout << "链表内容: ";while (current != nullptr) {std::cout << current->data << " -> ";current = current->next