用 C++ 删除链表中的节点

Jinku Hu 2021年6月28日
用 C++ 删除链表中的节点

本文将讨论如何在链表 C++ 中实现删除给定节点的函数的方法。

实现删除链表中给定节点的函数

在本文中,我们从头开始实现一个单向链表,而不使用 STL 中的容器。因此,我们需要定义一些必要的函数来管理链表中的节点。

insertNode 元素是创建新链表需要调用的核心函数。由于我们需要存储列表的头部,insertNode 返回指向 ListNode 类型节点的指针。后者是链表节点的最小表示。它只包含一个指向下一个节点的指针和 string 数据对象。

在程序的测试和演示过程中,重要的是要有一些实用函数来向用户控制台显示一些消息。在这种情况下,printNodes 元素用于打印给定列表结构中的所有节点。此外,在动态内存上分配新节点时,我们需要使用 freeNodes 函数在程序退出时释放列表中的每个现有节点。

一旦我们构建了一个包含任意数据的列表,如以下代码片段的 main 函数所示,我们就可以调用 deleteNode,它实现节点删除操作。节点的移除需要在其中处理几个极端情况。即,当给定节点与列表的头部相同时的场景,当给定节点是列表中的唯一节点时的另一个场景。

在后一种情况下,我们可以在节点指针上调用 delete 运算符并从函数返回。尽管将 nullptr 分配给地址很重要,因为这将帮助我们将新元素添加到 main 函数中的同一个 head 变量中。

另一方面,当链表中还有其他节点时,移除头节点是比较棘手的。我们必须将第二个节点的内容复制到头节点并删除前一个。请注意,每个案例都返回 EXIT_SUCCESS 值以指示成功的函数调用。

#include <iostream>
#include <string>

using std::cout; using std::cin;
using std::endl; using std::string;

struct ListNode {
    struct ListNode *next{};
    string data;
};

struct ListNode *insertNode(struct ListNode *root, string data) {
    auto new_node = new ListNode;
    if (root) {
        while (root->next)
            root = root->next;

        new_node->next = nullptr;
        new_node->data = std::move(data);
        root->next = new_node;

        return root->next;
    }
    new_node->next = nullptr;
    new_node->data = std::move(data);
    return new_node;
}

int deleteNode(struct ListNode *root, struct ListNode *node) {
    if (node == nullptr || root == nullptr)
        return EXIT_FAILURE;

    if (root == node) {
        if (root->next == nullptr) {
            delete node;
            root = nullptr;
            return EXIT_SUCCESS;
        }

        node = root->next;
        root->data = root->next->data;
        root->next = root->next->next;
        delete node;
        return EXIT_SUCCESS;
    }

    auto prev = root;
    while (prev->next != node && prev->next != nullptr) {
        prev = prev->next;
    }

    prev->next = node->next;
    delete node;
    return EXIT_SUCCESS;
}

void freeNodes(struct ListNode *root) {
    struct ListNode *tmp = nullptr;
    while (root) {
        tmp = root;
        root = root->next;
        delete tmp;
    }
}

void printNodes(struct ListNode *node) {
    auto count = 0;
    while (node){
        cout << "node " << count << " - data: " << node->data << endl;
        node = node->next;
        count++;
    }
}

int main() {
    struct ListNode *head = nullptr;

    head = insertNode(head, "Xenial");

    insertNode(head, "Artful");
    printNodes(head);
    cout << " ----------------------------------- " << endl;


    deleteNode(head, head);
    printNodes(head);

    freeNodes(head);
    return EXIT_SUCCESS;
}

输出:

node 0 - data: Xenial
node 1 - data: Artful
 -----------------------------------
node 0 - data: Artful

其余的函数代码实现了常规情况,其中给定节点从列表链中解开,然后使用 delete 运算符解除分配。但是请注意,此操作需要找到前一个节点,这是对除列表头部之外的每个节点的线性时间操作。通常,为了保证链表末尾的恒定时间移除,应该将链表的末尾存储在链表结构中。

下面的代码片段演示了一个不同的 main 函数场景,其中从列表中间删除了一个节点。

#include <iostream>
#include <string>

using std::cout; using std::cin;
using std::endl; using std::string;

struct ListNode {
    struct ListNode *next{};
    string data;
};

struct ListNode *insertNode(struct ListNode *root, string data) {
    auto new_node = new ListNode;
    if (root) {
        while (root->next)
            root = root->next;

        new_node->next = nullptr;
        new_node->data = std::move(data);
        root->next = new_node;

        return root->next;
    }
    new_node->next = nullptr;
    new_node->data = std::move(data);
    return new_node;
}

int deleteNode(struct ListNode *root, struct ListNode *node) {
    if (node == nullptr || root == nullptr)
        return EXIT_FAILURE;

    if (root == node) {
        if (root->next == nullptr) {
            delete node;
            root = nullptr;
            return EXIT_SUCCESS;
        }

        node = root->next;
        root->data = root->next->data;
        root->next = root->next->next;
        delete node;
        return EXIT_SUCCESS;
    }

    auto prev = root;
    while (prev->next != node && prev->next != nullptr) {
        prev = prev->next;
    }

    prev->next = node->next;
    delete node;
    return EXIT_SUCCESS;
}

void freeNodes(struct ListNode *root) {
    struct ListNode *tmp = nullptr;
    while (root) {
        tmp = root;
        root = root->next;
        delete tmp;
    }
}

void printNodes(struct ListNode *node) {
    auto count = 0;
    while (node){
        cout << "node " << count << " - data: " << node->data << endl;
        node = node->next;
        count++;
    }
}

int main() {
    struct ListNode *head = nullptr;

    head = insertNode(head, "Xenial");

    auto iter = insertNode(head, "Bionic");
    insertNode(head, "Artful");
    printNodes(head);
    cout << " ----------------------------------- " << endl;


    deleteNode(head, iter);
    printNodes(head);

    freeNodes(head);
    return EXIT_SUCCESS;
}

输出:

node 0 - data: Xenial
node 1 - data: Bionic
node 2 - data: Artful
 -----------------------------------
node 0 - data: Xenial
node 1 - data: Artful
Author: Jinku Hu
Jinku Hu avatar Jinku Hu avatar

Founder of DelftStack.com. Jinku has worked in the robotics and automotive industries for over 8 years. He sharpened his coding skills when he needed to do the automatic testing, data collection from remote servers and report creation from the endurance test. He is from an electrical/electronics engineering background but has expanded his interest to embedded electronics, embedded programming and front-/back-end programming.

LinkedIn

相关文章 - C++ Data Structure