C++实现单链表（头加法）（在任意位置添加）

#include <iostream>
using namespace std; // 使用标准命名空间

// 定义模板类节点
template <typename T>
class Node 
{
public:
    T data;            // 存储节点数据
    Node* next;        // 指向下一个节点的指针

    // 构造函数初始化节点
    Node(T value) 
    {
        data = value;  // 初始化节点数据
        next = nullptr; // 初始化指向下一个节点的指针为空
    }
};

// 定义模板类单链表
template <typename T>
class LinkedList {
private:
    Node<T>* head;     // 指向链表头节点的指针

public:
    LinkedList() : head(nullptr) 
    {

    }  // 构造函数初始化头节点为空


    //LinkedList()
    //{
    //    head = nullptr;  // 在构造函数体内初始化头节点为空
    //}

    // 头插法插入新节点
    void insertAtHead(T value)
    {
        Node<T>* newNode = new Node<T>(value);  // 创建新节点  Node* newNode = new Node(value);
        
        newNode->next = head;  // 新节点指向当前头节点
        head = newNode;        // 头节点更新为新节点
    }

    // 在任意位置插入新节点
    void insertAtPosition(T value, int position) 
 {
        if (position <= 0) 
        {  // 如果位置小于等于0，直接头插法插入
            insertAtHead(value); // 插入新节点到头部
            return; // 结束函数
        }

        Node<T>* newNode = new Node<T>(value);  // 创建新节点
        Node<T>* current = head;  // 当前节点从头节点开始

        // 遍历到指定位置的前一个节点
        for (int i = 1; i < position-1 && current != nullptr; ++i) 
        {
            current = current->next; // 当前节点向后移动
        }

        if (current == nullptr) 
        {  // 如果当前位置超出链表长度
            cout << "位置超出链表长度，将在链表末尾插入。\n"; // 输出提示信息
            Node<T>* last = head; // 从头节点开始找最后一个节点
            while (last->next != nullptr) {  // 找到链表的最后一个节点
                last = last->next; // 移动到下一个节点
            }
            last->next = newNode;  // 在最后一个节点后插入新节点
        }
        else 
        {
            newNode->next = current->next;  // 新节点指向当前位置的下一个节点
            current->next = newNode;        // 前一个节点指向新节点
        }
    }

    // 打印链表
    void printList() const 
    {
        Node<T>* current = head;  // 从头节点开始遍历
        while (current != nullptr) 
        {  // 遍历到链表末尾
            cout << current->data << " -> ";  // 打印当前节点数据
            current = current->next;  // 移动到下一个节点
        }
        cout << "nullptr\n";  // 打印链表结束标志
    }

    // 析构函数，释放链表内存
    ~LinkedList() 
    {
        Node<T>* current = head;  // 从头节点开始遍历
        while (current != nullptr) 
        {  // 遍历到链表末尾
            Node<T>* nextNode = current->next;  // 保存下一个节点指针
            delete current;  // 删除当前节点
            current = nextNode;  // 移动到下一个节点
        }
    }
};

int main() 
{
    LinkedList<int> list;  // 创建一个整型单链表
    list.insertAtHead(10);  // 插入数据10到头部
    list.insertAtHead(20);  // 插入数据20到头部
    list.insertAtHead(30);  // 插入数据30到头部

    cout << "初始链表:\n"; // 输出提示信息
    list.printList();  // 打印链表

    list.insertAtPosition(25, 2);  // 在位置2插入数据25
    cout << "在位置2插入25后:\n"; // 输出提示信息
    list.printList();  // 打印链表

    list.insertAtPosition(5, 0);  // 在位置0插入数据5
    cout << "在位置0插入5后:\n"; // 输出提示信息
    list.printList();  // 打印链表

    list.insertAtPosition(50, 10);  // 在位置10插入数据50，超出范围
    cout << "在位置10插入50后 (超出范围):\n"; // 输出提示信息
    list.printList();  // 打印链表

    system("pause");
    return 0;  // 返回0，结束程序
}



//
//#include <iostream>
//using namespace std; // 使用标准命名空间

// 定义具体的节点类（处理 int 类型）
//class Node
//{
//public:
//    int data;        // 存储节点数据
//    Node* next;      // 指向下一个节点的指针
//
//    // 构造函数初始化节点
//    Node(int value)
//    {
//        data = value;  // 初始化节点数据
//        next = nullptr; // 初始化指向下一个节点的指针为空
//    }
//};
//
 定义具体的单链表类（处理 int 类型）
//class LinkedList {
//private:
//    Node* head;     // 指向链表头节点的指针
//
//public:
//    LinkedList() : head(nullptr)
//    {
//    }  // 构造函数初始化头节点为空
//
//    // 头插法插入新节点
//    void insertAtHead(int value)
//    {
//        Node* newNode = new Node(value);  // 创建新节点
//        newNode->next = head;  // 新节点指向当前头节点
//        head = newNode;        // 头节点更新为新节点
//    }
//
//    // 在任意位置插入新节点
//    void insertAtPosition(int value, int position) {
//        if (position <= 0) 
//        {  // 如果位置小于等于0，直接头插法插入
//            insertAtHead(value); // 插入新节点到头部
//            return; // 结束函数
//        }
//
//        Node* newNode = new Node(value);  // 创建新节点
//        Node* current = head;  // 当前节点从头节点开始
//
//        // 遍历到指定位置的前一个节点
//        for (int i = 1; i < position-1 && current != nullptr; ++i) 
//        {
//            current = current->next; // 当前节点向后移动
//        } 
//
//        if (current == nullptr) 
//        {  // 如果当前位置超出链表长度
//            cout << "位置超出链表长度，将在链表末尾插入。\n"; // 输出提示信息
//            Node* last = head; // 从头节点开始找最后一个节点
//            while (last != nullptr && last->next != nullptr) 
//            {  // 找到链表的最后一个节点
//                last = last->next; // 移动到下一个节点
//            }
//            if (last != nullptr) 
//            {
//                last->next = newNode;  // 在最后一个节点后插入新节点
//            }
//            else {
//                // 链表为空，直接插入新节点
//                head = newNode;
//            }
//        }
//        else 
//        {
//            newNode->next = current->next;  // 新节点指向当前位置的下一个节点
//            current->next = newNode;        // 前一个节点指向新节点
//        }
//    }
//
//    // 打印链表
//    void printList() const 
//    {
//        Node* current = head;  // 从头节点开始遍历
//        while (current != nullptr) 
//        {  // 遍历到链表末尾
//            cout << current->data << " -> ";  // 打印当前节点数据
//            current = current->next;  // 移动到下一个节点
//        }
//        cout << "nullptr\n";  // 打印链表结束标志
//    }
//
//    // 析构函数，释放链表内存
//    ~LinkedList() {
//        Node* current = head;  // 从头节点开始遍历
//        while (current != nullptr) {  // 遍历到链表末尾
//            Node* nextNode = current->next;  // 保存下一个节点指针
//            delete current;  // 删除当前节点
//            current = nextNode;  // 移动到下一个节点
//        }
//    }
//};
//
//int main() {
//    LinkedList list;  // 创建一个整型单链表
//    list.insertAtHead(10);  // 插入数据10到头部
//    list.insertAtHead(20);  // 插入数据20到头部
//    list.insertAtHead(30);  // 插入数据30到头部
//
//    cout << "初始链表:\n"; // 输出提示信息
//    list.printList();  // 打印链表
//
//    list.insertAtPosition(25, 2);  // 在位置2插入数据25
//    cout << "在位置2插入25后:\n"; // 输出提示信息
//    list.printList();  // 打印链表
//
//    list.insertAtPosition(5, 0);  // 在位置0插入数据5
//    cout << "在位置0插入5后:\n"; // 输出提示信息
//    list.printList();  // 打印链表
//
//    list.insertAtPosition(50, 10);  // 在位置10插入数据50，超出范围
//    cout << "在位置10插入50后 (超出范围):\n"; // 输出提示信息
//    list.printList();  // 打印链表
//    system("pause");
//    return 0;  // 返回0，结束程序
//}