Why aren't new elements being added to my linked list?

Question

This is just a snippet of the code, but I checked and know for a fact that all the strings save nicely into the "new" element (in function SortedInsert), but then the "new" doesn't link to the head? I've tried everything I could think, hopefully I'm just missing something obvious.

typedef struct _Info* Position;
typedef struct _Info{
    char name[MAX];
    char surname[MAX];
    Position next;
} Info;

(declaration inside main function:
    Info headInfo = {.name = {0}, .surname {0}, .next = NULL};
    Position head = &headInfo;
)

int SortedInsert(Position head, char name[], char surname[]){

    Position prev = NULL, temp = NULL, new = NULL;

    prev = head;
    temp = head->next;

    new = (Position)malloc(sizeof(Info));

    if(!new){
        return EXIT_FAILURE;
    }

    strcpy(new->name, name);
    strcpy(new->surname, surname);
    new->next = NULL;

    if(head->next==NULL){
        temp = new;
    }
    else{
        // first sort, by surname
        while(strcmp(temp->surname, new->surname) < 0){
            prev = temp;
            temp = temp->next;
        }
        // second sort, by name
        while(strcmp(temp->name, new->name) < 0){
            prev = temp;
            temp = temp->next;
        }        
        new->next = prev->next;
        prev->next = new;
    }

    return EXIT_SUCCESS;
}

int PrintList(Position head){

    Position temp = NULL;

    temp = head->next;

    while(temp){
        printf("%s ", temp->name);
        printf("%s\n", temp->surname);
        printf("---\n");
        temp = temp->next;
    }

    return EXIT_SUCCESS;
}

Word of advice. Start by writing a separate insert function that inserts after a specified element. Then write a function that finds where to insert an element. Then make `SortedInsert` call those functions. That will make debugging much easier. — klutt, Jan 04 '22 at 22:40
Unrelated, if you think hiding pointer types in typedef aliases (looking at you, `Position`) brings clarity to C code, think again. It has the exact *opposite* effect. There are only two legitimate instances where pointer-type aliasing is genuinely warranted (blackbox "handle" APIs, and function pointer types), and this is neither of them. Embrace the splats. — WhozCraig, Jan 04 '22 at 22:41
And your insertion logic for while-loops i broken as well. Besides what was said prior by user3386109 , you should only descend into `name` comparison when the `surname` is (and remains) *equivalent*, not just no-longer-lesser. Gel on that awhile and you'll understand. — WhozCraig, Jan 04 '22 at 22:52

score 0 · Accepted Answer · answered Jan 05 '22 at 22:00

Some issues:

temp = new does not insert anything into the list. It merely copies a reference to the new node into a local variable. The assignment should be to head->next. Moreover, there is no need to create a separate case for this. It can be handled with the code you have in the else part.
The retrieval of the insert point is not correct. If in the first loop the strcmp call returns 1 (not 0), then the second while loop should not iterate at all: it doesn't matter in that case what the first name is like. The last name of temp is already greater, so the insertion point has been found. Similarly, if the strcmp call returns 0, the second loop should keep verifying that the last name is still the same in its second iteration,...etc. Moreover, this logic can be combined in one loop.

Not a problem for the correct execution, but still:

Many consider it bad practice to typedef a pointer to a struct where you dereference the pointer regularly in your code. See the answers to Is it a good idea to typedef pointers? for some background. So I'd keep using Info *.
Create a separate function for creating and initialising a node.
The comments that say "first sort", "second sort" are misleading. There is no sorting happening in the loop that follows the comment. The list is already sorted. The process that follows just intends to find the insertion spot according to the sort order. So the comment could be improved.
Many consider it better not to cast the value returned by malloc.

Here is the correction of the SortedInsert function, together with the separated function for node creation:

Info *createNode(char name[], char surname[]) {
    Info *new = malloc(sizeof(*new));

    if (new != NULL) {
        strcpy(new->name, name);
        strcpy(new->surname, surname);
        new->next = NULL;
    }
    return new;
}

int SortedInsert(Info *head, char name[], char surname[]){
    Info *new = createNode(name, surname);
    if (new == NULL) {
        return EXIT_FAILURE;
    }

    Info *prev = head;
    Info *temp = head->next;

    // Find insertion spot according to sort order
    while (temp != NULL) {
        int cmp = strcmp(temp->surname, new->surname);
        if (cmp == 0) { // It's a tie. Then use name as discriminator
            cmp = strcmp(temp->name, new->name);  
        }
        if (cmp >= 0) { // Found insertion spot
            break;
        }
        prev = temp;
        temp = temp->next;
    }
    new->next = prev->next;
    prev->next = new;
    return EXIT_SUCCESS;
}

Why aren't new elements being added to my linked list?

1 Answers1