单链表是一种常见的线性数据结构，由节点（Node）组成，每个节点包含数据域和指针域（指向下一个节点）。以下是单链表的核心操作实现，包括节点定义、链表类封装、增删查改、遍历、销毁等功能。

1. 完整代码实现

cpp

运行

#include <iostream>
#include <stdexcept>  // 用于异常处理
using namespace std;

// 定义链表节点结构体
template <typename T>
struct ListNode {
    T data;               // 数据域
    ListNode<T>* next;    // 指针域，指向下一个节点

    // 节点构造函数
    ListNode(T val) : data(val), next(nullptr) {}
};

// 单链表类封装
template <typename T>
class SinglyLinkedList {
private:
    ListNode<T>* head;    // 头节点指针（哨兵节点，不存储数据）
    int size;             // 链表元素个数

public:
    // 构造函数：初始化空链表
    SinglyLinkedList() {
        head = new ListNode<T>(T());  // 头节点（哨兵），数据域默认值
        size = 0;
    }

    // 析构函数：销毁链表
    ~SinglyLinkedList() {
        clear();          // 清空所有节点
        delete head;      // 释放头节点
        head = nullptr;
    }

    // 1. 清空链表
    void clear() {
        ListNode<T>* curr = head->next;  // 从第一个有效节点开始
        while (curr != nullptr) {
            ListNode<T>* temp = curr;
            curr = curr->next;
            delete temp;  // 释放当前节点
        }
        head->next = nullptr;
        size = 0;
    }

    // 2. 在链表尾部添加元素
    void push_back(T val) {
        ListNode<T>* newNode = new ListNode<T>(val);
        ListNode<T>* curr = head;
        // 找到最后一个节点
        while (curr->next != nullptr) {
            curr = curr->next;
        }
        curr->next = newNode;
        size++;
    }

    // 3. 在链表头部添加元素
    void push_front(T val) {
        ListNode<T>* newNode = new ListNode<T>(val);
        newNode->next = head->next;  // 新节点指向原第一个节点
        head->next = newNode;        // 头节点指向新节点
        size++;
    }

    // 4. 删除指定值的第一个节点
    bool remove(T val) {
        ListNode<T>* prev = head;
        ListNode<T>* curr = head->next;
        while (curr != nullptr) {
            if (curr->data == val) {
                prev->next = curr->next;  // 跳过待删除节点
                delete curr;              // 释放内存
                size--;
                return true;
            }
            prev = curr;
            curr = curr->next;
        }
        return false;  // 未找到该值
    }

    // 5. 根据索引删除节点（索引从0开始）
    bool removeAt(int index) {
        if (index < 0 || index >= size) {
            throw out_of_range("Index out of bounds");
        }
        ListNode<T>* prev = head;
        ListNode<T>* curr = head->next;
        for (int i = 0; i < index; i++) {
            prev = curr;
            curr = curr->next;
        }
        prev->next = curr->next;
        delete curr;
        size--;
        return true;
    }

    // 6. 查找元素是否存在
    bool find(T val) const {
        ListNode<T>* curr = head->next;
        while (curr != nullptr) {
            if (curr->data == val) {
                return true;
            }
            curr = curr->next;
        }
        return false;
    }

    // 7. 获取指定索引的元素（索引从0开始）
    T get(int index) const {
        if (index < 0 || index >= size) {
            throw out_of_range("Index out of bounds");
        }
        ListNode<T>* curr = head->next;
        for (int i = 0; i < index; i++) {
            curr = curr->next;
        }
        return curr->data;
    }

    // 8. 修改指定索引的元素
    bool set(int index, T val) {
        if (index < 0 || index >= size) {
            return false;
        }
        ListNode<T>* curr = head->next;
        for (int i = 0; i < index; i++) {
            curr = curr->next;
        }
        curr->data = val;
        return true;
    }

    // 9. 获取链表长度
    int getSize() const {
        return size;
    }

    // 10. 判断链表是否为空
    bool isEmpty() const {
        return size == 0;
    }

    // 11. 遍历打印链表
    void print() const {
        ListNode<T>* curr = head->next;
        if (curr == nullptr) {
            cout << "Linked list is empty" << endl;
            return;
        }
        cout << "Linked list: ";
        while (curr != nullptr) {
            cout << curr->data << " -> ";
            curr = curr->next;
        }
        cout << "nullptr" << endl;
    }
};

// 测试代码
int main() {
    // 创建int类型的链表
    SinglyLinkedList<int> list;

    // 测试添加元素
    list.push_back(10);
    list.push_back(20);
    list.push_front(5);
    list.print();  // 输出：5 -> 10 -> 20 -> nullptr

    // 测试查找
    cout << "Find 10: " << boolalpha << list.find(10) << endl;  // true
    cout << "Find 30: " << boolalpha << list.find(30) << endl;  // false

    // 测试获取元素
    cout << "Index 1: " << list.get(1) << endl;  // 10

    // 测试修改元素
    list.set(1, 15);
    list.print();  // 5 -> 15 -> 20 -> nullptr

    // 测试删除元素
    list.remove(15);
    list.print();  // 5 -> 20 -> nullptr

    list.removeAt(1);
    list.print();  // 5 -> nullptr

    // 测试清空
    list.clear();
    list.print();  // Linked list is empty

    // 测试边界情况
    try {
        list.get(0);  // 抛出异常
    } catch (const out_of_range& e) {
        cout << "Exception: " << e.what() << endl;
    }

    return 0;
}

2. 核心概念解析

（1）节点结构（ListNode）

• data：存储节点的实际数据，使用模板支持任意类型（int、string、自定义类型等）。
• next：指向链表中下一个节点的指针，尾节点的next为nullptr。

（2）头节点（哨兵节点）

• 代码中使用哨兵头节点（不存储有效数据），目的是统一空链表和非空链表的操作逻辑，避免处理head为nullptr的边界情况。
• 例如：空链表时head->next = nullptr，而非空时head->next指向第一个有效节点。

（3）核心操作说明

操作	功能描述	时间复杂度
push_back	尾部添加元素	O(n)
push_front	头部添加元素	O(1)
remove	删除指定值的第一个节点	O(n)
find	查找元素是否存在	O(n)
get/set	获取 / 修改指定索引元素	O(n)
clear	清空链表	O(n)

3. 关键注意事项

1. 内存管理：

   • 所有new创建的节点必须在析构 / 删除时用delete释放，避免内存泄漏。
   • 析构函数先调用clear()释放所有有效节点，再释放头节点。

2. 边界处理：

   • 操作索引时需检查是否越界（index < 0 || index >= size）。
   • 空链表的遍历 / 删除操作需特殊处理，避免访问nullptr。

3. 模板支持：

   • 代码使用模板template <typename T>，支持任意数据类型（如SinglyLinkedList<string>、SinglyLinkedList<double>）。

4. 遍历逻辑：

   • 从head->next开始遍历，直到curr == nullptr结束。

4. 扩展优化方向

• 尾指针优化：添加tail指针，将push_back的时间复杂度从 O (n) 降为 O (1)。
• 双向链表：扩展为双向链表（每个节点增加prev指针），支持反向遍历和高效删除指定节点。
• 迭代器封装：实现迭代器（iterator），支持 C++ 风格的范围遍历（for (auto val : list)）。
• 异常安全：使用智能指针（unique_ptr）替代裸指针，自动管理内存，避免手动delete。