如何用c++实现一个链表单链表的创建、插入和删除【数据结构】

C++单链表需定义节点结构和链表类，手动管理内存；核心操作包括头插（O(1)）、指定位置插入（需遍历）、按值删除（分头/中/尾处理），并需实现析构函数防止内存泄漏。

用 C++ 实现单链表，核心是定义节点结构、管理头指针，并封装插入、删除等操作。不需要依赖 STL 容器，手动管理内存更利于理解数据结构本质。

定义节点结构和链表类

每个节点包含数据域和指向下一节点的指针；链表类维护头指针（可为 nullptr 表示空表）：

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};
class LinkedList {
private:
ListNode* head;
public:
LinkedList() : head(nullptr) {}
~LinkedList(); // 后续需实现析构释放内存
};

在链表头部插入节点（最简单）

时间复杂度 O(1)，适合频繁在开头增删的场景：

新建节点，赋值
新节点 next 指向原 head
更新 head 指向新节点

void insertAtHead(int value) {
    ListNode* newNode = new ListNode(value);
    newNode->next = head;
    head = newNode;
}

在指定位置插入（如第 i 个位置，从 0 开始）

需遍历到前一个节点，注意边界检查（i 小于 0 或超过长度时可忽略或报错）：

i == 0 等价于头插，直接调用 insertAtHead
遍历至第 i−1 个节点（prev），若 prev 为 nullptr 说明越界
新建节点，接在 prev 后面：newNode→next = prev→next；prev→next = newNode

void insertAt(int index, int value) {
    if (index == 0) {
        insertAtHead(value);
        return;
    }
    ListNode* prev = head;
    for (int i = 0; i < index - 1 && prev != nullptr; ++i) {
        prev = prev->next;
    }
    if (prev == nullptr) return; // 位置无效
    ListNode* newNode = new ListNode(value);
    newNode->next = prev->next;
    prev->next = newNode;
}

删除节点（按值或按位置）

以按值删除为例（删第一个匹配的节点），需处理三种情况：

空链表 → 直接返回
头节点即目标 → 更新 head，并 delete 原头节点
中间或尾部节点 → 找到前驱 prev，跳过目标节点，并释放内存

void deleteByValue(int value) {
    if (!head) return;
    if (head->val == value) {
        ListNode* temp = head;
        head = head->next;
        delete temp;
        return;
    }
    ListNode* prev = head;
    while (prev->next && prev->next->val != value) {
        prev = prev->next;
    }
    if (prev->next) {
        ListNode* toDelete = prev->next;
        prev->next = toDelete->next;
        delete toDelete;
    }
}

补充：遍历与析构（避免内存泄漏）

打印链表用于调试：

void print() {
    ListNode* cur = head;
    while (cur) {
        std::cout << cur->val;
        if (cur->next) std::cout << " → ";
        cur = cur->next;
    }
    std::cout << std::endl;
}

析构函数应逐个释放节点：

LinkedList::~LinkedList() {
    while (head) {
        ListNode* temp = head;
        head = head->next;
        delete temp;
    }
}

不复杂但容易忽略

# node # c++ # 封装 # 析构函数 # 指针 # 数据结构 # delete # 链表 # 遍历 # 第一个 # 不需要 # 下一 # 三种 # 为例 # 报错 # 最简单

返回目录在线咨询

上一篇：国内网站使用GoDaddy建站时如何确保网站速度优化？
下一篇：网站服务器数据迁移对SEO有何影响？如何降低负面影响？

您的项目需求

*请认真填写需求信息，我们会在24小时内与您取得联系。

全网整合营销服务商