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 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);
}

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

Output: 30,20,10

Expected Output: 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);