删除单链表中的节点

基础概念

单链表（Singly Linked List）是一种线性数据结构，其中每个元素称为节点（Node），每个节点包含两部分：数据域和指针域。数据域存储数据，指针域存储下一个节点的地址。链表的头节点（Head Node）指向第一个节点，最后一个节点的指针域指向空（NULL）。

删除节点的优势

动态内存管理：链表可以动态地分配和释放内存，适合不确定大小的数据集合。
插入和删除操作高效：在已知节点的情况下，插入和删除操作的时间复杂度为O(1)。
空间利用率高：链表不需要连续的内存空间，适合内存碎片化的环境。

类型

单链表有多种变体，包括：

单向链表（Singly Linked List）：每个节点只有一个指向下一个节点的指针。
双向链表（Doubly Linked List）：每个节点有两个指针，一个指向前一个节点，一个指向后一个节点。
循环链表（Circular Linked List）：链表的最后一个节点指向头节点，形成一个环。

应用场景

动态数据存储：如缓存、队列、栈等。
内存管理：如垃圾回收机制。
图和树的遍历：如深度优先搜索（DFS）。

删除节点的操作

删除单链表中的节点通常涉及以下步骤：

找到要删除的节点：从头节点开始遍历，直到找到目标节点。
修改指针：将目标节点的前一个节点的指针指向目标节点的下一个节点。

示例代码

以下是一个删除单链表中节点的示例代码（假设节点结构如下）：

struct Node {
    int data;
    struct Node* next;
};

删除节点的函数如下：

void deleteNode(struct Node** head_ref, int key) {
    // 如果头节点就是要删除的节点
    if (*head_ref != NULL && (*head_ref)->data == key) {
        struct Node* temp = *head_ref;
        *head_ref = (*head_ref)->next;
        free(temp);
        return;
    }

    // 查找要删除的节点
    struct Node* current = *head_ref;
    struct Node* previous = NULL;
    while (current != NULL && current->data != key) {
        previous = current;
        current = current->next;
    }

    // 如果节点不存在
    if (current == NULL) {
        return;
    }

    // 删除节点
    previous->next = current->next;
    free(current);
}