c-在双链表中的给定节点之前插入一个节点

Question

我试图在给定节点之前插入一个节点。但我无法获得所需的输出。

#include<stdio.h>
#include<stdlib.h>
struct node{
    int data;
    struct node* prev;
    struct node* next;
};
void insert_beg(struct node** head, int new_data){
    struct node* temp = (struct node*)malloc(sizeof(struct node));
    temp->data = new_data;
    if(*head == NULL){
        temp->next = *head;
        temp->prev = NULL;          
        *head = temp;
    }
    else{
        temp->next = *head;     
        (*head)->prev = temp;
        *head = temp;
     }
}
void insert_before(struct node* next_node,int new_data){
    struct node* temp = (struct node*)malloc(sizeof(struct node));
    temp->data = new_data;
    if(next_node == NULL)
        printf("Invalid!!!!");

    temp->prev = next_node->prev;
    temp->next = next_node;
    next_node->prev = temp;
    if(temp->prev!=NULL)
        temp->prev->next = temp;
}
void printList(struct node* head){
    if(head == NULL)
        printf("The list is emptyn"); 
    else
        {
            while(head!=NULL){
                printf("%dn",head->data);              
                head = head->next;              
              }
         }
}
int main(){
    struct node* head = NULL;   
    printList(head);    
    insert_beg(&head,10);
    insert_beg(&head,20);
    insert_before(head,70); 
    insert_beg(&head,30);
    printList(head);
}

在这里，我试图在20之前插入一个节点（数据=70）。

输出：30,20,10

预期输出：30,70,20,10

Answer 1

当您调用insert_before时，如果给定节点是头，那么新节点将是新头。所以你需要传递head的地址才能修改它

你现在拥有的是这样的：

head
  |
  v
------          ------          ------
- 30 -   --->   - 20 -   --->   - 10 - 
------   <---   ------   <---   ------
                  ^
------            |
- 70 -   ---------|
------

要解决此问题，请在insert_before的参数中包含head的地址。

void insert_before(struct node **head, struct node *next_node, int new_data){
    struct node* temp = malloc(sizeof(struct node));   // don't cast the return value of malloc
    temp->data = new_data;
    if(next_node == NULL)
        printf("Invalid!!!!");

    temp->prev = next_node->prev;
    temp->next = next_node;
    next_node->prev = temp;
    if(temp->prev!=NULL) {
        temp->prev->next = temp;
    } else {
        *head = temp;
    }
}

然后这样称呼它：

insert_before(&head,head,70);

Answer 2

你做的每件事都很好。但在insert_before中，您缺少了一件事，如果传递的参数next_node是head，那么您将在head之前插入一个节点。因此，您必须将这个新添加的节点设置为head。