在双向链表中的给定节点之前插入节点 [英] Inserting a node before a given node in doubly linked list

问题描述

我正在尝试在给定节点之前插入一个节点.但是我无法获得所需的输出.

I am trying to insert a node before a given node. But I am not able to get the required output.

#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).

Here I am trying to insert a node(with data = 70) before 20.

输出:30,20,10

Output: 30,20,10

预期产量:30,70,20,10

Expected Output: 30,70,20,10

推荐答案

调用 insert_before 时，如果给定节点是头，则新节点将是新头.因此，您需要传递 head 的地址才能对其进行修改.

When you call insert_before, if the given node is the head, then the new node will be the new head. So you need to pass the the address of head in order to modify it.

您现在所拥有的看起来像这样:

What you have right now looks like this:

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

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

To fix this, include the address of head in the parameters to 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);

这篇关于在双向链表中的给定节点之前插入节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！