C++链表

template <typename T>
class LinkedList
{
public:
    struct Node
    {
        T data;
        Node *next;
        Node (const T& value, Node* nextNode = nullptr) : data(value), next(nextNode){};
    }

    LinkedList():head(nullptr), size(0)
    {
    }
    ~LinkedList()
    {
        clear();
    }

    void insert(int index, const T& value)
    {
        if(index < 0 || index > size)
        {
            throw std::out_of_range("Index out of range");
        }
        if(index == 0)
        {
            head = new Node(value, head);
        } else
        {
            Node* current = head;
            for(int i = 0; i < index - 1; ++i)
            {
                current = current->next;
            }
            current->next = new Node(value, current->next);    // 不是同一个next
        }
        ++size;
    }

}

#include <iostream>
#include <stdexcept>

template <typename T>
class LinkedList {
public:
    // 定义链表节点结构
    struct Node {
        T data;       // 数据域
        Node* next;   // 指针域
        Node(const T& value, Node* nextNode = nullptr) : data(value), next(nextNode) {}
    };

    // 构造函数
    LinkedList() : head(nullptr), size(0) {}

    // 析构函数
    ~LinkedList() {
        clear();
    }

    // 禁止拷贝构造和赋值操作
    LinkedList(const LinkedList&) = delete;
    LinkedList& operator=(const LinkedList&) = delete;

    // 插入元素
    void insert(int index, const T& value) {
        if (index < 0 || index > size) {
            throw std::out_of_range("Index out of range");
        }
        if (index == 0) {
            head = new Node(value, head);
        } else {
            Node* current = head;
            for (int i = 0; i < index - 1; ++i) {
                current = current->next;
            }
            current->next = new Node(value, current->next);
        }
        ++size;
    }

    // 在链表尾部追加元素
    void append(const T& value) {
        insert(size, value);
    }

    // 删除指定索引的元素
    void remove(int index) {
        if (index < 0 || index >= size) {
            throw std::out_of_range("Index out of range");
        }
        Node* toDelete;
        if (index == 0) {
            toDelete = head;
            head = head->next;
        } else {
            Node* current = head;
            for (int i = 0; i < index - 1; ++i) {
                current = current->next;
            }
            toDelete = current->next;
            current->next = toDelete->next;
        }
        delete toDelete;
        --size;
    }

    // 查找元素，返回其索引
    int find(const T& value) const {
        Node* current = head;
        int index = 0;
        while (current != nullptr) {
            if (current->data == value) {
                return index;
            }
            current = current->next;
            ++index;
        }
        return -1; // 未找到返回 -1
    }

    // 获取指定索引的元素
    T& get(int index) {
        if (index < 0 || index >= size) {
            throw std::out_of_range("Index out of range");
        }
        Node* current = head;
        for (int i = 0; i < index; ++i) {
            current = current->next;
        }
        return current->data;
    }

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

    // 清空链表
    void clear() {
        while (head != nullptr) {
            Node* toDelete = head;
            head = head->next;
            delete toDelete;
        }
        size = 0;
    }

    // 打印链表
    void print() const {
        Node* current = head;
        while (current != nullptr) {
            std::cout << current->data << " ";
            current = current->next;
        }
        std::cout << std::endl;
    }

private:
    Node* head; // 链表头指针
    int size;   // 链表长度
};

int main() {
    LinkedList<int> list;

    // 测试插入
    list.append(10);
    list.append(20);
    list.append(30);
    list.insert(1, 15); // 在索引 1 处插入 15
    std::cout << "After insert: ";
    list.print(); // 输出：10 15 20 30

    // 测试删除
    list.remove(2); // 删除索引 2 的元素
    std::cout << "After remove: ";
    list.print(); // 输出：10 15 30

    // 测试查找
    int index = list.find(15);
    std::cout << "Index of 15: " << index << std::endl; // 输出：Index of 15: 1

    // 测试获取元素
    std::cout << "Element at index 2: " << list.get(2) << std::endl; // 输出：Element at index 2: 30

    // 测试链表长度
    std::cout << "Length of list: " << list.length() << std::endl; // 输出：Length of list: 3

    // 测试清空
    list.clear();
    std::cout << "After clear: ";
    list.print(); // 输出：（空）

    return 0;
}

---

来源：CSDN 原文，首次发布于 2025-04-16。