在C中的双向链表中删除头节点的问题

Question

我正在尝试在 C 中实现双向链表。在编写代码时，我运行在尝试删除列表的第一个元素时遇到了问题。

这是一个说明问题的玩具示例：

 #include<stdio.h>
 #include <stdlib.h>

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


 Node* create_dll(int array[], int arrSize){
     Node *current = (Node*)malloc(sizeof(Node));
     current->next = NULL;
     current->data = array[0];
     for(int i = 1; i < arrSize; i++){
         Node *temp = (Node*)malloc(sizeof(Node));
         temp->data = array[i];
         temp->next = current;
         current->previous  = temp;
         current = temp;
     }
     current->previous = NULL; 
     return current;
 }
 void print_dll(Node *head){
     if(head != NULL){
         Node *current = head;
         while(current!=NULL){
         printf("%d \t", current ->data);
             current = current->next;
         }
     }
     puts(" ");
 }

 void delete_head(Node *head){
     Node *current = head;
     head = head->next;
     //head ->previous = NULL;
     free(current);
 }
 void kill(Node *head){
     Node *current = head;
     while (current != NULL){
         Node *previous = current;
         current = current ->next;
         free(previous);
     }
 }

 int main(){
     int array [] = {1, 2, 3, 4, 5};
     int arrSize = 5;

     Node *head;

     head = create_dll(array, 5);

     print_dll(head);

     delete_head(head);
     print_dll(head);

     kill(head);
     return 0;

}

每当我尝试运行 main 中的代码时，它会创建一个 DLL，然后打印其中的内容，然后尝试删除第一个节点，然后再次打印列表，我得到以下结果：

    5   4   3   2   1    
    5

现在，我知道一个解决方法是使 head 成为一个全局变量，但这在代码的其他部分会有问题，而且我真的不想走那条路。我也不想修改任何函数头或 main 中的任何内容。

我确实通过使用 head 始终指向的虚拟节点实现 DLL 来实现此功能，但我确信此实现有一个简单的修复程序可以避免所有这些问题。

基本上，如果我可以更改 head 在 delete_head 函数中指向的内容并将此更改反映在主要功能中，这将是一个解决方案。否则，我很乐意理解为什么这段代码无法执行我想要的操作。

非常感谢任何帮助！谢谢！

Answer 1

诀窍是，所有外部指针都指向单个节点。因此，当您将头部从列表的其余部分切掉时，所有指向 head 的指针都会继续指向它——您得到的是它自己的单个节点，而不是列表的其余部分。

我会通过添加一个额外的结构来解决这个问题。

typedef struct DLL{
    struct Node * head;
} DLL;

当你想创建列表时，创建一个指向头部的DLL，而不是返回头部本身。现在当你想改变头部时，改变 DLL 结构中的指针。所有对 DLL 本身的引用都可以保持不变，但是现在它里面的 head 已经改变了，所有这些引用在查找时都会看到新的 head！

Answer 2

问题在于，当您调用 delete_head 时，C 参数传递是按值传递的，因此在 return 上不会更改 head。你需要这样实现它：

void delete_head(Node **head){
            Node *current = *head;
            *head = current->next;
            //head ->previous = NULL;
            free(current);
}

并这样称呼它：delete_head(&head);

在C中的双向链表中删除头节点的问题

Problem deleting head node in a doubly linked list in C

c

pointers

doubly-linked-list