【数据结构】双向链表中删除节点的方法实现(代码+详解)
2023-12-13 16:31:13
【数据结构】双向链表中删除节点方法的实现(代码+详解)
分析
💕 在双向链表中,删除一个结点可能出现以下几种情况,取决于待删除的结点在链表中的位置:
-
删除头结点:
- 如果待删除的结点是头结点,需要特殊处理,更新头结点为原头结点的后继结点,并释放原头结点的内存。
-
删除尾结点:
- 如果待删除的结点是尾结点,需要特殊处理,更新尾结点为原尾结点的前驱结点,并释放原尾结点的内存。
-
删除中间结点:
- 如果待删除的结点位于链表的中间位置,只需调整前驱结点和后继结点的指针,将它们连接在一起,并释放待删除结点的内存。
💕 这些情况可以进一步细分为以下几类:
-
删除头结点
- 头结点是唯一结点
- 头结点后还有其他结点
-
删除尾结点
- 尾结点是唯一结点
- 尾结点前还有其他结点
-
删除中间结点
代码
#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;
}
文章来源:https://blog.csdn.net/weixin_75202470/article/details/134834446
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!