Sorted insert program in a linked list

Question

I am a beginner in Data structures and I am learning linked list now . I encountered a program about sorted insert where I had an add() function to add the nodes in the sorted order

         /*Linked List program to add ascending order sorted nodes in     

         the list */
 #include <stdio.h>
  #include <stdlib.h>
enter code here
 struct node {
   int data ;
   struct node link;

 };

 void add(struct node **q,int num){
    struct node *r,*temp = *q;
    r = malloc(sizeof(struct node )); //Data Allocated
    r->data = num;

    if(*q==NULL ||(*q)->data >num){
     *q = r;
     (*q)->link = temp;

    }else{
      while(temp !=NULL){
         if(temp->data <=num &&(temp->link->data >num                    
                                             ||temp->link==NULL)){
             r->link = temp->link;
             temp->link=r;
             return;
         }
          temp = temp->link;
      }

    }

 }

 void main(){
 struct node *p;
 p = NULL;

 }

I have expected to add the nodes in sorted ascending order but when I input data then error is shown.I am Using Code Blocks to run the program in C

I think it has to do something with the end condition temp->link == null but I am unable to figure out exact condition for that part of code .Please Help !

You are checking for temp !=NULL but you are accessing temp->link. temp->link can be NULL in which case you have undefined behaviour. — Rishikesh Raje
– Rishikesh Raje, Commented Sep 27, 2019 at 7:18
Also the structure definition is wrong. Maybe you wanted. struct node *link; — Rishikesh Raje
– Rishikesh Raje, Commented Sep 27, 2019 at 7:20

Rishikesh Raje · Accepted Answer · 2019-09-27 07:35:44Z

3

The definition for the structure struct node is not correct. I assume it is a typo. It should be struct node *link;
Your conditions for traversing the loop are not correct. As mentioned in the comments, you are accessing temp->link in case it might be NULL.
You are not checking for the condition that the number to be added is greater than all the numbers and is to be added at the end of the list.

The modified function is below.

 void add(struct node **q,int num){
    struct node *r,*temp = *q;
    r = malloc(sizeof(struct node )); //Data Allocated
    r->data = num;
    r->link = NULL;

    if(*q==NULL ||(*q)->data >num){
     *q = r;
     (*q)->link = temp;

    }else{
      while(temp->link !=NULL){
         if(temp->data <=num &&(temp->link->data >num)){
             r->link = temp->link;
             temp->link=r;
             return;
         }
         temp = temp->link;
      }
      temp ->link = r; // add at the end as not added at any other location.
    }
}

answered Sep 27, 2019 at 7:35

Rishikesh Raje

8,6222 gold badges18 silver badges33 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Viraj Kumar Over a year ago

Thanks for your help ! But besides Any typing error I wanted to know the exact logic where I can specify the numbers at the end of the linked list where temp->link is null and A larger number has to inserted at the end of the list

Viraj Kumar Over a year ago

As you can see there is no explicit condition for that

Rishikesh Raje Over a year ago

In the code above, if you exit the while loop you are at the end of the list and the number is greater than all the numbers in the list. It is added at the end by temp ->link = r;

Aconcagua · Accepted Answer · 2019-09-27 07:55:13Z

In addition to Rishikesh Raje's answer (you need to use a pointer inside struct: struct node* link;; you need to check first for link being null, then access link->data), the loop can be simplified quite a bit:

// advance only, if we need to insert (at least) after temp->link:
while(temp->link && temp->link->data <= num)
{
    temp = temp->link;
}
// once the loop is done, temp points to the last element smaller than num, so:
r->link = temp->link;
temp->link = r;

Inside the while, we don't need to check for temp->data > num; we re-enter the loop only, if the loop condition was met previously, which checked exactly this condition already; remains the very first loop run; however, in this case, your if before the loop covered the condition already.

Side note: Is it a requirement to insert new elements after the existing ones? If not, inserting in front of is a bit faster, all you'd do is replacing <= with < and > with >=...

ybalcanci · Accepted Answer · 2019-09-27 07:23:12Z

0

You should use

( temp->link == NULL || temp->link->data > num )

instead of

( temp->link->data > num || temp->link == NULL )

because if temp->link is NULL, the first code will return true immediately after checking the first condition and will not check the second condition, thus you will not get an error. But when you use it like in the second expression, if temp->link is NULL, you will get an error because you are trying to reach a field named "data" of a NULL object with the code

temp->link->data

answered Sep 27, 2019 at 7:23

ybalcanci

1053 silver badges9 bronze badges

Collectives™ on Stack Overflow

Sorted insert program in a linked list

3 Answers 3

3 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

3 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related