【数据结构】双向链表中删除节点方法的实现(代码+详解)
分析
💕 在双向链表中，删除一个结点可能出现以下几种情况，取决于待删除的结点在链表中的位置：
- 删除头结点：
- 如果待删除的结点是头结点，需要特殊处理，更新头结点为原头结点的后继结点，并释放原头结点的内存。
- 删除尾结点：
- 如果待删除的结点是尾结点，需要特殊处理，更新尾结点为原尾结点的前驱结点，并释放原尾结点的内存。
- 删除中间结点：
- 如果待删除的结点位于链表的中间位置，只需调整前驱结点和后继结点的指针，将它们连接在一起，并释放待删除结点的内存。
💕 这些情况可以进一步细分为以下几类：
- 删除头结点
- 头结点是唯一结点
- 头结点后还有其他结点
- 删除尾结点
- 尾结点是唯一结点
- 尾结点前还有其他结点
- 删除中间结点
代码
#include <stdio.h> #include <stdlib.h> // 定义双向链表的结点结构 typedef struct Node { int data; struct Node* prev; // 前驱指针 struct Node* next; // 后继指针 } Node; // 删除双向链表的头结点 Node* deleteHead(Node* head) { if (head == NULL) { printf("Error: Empty list\n"); return NULL; } Node* newHead = head->next; if (newHead != NULL) { newHead->prev = NULL; } free(head); printf("Head node deleted successfully.\n"); return newHead; } // 删除双向链表的尾结点 Node* deleteTail(Node* head) { if (head == NULL) { printf("Error: Empty list\n"); return NULL; } if (head->next == NULL) { free(head); printf("Tail node (and the only node) deleted successfully.\n"); return NULL; } Node* current = head; while (current->next->next != NULL) { current = current->next; } free(current->next); current->next = NULL; printf("Tail node deleted successfully.\n"); return head; } // 删除双向链表的中间结点 Node* deleteMiddle(Node* head, int target) { if (head == NULL) { printf("Error: Empty list\n"); return NULL; } Node* current = head; while (current != NULL && current->data != target) { current = current->next; } if (current == NULL) { printf("Error: Node with data %d not found in the list\n", target); return head; } if (current->prev != NULL) { current->prev->next = current->next; } if (current->next != NULL) { current->next->prev = current->prev; } free(current); printf("Node with data %d deleted successfully.\n", target); return head; } // 打印双向链表的内容 void printList(Node* head) { Node* current = head; while (current != NULL) { printf("%d ", current->data); current = current->next; } printf("\n"); } int main() { // 创建一个简单的双向链表：1 <-> 2 <-> 3 <-> 4 Node* head = (Node*)malloc(sizeof(Node)); head->data = 1; head->prev = NULL; head->next = (Node*)malloc(sizeof(Node)); head->next->data = 2; head->next->prev = head; head->next->next = (Node*)malloc(sizeof(Node)); head->next->next->data = 3; head->next->next->prev = head->next; head->next->next->next = (Node*)malloc(sizeof(Node)); head->next->next->next->data = 4; head->next->next->next->prev = head->next->next; head->next->next->next->next = NULL; printf("Original list: "); printList(head); // 删除头结点 head = deleteHead(head); printf("List after deleting head: "); printList(head); // 删除尾结点 head = deleteTail(head); printf("List after deleting tail: "); printList(head); // 删除中间结点（例如，删除值为3的结点） head = deleteMiddle(head, 3); printf("List after deleting middle node: "); printList(head); return 0; }
