Sorted linked list function (C)

Question

I'm a beginner who has been self-teaching for the past weeks data structures. I'm trying to create a function that inserts an integer into a linked lists in a sorted fashion.

Here's my function:

void sortedInsert(int n)
{
    node *temp = malloc(sizeof(node));
    temp->data= n;

    //if list is empty or n is less than minimum number in the list, insert at the beggining.
    if(head == NULL || n < head->data )
    {
        temp->next = head;
        head = temp;
    }
    else
    {
        node *cur, *prev, *temp;
        for (cur = head, prev = NULL
             cur != NULL && cur->data < n;  //if n is less than cur->value it breaks out of loop
             prev = cur, cur = cur->next);

         //now cur is pointing at last node or the node it broke out off

         if( n < cur->data)
         {
             temp->next = cur;
             prev->next = temp;
         }
         else
         {
             //if its larger than the maximun number in the list
             //insert at end 
             temp->next = NULL;
             cur->next = temp;
         }

         free(cur);
         free(prev);
    }
}

Output:

How many numbers?
4
Enter the number
10
List is:  10
Enter the number
4
List is:  4 10
Enter the number
5

Process returned -1073741819 (0xC0000005)   execution time : 7.161 s
Press any key to continue.

It crashes out whenever I insert a number greater than those on the list. I'll appreciate any help or guidance I could get.

If you have calls to free in your insert functions, you are doing it wrong. Can you justify these calls? — n. m. could be an AI
– n. m. could be an AI, Commented Dec 25, 2016 at 9:00
1) if( n < cur->data) need check of cur != NULL 2) free(cur); free(prev); are wrong. 3) for (cur = head, prev = NULL --> for (cur = head, prev = NULL; — BLUEPIXY
– BLUEPIXY, Commented Dec 25, 2016 at 9:00
You free nodes (not pointers) you no longer need. Can a list after an insertion contain one less node than before? — n. m. could be an AI
– n. m. could be an AI, Commented Dec 25, 2016 at 9:16

ilim · Accepted Answer · 2016-12-25 09:30:29Z

1

The erroneous behavior is in the for loop inside the else statement. That loop terminates in two conditions. The first is, if a node with data that is greater than or equal to n is found. The second is when cur is NULL. If you traverse all the list before finding a node with a value greater than or equal to n, the loop will terminate when cur becomes NULL.

Therefore you need to check if cur is NULL or not, and you should not use it as if it will definitely be a value that is not NULL.

To achieve the behavior you desire, I believe you should get rid of the if-else statement following the for loop and instead just use the two lines below.

temp->next = cur;
prev->next = temp;

In addition to that, before the for loop, you declaring temp variable once more causes temp you declared in the beginning of the function to be inaccessible for that scope. That second declaration should be removed as well.

Finally, although you did not specify the desired behavior of your function, based on the semantic implications of the name of your function, I believe you do not need to make calls to free(), and you should remove them.

So, after making the changes I mentioned, here's how your code should look.

void sortedInsert(int n)
{
    node *temp = malloc(sizeof(node));
    temp->data= n;

    //if list is empty or n is less than minimum number in the list, insert at the beggining.
    if(head == NULL || n < head->data )
    {
        temp->next = head;
        head = temp;
    }
    else
    {
        node *cur, *prev;
        for (cur = head, prev = NULL
             cur != NULL && cur->data < n;  //if n is less than cur->value it breaks out of loop
             prev = cur, cur = cur->next);

         //now cur is pointing at last node or the node it broke out off
         temp->next = cur;
         prev->next = temp;
    }
}

edited Dec 25, 2016 at 9:30

answered Dec 25, 2016 at 9:06

ilim

4,5477 gold badges30 silver badges50 bronze badges

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

3 Comments

tadm123 Over a year ago

Makes sense. In the for loop, would breaking out if cur->next = NULL, fix this?

tadm123 Over a year ago

The program is crashing when I used the code above @ilim.

ilim Over a year ago

I forgot to remove the redefinition of temp variable inside else. I fixed it now, you may try again.

Collectives™ on Stack Overflow

Sorted linked list function (C)

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related