Thread: Sorting a linked list upon node insertion

Hi James,

When you cross-post a question (i.e., post it to multiple forums), say so and include links to the other posts. Otherwise (and I promise there are multiple users here that also subscribe to C on S.O.) people will get irritated with you, because it means someone can end up wasting time giving you help that you already got elsewhere.

Let's look at some potential pitfalls with your code:

Code:

    dict_head = malloc(sizeof(struct node_t));

On most modern operating systems, the various fields in 'traversor' will be zero'd out, hence 'traversor->next' will be NULL. However, you should not rely on this,

• because it is coincidental -- the reason it is zero'd out is NOT to initialize your struct, and
  
• because it's not guaranteed to happen.

Instead, you should initialize the fields after you allocate memory, or use calloc() or memset(). This is important because the first place dict_head gets used is:

Code:

traversor = dict_head;
         
while(traversor->next!= NULL){

If your OS had not coincidentally zero'd dict_head, traversor->next would be a random junk address and you would seg fault here. Note also that on the first run, you have leaked the memory you assigned to traversor.

Something eventually becomes of the traversor pointer in this loop:

Code:

while(fscanf(fp,"%d %s\n", &traversor->key, traversor->word) == 2){

[...]
        for(x = 0; x < list_size; x++)
        {
            printf("%d %s %d ->", traversor, traversor->word, traversor->key);
            traversor = traversor->next;
        }
       printf("%d %s %d",traversor->next, traversor->next->word, traversor->next->key);
[...]
}

At the end, 'traversor' is the last node in the list. Then the loop re-iterates and *gasp* you overwrite it with fscanf().:/ Remember this point.

Next let's consider your insertion:

Code:

        while(traversor->next!= NULL){
             
            if(traversor->next->key > newnode->key){break;}
             
            traversor = traversor->next;
        }

If traversor == dict_head, and dict_head->key == 0 (since dict_head was not initialized, and so coincidentally zero'd), then the "if" condition will always be true, unless newnode->key is also zero.

That won't sort at all, since everything will just get inserted at the beginning.

Except remember that point about overwriting traversor? This means the second insertion will now overwrite dict_head (since after the first one, traversor == dict_head). Now the sorting will work, just not quite via the mechanism you intended; although traversor will be overwritten, it won't matter because you actually have two copies of that first node on the first insertion (traversor, which you wrote into, and newnode, which you copied into). This is how you potentially end up with two "worlds".

But if the first thing you put in has a key of 0, the next insertion will get put in front of that and the "ant" node will be leaked here:

Code:

        newnode->next = traversor->next;
        traversor->next = newnode;
        traversor = dict_head

Because it was in the traversor node and when you reassign the pointer, that node is not attached to anything anymore (hence, leaked).

-- Goldilocks