用C语言代码实现单链表的插入与删除

<think>好的，我现在需要帮用户解决如何用C语言实现单链表的插入和删除操作。首先，我得回忆单链表的基本结构。单链表每个节点应该包含数据和指向下一个节点的指针。所以结构体定义应该是这样的： struct Node { int data; struct Node* next; }; 接下来是插入操作。插入分为头部插入、尾部插入和中间插入。用户可能需要全部，所以我得分别考虑。比如头部插入，需要创建新节点，然后让新节点的next指向原头节点，再更新头指针。如果是尾部插入，则需要遍历到最后一个节点，然后修改其next指向新节点。中间插入的话，得找到要插入的位置的前驱节点，调整指针指向。 然后是删除操作。同样分为头节点删除、中间和尾部删除。删除头节点比较简单，直接将头指针指向下一个节点并释放内存。删除中间或尾部节点需要找到前驱节点，然后调整指针，跳过要删除的节点，再释放内存。 接着要考虑代码的健壮性，比如处理空链表的情况，或者删除的节点不存在时的错误处理。例如，如果链表为空，插入尾部其实和头部插入一样；删除时如果链表为空，应该提示错误。 可能还需要写一个打印链表的函数来测试插入和删除的效果。这样用户可以看到操作后的链表状态。 然后，我需要把这些步骤用C语言代码写出来。比如，插入函数可能需要传递头指针的地址，因为头指针本身可能需要修改。使用双指针或者返回新的头指针都是常见的方法，这里用双指针可能更直观。 在写具体代码的时候，要注意内存分配，使用malloc申请新节点，删除时用free释放内存。还要注意指针的操作顺序，避免内存泄漏或者悬空指针。 举个例子，比如在头部插入： void insertAtHead(struct Node** head_ref, int data) { struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); new_node->data = data; new_node->next = *head_ref; *head_ref = new_node; } 删除特定值的节点： void deleteNode(struct Node** head_ref, int key) { struct Node* temp = *head_ref, *prev = NULL; if (temp != NULL && temp->data == key) { *head_ref = temp->next; free(temp); return; } while (temp != NULL && temp->data != key) { prev = temp; temp = temp->next; } if (temp == NULL) return; prev->next = temp->next; free(temp); } 测试的时候，用户可能需要创建链表，执行插入删除，然后打印结果。所以需要提供完整的示例，包括main函数，这样用户可以直接编译运行。 此外，应该提醒用户注意内存管理，避免内存泄漏。比如，每次删除节点后都要释放内存，插入时检查malloc是否成功。 最后，总结步骤，让用户清晰了解每个部分的功能，并强调指针操作的重要性，因为这是链表实现中的关键点。</think>以下是用C语言实现单链表插入与删除的详细步骤及代码示例： --- ### 一、单链表结构定义 ```c #include <stdio.h> #include <stdlib.h> // 定义链表节点 struct Node { int data; // 数据域 struct Node* next; // 指针域 }; ``` --- ### 二、插入操作实现 #### 1. 头部插入 $$时间复杂度：O(1)$$ ```c void insertAtHead(struct Node** head_ref, int data) { // 创建新节点 struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); new_node->data = data; new_node->next = *head_ref; // 新节点指向原头节点 *head_ref = new_node; // 更新头指针 } ``` #### 2. 尾部插入 $$时间复杂度：O(n)$$ ```c void insertAtTail(struct Node** head_ref, int data) { struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); new_node->data = data; new_node->next = NULL; // 如果链表为空，直接作为头节点 if (*head_ref == NULL) { *head_ref = new_node; return; } // 遍历到链表尾部 struct Node* last = *head_ref; while (last->next != NULL) { last = last->next; } last->next = new_node; // 尾部插入新节点 } ``` --- ### 三、删除操作实现 #### 1. 删除指定值的节点 $$时间复杂度：O(n)$$ ```c void deleteNode(struct Node** head_ref, int key) { struct Node* temp = *head_ref; struct Node* prev = NULL; // 如果头节点就是要删除的节点 if (temp != NULL && temp->data == key) { *head_ref = temp->next; // 更新头指针 free(temp); // 释放内存 return; } // 遍历查找目标节点 while (temp != NULL && temp->data != key) { prev = temp; temp = temp->next; } // 未找到目标节点 if (temp == NULL) return; // 调整指针跳过目标节点 prev->next = temp->next; free(temp); // 释放内存 } ``` --- ### 四、辅助函数 #### 1. 打印链表 ```c void printList(struct Node* node) { while (node != NULL) { printf("%d -> ", node->data); node = node->next; } printf("NULL\n"); } ``` --- ### 五、完整示例代码 ```c int main() { struct Node* head = NULL; // 插入测试 insertAtTail(&head, 10); insertAtHead(&head, 5); insertAtTail(&head, 20); printf("原始链表: "); printList(head); // 输出: 5 -> 10 -> 20 -> NULL // 删除测试 deleteNode(&head, 10); printf("删除后: "); printList(head); // 输出: 5 -> 20 -> NULL return 0; } ``` --- ### 六、关键点说明 1. **指针操作**：插入和删除时需要特别注意指针的指向顺序，避免链表断裂 2. **内存管理**： - 插入时必须用`malloc`动态分配内存 - 删除后必须用`free`释放内存，防止泄漏 3. **边界条件**： - 链表为空时的处理 - 删除头节点时的特殊处理 - 遍历链表时防止空指针访问 通过上述代码可以清晰理解单链表的操作原理。实际开发中建议封装链表操作函数，提高代码复用性。