oldDoctor oldDoctor - 4 months ago 9
C Question

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.

CODE:

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


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

Output: 30,20,10

Expected Output: 30,70,20,10

Answer

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 -   ---------|
------

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

Then call it like this:

insert_before(&head,head,70);