在双向链表中给定节点之前插入一个节点

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 empty\n"); 
    else 
     { 
      while(head!=NULL){ 

       printf("%d\n",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); 
} 

在这里，我试图插入的节点（与数据= 70）前20

输出：30,20,10

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

Answer 1

当您拨打insert_before时，如果给定节点是头部，则新节点将成为新头部。所以你需要通过head的地址来修改它。

你现在看起来是这样的：

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

为了解决这个问题，包括head在参数insert_before地址。

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

你正在做right.But你缺少一个东西在insert_before如果传递的参数next_node是头，那么你将被插入头节点之前的一切。因此，您必须将此新添加的节点设为head。