CODEWITHSUNDEEP
clinked-listlogicdoubly-linked-list
Shail
Shail

Reputation: 901

Insertion in a doubly linked list in C

My program keeps on crashing. I think there's a problem in my logic. Please help! Thanks!

struct node{
    int data;
    struct node *prev,*next;
} *head = NULL;


void insert(){
    struct node* temp = (struct node*) malloc (sizeof (struct node*));
    int value;
    printf("Enter an element");
    scanf("%d",&value);
    temp -> data = value;
    temp -> next = NULL;
    temp -> prev = NULL;
    if(value < head -> data || head == NULL){
        temp -> next = head -> next;
        head = temp;
        return;
    }
    while(head->next != NULL && value > head -> next -> data)
        head = head -> next;
    temp -> next = head ->next->prev;
    head -> next = temp -> prev;
    while (head -> prev != NULL)
        head = head -> prev;
}

Upvotes: 1

Views: 11298

Answers (4)

AFKAP
AFKAP

Reputation: 63

There are two core problems I see.

  1. You are not allocating sufficient space for a node struct. sizeof(struct node *) returns the size of a node pointer, not a node. This:

    struct node* temp = (struct node*) malloc (sizeof (struct node*));`

    ... should be this:

    struct node* temp = (struct node*) malloc (sizeof (struct node));

  2. Be careful with pointers:

     if (value < head -> data || head == NULL)

    ... what is the value of head->data if you haven't initialized head? (e.g. it is still NULL). Your program will fetch data from address NULL with an offset for field data. Address NULL is not valid / is part of protected memory space, your OS won't like this :).

You should first check if head is NULL. If it is, then you can't reference fields of head as they are invalid (in any situation). Be careful with multi-part conditional expressions to check for struct pointer NULL presence prior to subsequent parts that reference struct fields, also.

Upvotes: 2

Charlie Burns
Charlie Burns

Reputation: 7044

Try this:

#include <stdio.h>
#include <stdlib.h>

struct node{
    int data;
    struct node *prev,*next;
} *head = 0;


void insert(int value){
    struct node* temp = (struct node*) malloc (sizeof (struct node));
    //int value;
    //printf("Enter an element");
    //scanf("%d",&value);
    temp -> data = value;
    temp -> next = 0;
    temp -> prev = 0;
    if(head == 0) {
        // no head, make temp the head
        head = temp;
    } else if(value > head->data) {
        // put temp in front of the head
        temp->next = head;
        head->prev = temp;
        head = temp;
    } else {
        // put temp after the head
        struct node *this = head;
        struct node *prev = 0;
        while(this && this->data > value) {
            prev = this;
            this = this->next;
        }
        temp->next = this;
        temp->prev = prev;
        prev->next = temp;
        if(this) {
            this->prev = temp;
        }
    }
}

int main() {
    insert(1);
    insert(3);
    insert(4);
    struct node *t = 0;
    for(t = head; t; t = t->next) {
        printf("%d\n", t->data);
    }
}

This one compiles and sorts in descending value. Note I commented out your scanf and made insert take a parameter.

Upvotes: 4

Paul
Paul

Reputation: 141829

As a start, think about these two lines and what happens if head == NULL:

if(value < head->data || head == NULL){
    temp->next = head->next;

Specifically what is head->next?

Upvotes: 4

vvy
vvy

Reputation: 2073

the space you malloc is not enough.

change

struct node* temp = (struct node*) malloc (sizeof (struct node*));

to

struct node* temp = (struct node*) malloc (sizeof (struct node));

Upvotes: 4

Related Questions