C++详解如何实现单链表

下面我就来为大家详细讲解C++如何实现单链表。

创建链表节点

在C++中，我们通常使用结构体来表示链表节点，结构体中包括了数据域和指向下一个节点的指针域。代码如下：

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

在上面的代码中，val为节点中存储的数据，next为指向下一个节点的指针。我们使用一个构造函数来初始化节点，将参数x赋值给val，将next初始化为空指针。

添加节点

要向链表中添加节点，我们需要先找到链表的尾部，然后将新节点插入到尾部后面。具体代码如下：

void addNode(ListNode* &head, int val) {
    ListNode* newNode = new ListNode(val);
    if (head == nullptr) {
        head = newNode;
        return;
    }
    ListNode* cur = head;
    while (cur->next != nullptr) {
        cur = cur->next;
    }
    cur->next = newNode;
}

在上面的代码中，&head表示head是一个指针的引用，即我们可以通过修改head指针的值来改变链表的头节点。newNode是即将被插入到链表中的新节点。如果链表为空，那么直接将头指针指向新节点即可。如果链表不为空，则需找到链表的尾部，将指向新节点的指针赋值给尾节点的next指针。

删除节点

要删除链表中的一个节点，我们需要先找到目标节点，并记录其前驱节点。然后将前驱节点的next指针指向目标节点的下一个节点即可。需要注意的是，对于头节点的删除，我们需要特殊处理，代码如下：

void deleteNode(ListNode* &head, int val) {
    ListNode* dummy = new ListNode(-1);
    dummy->next = head;
    ListNode* cur = head;
    ListNode* pre = dummy;
    while (cur != nullptr) {
        if (cur->val == val) {
            pre->next = cur->next;
            if (head == cur) head = cur->next; // 对于头节点的删除
            break;
        }
        pre = cur;
        cur = cur->next;
    }
    head = dummy->next;
    delete dummy;
}

在上面的代码中，我们使用一个虚拟节点来记录头指针的前驱节点。如果另外使用一个指针指向头节点的话，头节点的删除操作会比较麻烦。if (head == cur) head = cur->next;是对于头节点的特殊处理，如果发现要删除的节点是头节点，那么需要修改头指针为新的头节点。

示例说明

下面给出两个示例，分别是向链表中添加节点和从链表中删除节点。代码如下：

ListNode* head = nullptr;
addNode(head, 1);
addNode(head, 2);
addNode(head, 3);

在上述示例中，我们首先定义了一个空链表，然后依次添加了值为1、2、3的三个节点。最终链表的头节点指向值为1的节点，链表中有3个元素。

ListNode* head = nullptr;
addNode(head, 1);
addNode(head, 2);
addNode(head, 3);
deleteNode(head, 2);

在上述示例中，我们仍然首先定义了一个空链表，并添加了值为1、2、3的三个节点。然后我们删除了值为2的节点，最终链表中有两个元素，头节点为值为1的节点，尾节点为值为3的节点。

以上就是C++实现单链表的详细攻略。需要注意的是，为了防止内存泄漏，我们在删除节点时需要手动释放内存，即调用delete函数。如有疑问，欢迎继续探讨。