Sorting a linked list upon node insertion

While I know that linked lists seem to be a fairly common problem area among beginner C programmers, most examples that I have come across abstract the sorting of a linked list to a separate function which is sadly not what I am trying to do.

The code below is my attempt to have the nodes inserted into their correct place so that once all nodes have been inserted they are already in a sorted order.

Code:

---

int main(int argc, char *argv[])
{
    struct node_t* dict_head;
    struct node_t* traversor;
    struct node_t* newnode;


    int list_size = 0, insert_key, search_key, delete_key, x;
    char insert_word[WORDLEN];
   
   
    /*Opening the dictionary file provided by the command line argument */
    FILE *fp;
    fp = fopen(argv[1], "r");


    dict_head = malloc(sizeof(struct node_t));
    assert(dict_head != NULL);
    traversor = malloc(sizeof(struct node_t));
    assert(dict_head != NULL);
   
    while(fscanf(fp,"%d %s\n", &traversor->key, traversor->word) == 2){
        newnode =  malloc(sizeof(struct node_t));
        newnode->key = traversor->key;
        strcpy(newnode->word, traversor->word);
        traversor = dict_head;
       
        while(traversor->next!= NULL){
           
            if(traversor->next->key > newnode->key){break;}
           
            traversor = traversor->next;
        }
        printf("Traversor is sitting on %s\n", traversor->word);
        newnode->next = traversor->next;
        traversor->next = newnode;
        traversor = dict_head;
        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);
       
        printf("\n");
        list_size++;
    }
   
    return 0;
}

---

with node_t being

Code:

---

struct node_t{
    int key;
    char word[WORDLEN];
    struct node_t *next;
};

---

The problem is as follows. When you provide it with input in which the first word scanned is any other word than that which would be placed at the front of the list, it works as intended. For example.

7 world
0 ant
3 kodak
1 best
6 the
2 is

Produces ant -> best->is->kodak->best->world

However, swapping ant and world in the above input gives:
world->best->is->kodak->best->world


In regards to why I have my head node set as a node without a word or a key, it was suggested that I make it so that the first node inserted is set to be the head of the list and then changed as sorting required, yet this caused only additional problems.

Any help that can be given would be greatly appreciated :)

This seems wrong to me:

Code:

---

traversor = malloc(sizeof(struct node_t));

---

Generally, the conductor will be assigned such that it points to the head of the list, and then use the next members to traverse the list. Why are you allocating a node for the conductor to point to?

The algorithm for what you are trying to do would be (roughly) something like this:

1. Get input
2. Compare input to current node. (root node initially)
3. If comp(input, current_node->val) insert a new node before the current node. Else move to the next node.
4. If current_node == tail, insert the new node at the end of the list.

You also need to make sure that the list properties are maintained along the way.

Agreed, I removed the malloc for the traversor. Yet the same problem still manifests, and in my mind my program is following the above algorithm, so I honestly have no idea why it only works when the first line of input isn't the first item in the sorted list :(

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 ;)

I can't begin to express how grateful I am for your help tonight, were I able to give you more than one like I definitely would. Thanks for the in-depth analysis of what is going wrong, incredibly helpful after a night of staring at the code trying to fix it. Thanks again :biggrin:

If you move the next pointer to the beginning of the struct, then a pointer to pointer to node is the same as pointer to node->next. (The rule in C / C++ is the address to the first member of a struct is the same as the address of the struct). In this example, dict_head is initialized to NULL, and traversor is initialized as a pointer to dict_head, so that traversor->next == dict_head. I also added code to free the nodes after displaying them, using newnode as a temp pointer.

Code:

---

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

#define WORDLEN 24

struct node_t{
    struct node_t *next;
    int key;
    char word[WORDLEN];
};

int main(int argc, char *argv[])
{
    struct node_t* dict_head = NULL;
    /* since next is first member, this will work */
    struct node_t* traversor = (struct node_t *)&dict_head;
    struct node_t* newnode;
    int key;
    char word[WORDLEN];
    FILE *fp;
    fp = fopen(argv[1], "r");
    while(fscanf(fp,"%d %s\n", &key, word) == 2){
        newnode =  malloc(sizeof(struct node_t));
        newnode->key = key;
        strcpy(newnode->word, word);
        while(traversor->next!= NULL){
            if(traversor->next->key > newnode->key){break;}
            traversor = traversor->next;
        }
        newnode->next = traversor->next;
        traversor->next = newnode;
    }
    traversor = dict_head;
    while(traversor != NULL){
        printf("%s %d", traversor->word, traversor->key);
        newnode  = traversor;
        traversor = traversor->next;
        if(traversor)
            printf(" ->");
        free(newnode);
    }
    printf("\n");
    return(0);
}

---

Correction to previous code example. traversor needs to be initialized each time a node is inserted / appended to the list. Same principle, since next is first member of node_t, then setting traversor = &dict_head results in traversor->next == dict_head.

Code:

---

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

#define WORDLEN 24

struct node_t{
    struct node_t *next;
    int key;
    char word[WORDLEN];
};

int main(int argc, char *argv[])
{
    struct node_t* dict_head = NULL;
    struct node_t* traversor;
    struct node_t* newnode;
    int key;
    char word[WORDLEN];
    FILE *fp;
    fp = fopen(argv[1], "r");
    while(fscanf(fp,"%d %s\n", &key, word) == 2){
        newnode =  malloc(sizeof(struct node_t));
        newnode->key = key;
        strcpy(newnode->word, word);
        /* since next is first member, this will work */
        traversor = (struct node_t *)&dict_head;
        while(traversor->next!= NULL){
            if(traversor->next->key > newnode->key){break;}
            traversor = traversor->next;
        }
        newnode->next = traversor->next;
        traversor->next = newnode;
    }
    traversor = dict_head;
    while(traversor != NULL){
        printf("%s %d", traversor->word, traversor->key);
        newnode  = traversor;
        traversor = traversor->next;
        if(traversor)
            printf(" -> ");
        free(newnode);
    }
    printf("\n");
    return(0);
}

---

When using %s in scanf I prefer always limit the number of chars to read to prevent buffer overrun, so line 22 I would write

Code:

---

while(fscanf(fp,"%d %23s", &key, word) == 2){

---