C++ 单向链表（包含头哨兵节点）教程

什么是单向链表？

单向链表是一种常见的数据结构，由一系列节点组成。每个节点包含两个部分：

• 数据域：存储实际的数据。
• 指针域：指向下一个节点。

我们使用一个特殊的“头哨兵节点”（也叫哑节点、虚拟头节点），它不存储实际内容，仅用于简化对链表头部的操作。

---

为什么使用头哨兵节点？

• 简化插入和删除操作的逻辑。
• 避免对空链表或头节点进行特殊判断。
• 提高代码可读性和健壮性。

---

示例代码（带详细注释）

#include <iostream>
using namespace std;

// 定义链表节点结构体
struct Node {
    int data;       // 数据域
    Node* next;     // 指针域，指向下一个节点

    // 构造函数
    Node(int val) : data(val), next(nullptr) {}
};

class LinkedList {
private:
    Node* head;     // 头哨兵节点指针

public:
    // 构造函数：初始化头哨兵节点
    LinkedList() {
        head = new Node(-1);  // 哨兵节点不存储有效数据，用 -1 表示无效值
    }

    // 析构函数：释放所有节点内存
    ~LinkedList() {
        Node* curr = head;
        while (curr != nullptr) {
            Node* temp = curr;
            curr = curr->next;
            delete temp;
        }
    }

    // 在链表末尾插入一个新节点
    void append(int val) {
        Node* newNode = new Node(val);  // 创建新节点
        Node* curr = head;              // 从哨兵节点开始遍历

        // 找到最后一个节点
        while (curr->next != nullptr) {
            curr = curr->next;
        }

        // 插入新节点
        curr->next = newNode;
    }

    // 在指定位置前插入一个新节点（索引从0开始）
    void insert(int index, int val) {
        Node* newNode = new Node(val);  // 创建新节点
        Node* curr = head;              // 从哨兵节点开始

        // 找到要插入位置的前一个节点
        for (int i = 0; i < index && curr->next != nullptr; ++i) {
            curr = curr->next;
        }

        // 插入新节点
        newNode->next = curr->next;
        curr->next = newNode;
    }

    // 删除指定值的第一个节点
    void remove(int val) {
        Node* prev = head;      // 前一个节点（从哨兵开始）
        Node* curr = head->next; // 当前节点是第一个有效节点

        // 遍历链表查找目标值
        while (curr != nullptr) {
            if (curr->data == val) {
                prev->next = curr->next;  // 删除当前节点
                delete curr;              // 释放内存
                return;
            }
            prev = curr;
            curr = curr->next;
        }

        cout << "未找到值为 " << val << " 的节点" << endl;
    }

    // 查找某个值是否存在
    bool search(int val) {
        Node* curr = head->next; // 跳过哨兵节点
        while (curr != nullptr) {
            if (curr->data == val)
                return true;
            curr = curr->next;
        }
        return false;
    }

    // 打印整个链表
    void printList() {
        Node* curr = head->next; // 跳过哨兵节点
        while (curr != nullptr) {
            cout << curr->data << " -> ";
            curr = curr->next;
        }
        cout << "nullptr" << endl;
    }
};

// 主函数测试链表功能
int main() {
    LinkedList list;

    list.append(10);
    list.append(20);
    list.append(30);

    cout << "初始链表：" << endl;
    list.printList();

    list.insert(1, 15); // 在索引1处插入15
    cout << "插入15后：" << endl;
    list.printList();

    list.remove(20); // 删除值为20的节点
    cout << "删除20后：" << endl;
    list.printList();

    int target = 15;
    if (list.search(target))
        cout << "找到了值为 " << target << " 的节点" << endl;
    else
        cout << "未找到值为 " << target << " 的节点" << endl;

    return 0;
}

---

输出示例：

初始链表：
10 -> 20 -> 30 -> nullptr
插入15后：
10 -> 15 -> 20 -> 30 -> nullptr
删除20后：
10 -> 15 -> 30 -> nullptr
找到了值为 15 的节点

---

小结

操作	时间复杂度
插入/删除（已知位置）	O(1)
插入/删除（按值查找）	O(n)
查找

---

关键点总结

• 头哨兵节点可以避免对头节点做特殊处理。
• 使用 new 动态创建节点时记得在析构函数中用 delete 释放内存。
• 插入和删除操作时要注意指针顺序，防止内存泄漏或指针断裂。

---

如果你还有关于双向链表、循环链表或其他数据结构的问题，也可以继续问我！

有头哨兵（哑节点）的单链表和没有头哨兵的单链表在结构设计和操作实现上有一些关键区别，这些区别影响了代码的复杂度、边界条件处理以及使用便利性。下面我将从多个方面详细对比它们的差异。

1. 结构定义的区别

无头哨兵的单链表：

• 头指针直接指向第一个存储数据的节点
• 当链表为空时，头指针为空（nullptr）

template<typename T>
class LinkedList {
private:
    Node<T>* head;  // 头指针直接指向第一个节点
    
public:
    LinkedList() : head(nullptr) {}  // 初始化头指针为空
    // ... 其他成员函数
};

有头哨兵的单链表：

• 头指针指向一个特殊的头哨兵节点（不存储实际数据）
• 头哨兵节点的next指针指向第一个存储数据的节点
• 当链表为空时，头哨兵节点的next指针为空（nullptr）

template<typename T>
class LinkedList {
private:
    Node<T>* head;  // 头指针指向头哨兵节点
    
public:
    LinkedList() {
        head = new Node<T>();  // 创建头哨兵节点
    }
    // ... 其他成员函数
};

2. 插入操作的区别

无头哨兵的单链表：

• 在头部插入节点时需要特殊处理空链表的情况
• 需要更新头指针的值

void push_front(const T& value) {
    Node<T>* newNode = new Node<T>(value, head);
    head = newNode;  // 更新头指针
}

有头哨兵的单链表：

• 头部插入操作统一，无需处理空链表的特殊情况
• 头指针始终指向头哨兵节点，不发生变化

void push_front(const T& value) {
    Node<T>* newNode = new Node<T>(value, head->next);
    head->next = newNode;  // 更新头哨兵节点的next指针
}

3. 删除操作的区别

无头哨兵的单链表：

• 删除头部节点时需要特殊处理空链表的情况
• 删除头部节点后可能需要更新头指针的值

void pop_front() {
    if (head == nullptr) return;  // 处理空链表
    
    Node<T>* temp = head;
    head = head->next;  // 更新头指针
    delete temp;
}

有头哨兵的单链表：

• 删除头部节点操作统一，无需处理空链表的特殊情况
• 头指针始终指向头哨兵节点，不发生变化

void pop_front() {
    if (empty()) return;  // 链表为空时不执行任何操作
    
    Node<T>* temp = head->next;
    head->next = temp->next;  // 更新头哨兵节点的next指针
    delete temp;
}

4. 边界条件处理的区别

无头哨兵的单链表：

• 在插入、删除操作中，需要频繁检查链表是否为空
• 处理第一个节点和其他节点的逻辑不一致，需要特殊处理

有头哨兵的单链表：

• 头哨兵节点的存在统一了边界条件，无需特殊处理空链表
• 插入和删除操作对第一个节点和其他节点的处理逻辑一致

5. 代码复杂度的区别

无头哨兵的单链表：

• 代码中需要多处判断链表是否为空
• 头部操作和其他位置操作的代码不一致，增加了复杂度

有头哨兵的单链表：

• 代码更简洁、统一，减少了条件判断
• 头部操作和其他位置操作的代码逻辑一致，降低了复杂度

6. 优缺点总结

无头哨兵的单链表：

• 优点：节省一个节点的内存空间（头哨兵节点）
• 缺点：代码复杂度高，边界条件处理繁琐，容易出错

有头哨兵的单链表：

• 优点：代码简洁，边界条件处理统一，减少出错机会
• 缺点：占用额外的一个节点空间（头哨兵节点）

7. 使用场景建议

• 如果链表操作频繁，尤其是头部插入和删除操作，建议使用有头哨兵的单链表，可以显著简化代码
• 如果内存空间非常紧张，且链表操作简单，可以考虑使用无头哨兵的单链表
• 在实现链表相关算法时，有头哨兵的单链表通常更容易处理，减少了边界条件的干扰

总结

头哨兵节点通过引入一个不存储数据的特殊节点，统一了链表的边界条件，简化了插入和删除操作的实现，降低了代码复杂度。虽然占用了额外的一点内存空间，但在大多数情况下，使用有头哨兵的单链表是更优的选择，尤其是在需要频繁操作链表头部的场景中。

在单向链表中删除节点同样有多种情况，包括删除头部节点、尾部节点，以及删除指定位置或指定值的节点。下面我将详细介绍这几种删除操作的实现方法和原理。

删除链表头部节点

删除链表头部节点（即头哨兵节点的下一个节点）是最简单的情况，只需修改头哨兵节点的指针并释放被删节点的内存。

步骤如下：

1. 检查链表是否为空（头哨兵节点的next是否为nullptr）
2. 保存要删除的节点指针
3. 更新头哨兵节点的next指针指向被删节点的下一个节点
4. 释放被删节点的内存

代码示例：

void pop_front() {
    if (empty()) return;  // 链表为空时不执行任何操作
    
    Node<T>* temp = head->next;  // 保存要删除的节点
    head->next = temp->next;     // 更新头哨兵节点的next指向
    delete temp;                 // 释放被删节点的内存
}

删除链表尾部节点

删除链表尾部节点需要先找到倒数第二个节点，然后修改其next指针并释放最后一个节点的内存。

步骤如下：

1. 检查链表是否为空
2. 从头哨兵节点开始，遍历链表找到倒数第二个节点（即next指针指向最后一个节点的节点）
3. 保存最后一个节点的指针
4. 将倒数第二个节点的next指针置为nullptr
5. 释放最后一个节点的内存

代码示例：

void pop_back() {
    if (empty()) return;  // 链表为空时不执行任何操作
    
    Node<T>* current = head;
    
    // 找到倒数第二个节点
    while (current->next->next != nullptr) {
        current = current->next;
    }
    
    Node<T>* temp = current->next;  // 保存最后一个节点
    current->next = nullptr;        // 更新倒数第二个节点的next为nullptr
    delete temp;                    // 释放最后一个节点的内存
}

删除指定位置的节点

删除指定位置的节点需要先找到该位置的前一个节点，然后修改指针关系并释放被删节点的内存。

步骤如下：

1. 检查链表是否为空以及位置是否合法
2. 从头哨兵节点开始，遍历链表找到位置i-1的节点（即要删除节点的前一个节点）
3. 保存要删除的节点指针（位置i的节点）
4. 更新位置i-1节点的next指针指向位置i+1的节点
5. 释放被删节点的内存

代码示例：

// 删除位置index的节点（index从0开始）
bool erase(size_t index) {
    if (index >= size()) return false;  // 检查位置是否合法
    
    Node<T>* current = head;
    // 找到位置index的前一个节点
    for (size_t i = 0; i < index; ++i) {
        current = current->next;
    }
    
    Node<T>* temp = current->next;  // 保存要删除的节点
    current->next = temp->next;     // 更新前一个节点的next指向
    delete temp;                    // 释放被删节点的内存
    
    return true;
}

删除指定值的节点

删除指定值的节点需要遍历链表，找到所有值等于给定值的节点并删除它们。

步骤如下：

1. 从头哨兵节点开始，遍历链表
2. 对于每个节点，检查其下一个节点的值是否等于给定值
3. 如果相等，保存下一个节点的指针，修改当前节点的next指针跳过该节点，然后释放被删节点的内存
4. 如果不相等，移动到下一个节点继续检查

代码示例：

// 删除链表中所有值等于value的节点
void remove(const T& value) {
    Node<T>* current = head;
    
    // 遍历链表，查找所有值等于value的节点
    while (current->next != nullptr) {
        if (current->next->data == value) {
            Node<T>* temp = current->next;
            current->next = temp->next;  // 跳过要删除的节点
            delete temp;                 // 释放被删节点的内存
            // 注意：这里不移动current指针，继续检查下一个节点
        } else {
            current = current->next;     // 移动到下一个节点
        }
    }
}

删除操作的时间复杂度

• 头部删除：时间复杂度为O(1)，因为只需要修改头哨兵节点的指针
• 尾部删除：时间复杂度为O(n)，因为需要遍历整个链表找到倒数第二个节点
• 指定位置删除：平均时间复杂度为O(n)，最坏情况下需要遍历到链表尾部
• 指定值删除：时间复杂度为O(n)，因为需要遍历整个链表

删除操作的关键点

1. 头哨兵节点的作用：头哨兵节点确保链表始终有一个有效的头节点，使得头部删除操作与其他位置删除操作一致，无需特殊处理空链表的情况。

2. 指针操作顺序：在删除节点时，必须先保存被删节点的指针，然后修改前一个节点的next指针，最后释放被删节点的内存。

3. 边界条件处理：删除操作前需要检查链表是否为空以及位置是否合法，避免越界访问。

如果你想扩展之前的链表类，可以将上述删除方法添加到类中。这些方法展示了链表删除操作的基本原理，实际应用中可能需要根据具体需求进行调整。

在单向链表中插入新节点有多种情况，包括在链表头部插入、尾部插入，以及在指定位置插入。下面我将详细介绍这几种插入操作的实现方法和原理。

在链表头部插入节点

在链表头部插入新节点是最简单的情况，只需要修改头哨兵节点的指针。

步骤如下：

1. 创建新节点，设置其数据和指向下一个节点的指针
2. 将新节点的next指针指向当前的第一个节点
3. 更新头哨兵节点的next指针指向新节点

代码示例：

void push_front(const T& value) {
    Node<T>* newNode = new Node<T>(value, head->next);
    head->next = newNode;  // 更新头哨兵节点的next指向新节点
}

在链表尾部插入节点

在链表尾部插入新节点需要先遍历到链表的最后一个节点，然后修改其next指针。

步骤如下：

1. 从头哨兵节点开始，遍历链表直到找到最后一个节点（即next指针为nullptr的节点）
2. 创建新节点，设置其数据和next指针（初始为nullptr）
3. 将最后一个节点的next指针指向新节点

代码示例：

void push_back(const T& value) {
    Node<T>* current = head;
    
    // 找到链表的最后一个节点
    while (current->next != nullptr) {
        current = current->next;
    }
    
    // 在尾部插入新节点
    current->next = new Node<T>(value);
}

在指定位置插入节点

在指定位置插入新节点需要先找到插入位置的前一个节点，然后修改指针关系。

步骤如下：

1. 从头哨兵节点开始，遍历链表直到找到插入位置的前一个节点（位置i-1）
2. 创建新节点，设置其数据和next指针指向位置i的节点
3. 更新位置i-1节点的next指针指向新节点

代码示例：

// 在位置index插入新节点（index从0开始）
bool insert(size_t index, const T& value) {
    if (index > size()) return false;  // 检查位置是否合法
    
    Node<T>* current = head;
    // 找到位置index的前一个节点
    for (size_t i = 0; i < index; ++i) {
        current = current->next;
    }
    
    // 插入新节点
    Node<T>* newNode = new Node<T>(value, current->next);
    current->next = newNode;
    
    return true;
}

插入操作的时间复杂度

• 头部插入：时间复杂度为O(1)，因为只需要修改头哨兵节点的指针
• 尾部插入：时间复杂度为O(n)，因为需要遍历整个链表找到尾部节点
• 指定位置插入：平均时间复杂度为O(n)，最坏情况下需要遍历到链表尾部

插入操作的关键点

1. 头哨兵节点的作用：头哨兵节点确保链表始终有一个有效的头节点，使得头部插入操作与其他位置插入操作一致，无需特殊处理空链表的情况。

2. 指针操作顺序：在插入新节点时，必须先设置新节点的next指针，再修改前一个节点的next指针，否则会导致链表断裂。

3. 边界条件处理：插入位置的合法性检查非常重要，避免越界访问。

如果你想扩展之前的链表类，可以将上述插入方法添加到类中。这些方法展示了链表插入操作的基本原理，实际应用中可能需要根据具体需求进行调整。