CODEWITHSUNDEEP
clinked-listdoubly-linked-listsorting
Sarin Nanda
Sarin Nanda

Reputation: 35

Inserting a node into a sorted doubly linked list

I am trying to enter a new node in a sorted linked list. I do not know what is wrong in this code.

Node* SortedInsert(Node *head,int data)
{
    struct Node *temp=head,*p=NULL;
    struct Node *newNode=(struct Node*)malloc(sizeof(struct Node));
    newNode->data=data;
    newNode->next=NULL;
    newNode->prev=NULL;
    if(!head){
        return newNode;
    }

    while((data>=(temp->data)) && temp!=NULL){
        p=temp;
        temp=temp->next;
    }
    if(temp==NULL){
        p->next=newNode;
        newNode->prev=p;
        return head;
    }
    if(p==NULL){
        head->prev=newNode;
        newNode->next=head;
        return newNode;
    }

    p->next=newNode;
    newNode->prev=p;
    newNode->next=temp;
    temp->prev=newNode;

    return head;
}

Upvotes: 1

Views: 3069

Answers (2)

rcgldr
rcgldr

Reputation: 28828

Seems like Eelke's answer was the key issue. Here's an example using a typedef for Node to eliminate the need for struct Node, since it wasn't used consistently in the example code:

#include <malloc.h>
#include <stdio.h>

typedef struct Node_{
    struct Node_ *next;
    struct Node_ *prev;
    int data;
}Node;

Node* SortedInsert(Node *head,int data)
{
    Node *temp=head,*p=NULL;
    Node *newNode=(Node*)malloc(sizeof(Node));
    newNode->data=data;
    newNode->next=NULL;
    newNode->prev=NULL;
    if(!head){
        return newNode;
    }
    while(temp!=NULL && (data>=(temp->data))){
        p=temp;
        temp=temp->next;
    }
    if(temp==NULL){
        p->next=newNode;
        newNode->prev=p;
        return head;
    }
    if(p==NULL){
        head->prev=newNode;
        newNode->next=head;
        return newNode;
    }
    p->next=newNode;
    newNode->prev=p;
    newNode->next=temp;
    temp->prev=newNode;
    return head;
}

int main(int argc, char *argv[])
{
Node * head = NULL;
Node *pNode;
    head = SortedInsert(head, 2);
    head = SortedInsert(head, 5);
    head = SortedInsert(head, 3);
    head = SortedInsert(head, 4);
    head = SortedInsert(head, 1);
    while(head){        /* scan to last */
        pNode = head;
        head = head->next;
    }
    while(pNode){       /* follow last to first */
        printf("%d\n", pNode->data);
        head = pNode;
        pNode = pNode->prev;
    }
    printf("\n");
    while(head){        /* follow first to last and free */
        printf("%d\n", head->data);
        pNode = head;
        head = head->next;
        free(pNode);
    }
    return(0);
}

Upvotes: 2

Eelke
Eelke

Reputation: 21993

The line

while((data>=(temp->data)) && temp!=NULL){

should read

while(temp!=NULL && (data>=(temp->data))){

You need to test temp is not NULL first otherwise you might do an invalid read which can cause an access violation.

Upvotes: 3

Related Questions