Appending nodes alphabetically to create linked list. Can't get nodes to link (C program)

Question

I have problem with this section of my code for, some reason everything seems to work fine but when I print out the whole linked list it only prints the header and next node if it went through "if (compare_node(list, node) == -1)" function. I have written that rest = list, but operations I do on rest doesn't seem to affect the list variable. I need help on how to link the output of rest variables to list variable which is the header of my code.

link *add_node(link *list, link *node) { //  list = header, node =  new node I want to insert alphabetically
    link* temp;
    link* rest;
    rest = list;

    if (compare_node(list, node) == -1){
        temp = list;
        list = node;
        list->next = temp;
        printf("%s->%s->%s...\n",list->node_str, list->next->node_str, list->next->next->node_str);
        printf("nodes interchanged\n");
    }
    else{
        while(rest != NULL){
            if(compare_node(rest, node) == -1){
                printf("initial rest value: %s\n", rest->node_str);
                temp = rest;
                rest = node;
                rest->next = temp;
                printf("nodes interchanged, new rest value: %s\n", rest->node_str); //nodes interchanged: name
                printf("%s->%s->%s...\n",list->node_str, list->next->node_str, list->next->next->node_str);
                return list;
            }
            rest = rest->next;
            printf("next rest value: %s\n", rest->node_str); //next rest value: name
        }
        rest = node;
        printf("new rest value %s\n", rest->node_str);
    }
    return list;
}

my output looks like this:
Enter the user name for user N1: mike
Enter the user name for user N2: ann
ann->mike->(null)...
nodes interchanged
Enter the user name for user N3: luka
next rest value: mike
initial rest value: mike
nodes interchanged, new rest value: luka
ann->mike->(null)...
Enter the user name for user N4: nick
next rest value: mike
next rest value: (null)
new rest value nick
Enter the user name for user N5:
1. ann
2. mike

My whole Code looks like this:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_STR_LEN 80

//STRUCT
typedef struct link_node
{
char node_str[MAX_STR_LEN];
struct link_node *next;
} link;

void Node_Create(link *Node, char* userName, link *nextNode);
int compare_node(link *n1, link *n2);
link *add_node(link *list, link *node);
void display_list(link *head);

//MAIN
int main() {
    int num, i = 1;
    char name[MAX_STR_LEN];
    link *Curr, *Head;

    printf("Enter the user name for user N%d: ", i);
    gets(name);
    Head = (link*)malloc(sizeof(link));
    Node_Create(Head, name, NULL);
    i++;

    while(1){
        printf("Enter the user name for user N%d: ", i);
        gets(name);
        if (strcmp(name, "\0") == 0) break;
        Curr = (link*)malloc(sizeof(link));
        Node_Create(Curr, name, NULL);
        Head = add_node(Head, Curr);
        i++;
    }

    display_list(Head);
    printf("\n%s\n", Head->node_str);

    return 0;
}

//FUNCTION FOR CREATING NODES
void Node_Create(link *Node, char* userName, link *nextNode) {
    strcpy(Node->node_str, userName);
    Node->next = nextNode;
}

//FUNCTION FOR COMPARING NODES
int compare_node(link *n1, link *n2) {
    link* Temp;

    if(n1->node_str[0] > n2->node_str[0])
        return -1;
    else if(n1->node_str[0] == n2->node_str[0])
        return 0;
    else
        return 1;
}

//FUNCTION FOR ADDING NODES
link *add_node(link *list, link *node) { //  list = header, node =  new node I want to insert alphabetically
    link* temp;
    link* rest;
    rest = list;

    if (compare_node(list, node) == -1){
        temp = list;
        list = node;
        list->next = temp;
        printf("%s->%s->%s...\n",list->node_str, list->next->node_str, list->next->next->node_str);
        printf("nodes interchanged\n");
    }
    else{
        while(rest != NULL){
            if(compare_node(rest, node) == -1){
                printf("initial rest value: %s\n", rest->node_str);
                temp = rest;
                rest = node;
                rest->next = temp;
                printf("nodes interchanged, new rest value: %s\n", rest->node_str); //nodes interchanged: name
                printf("%s->%s->%s...\n",list->node_str, list->next->node_str, list->next->next->node_str);
                return list;
            }
            rest = rest->next;
            printf("next rest value: %s\n", rest->node_str); //next rest value: name
        }
        rest = node;
        printf("new rest value %s\n", rest->node_str);
    }
    return list;
}

//FUNCTION FOR DISPLAYING NODES
void display_list(link *head) {
    link *rest = head;
    int i = 1;

    while(rest != NULL){
        printf("%d. %s\n", i++, rest->node_str);
        rest = rest->next;
    }
}

Thanks in advance :)

regarding: `gets(name);` The function: `gets()` has been depreciated for years and completely removed from the C language about a decade ago. Strongly suggest using `fgets()` (which does have a different parameter list than `gets()`) — user3629249, Nov 19 '20 at 08:46
See `addinorder()` within [Singly Linked List (node only, no wrapper)](https://pastebin.com/5MPLU4wB). For strings, you would replace `while (ps && ps->data <= pn->data)` with `while (ps && strcmp (ps->data, pn->data) < 0)`. More importantly see [Why gets() is so dangerous it should never be used!](https://stackoverflow.com/q/1694036/3422102). Use `fgets (name, MAX_STR_LEN, stdin)` instead and trim the `'\n'` from the end with `name[strcspn (name, "\n")] = 0;` — David C. Rankin, Nov 19 '20 at 08:46
when compiling, always enable the warnings, then fix those warnings. — user3629249, Nov 19 '20 at 08:49
thanks I will do that but I don't think that's the reason it doesn't wok. @DavidC.Rankin — yung_tesla, Nov 19 '20 at 08:49
regarding the function: `compare_node()` is this to try and produce a sorted list? — user3629249, Nov 19 '20 at 08:50
Or probably better (but dynamically allocating for the string) is [Singly Linked List of Strings With Sorted Insertion](https://pastebin.com/PechfyQa) See [Linus on Understanding Pointers](https://grisha.org/blog/2013/04/02/linus-on-understanding-pointers/) for details on iterating using both the *address of the pointer* and pointer -- which makes list insertions and deletions much simpler. — David C. Rankin, Nov 19 '20 at 08:50
no compare_node() is to return integer values by comparing the first letter of each name(for example, if first node has "bigger" first character than second node it will return -1). sorted list should be produced in add_node(). @user3629249 — yung_tesla, Nov 19 '20 at 08:53
Yes, that will work too, it just means the sort of two strings with the same first character won't be strictly sorted. From an efficiency standpoint, calling `strcmp()` does essentially the same thing and stops when it reaches the first character that differs -- or end of string, so the first-char trick doesn't do much from an optimization standpoint. — David C. Rankin, Nov 19 '20 at 08:59
the posted code results in a massive memory leak. Before exiting the program, pass each of the allocated (via `malloc()`) memory segments to `free()`. — user3629249, Nov 19 '20 at 09:13
OT: regarding: `Head = (link*)malloc(sizeof(link));` The function: `malloc()` can fail. Always check (!=NULL) the returned value to assure the operation was successful.. If not successful (==NULL) then call `perror( "malloc failed" );` which will output both your error message and the text reason the system thinks the error occurred to `stderr` — user3629249, Nov 19 '20 at 09:20
thank you very much, I just started learning structs and linked lists and your comments are very helpful. @user3629249 — yung_tesla, Nov 19 '20 at 09:27

Serge Ballesta · Answer 1 · 2020-11-19T09:08:16.903

1

First 2 remarks. As you have already been told in comments, do not use gets, and use strcmp to compare strings (you version only compare the first character of both strings).

Now for the actual problem:

To insert a node in a linked list, you must change the link of the previous node. Let's say we have in lexicographic order B < X < C and the list is A -> B -> C -> D. You tests will say:

X > A: try next
X > B: try next
x < C: ok insert

But you have to do:

B->next = X;
X->next = C;

It is useless to change the value of any other variable, that means that you have to record the previous node.

edited Nov 19 '20 at 09:08

answered Nov 19 '20 at 08:58

Serge Ballesta

143,923
11
122
252

Thanks for the explaining, but I'd like to know, how can I record the previous node? especially in the case where the head variable is replaced? – yung_tesla Nov 19 '20 at 09:03
also, rest is initialized with "list". I have "rest = list;" written right after "link* rest;" – yung_tesla Nov 19 '20 at 09:06

score 1 · Accepted Answer · answered Nov 19 '20 at 09:26

To replace the previous node you must keep a pointer to it. As an example, you can do it this way :

    link * prev = NULL; 
    while(rest != NULL){
        if(compare_node(rest, node) == -1){
            temp = rest;
            rest = node;
            rest->next = temp;
            if (prev) prev->next = rest; //<==== Sets the next of previous
            return list;
        }
        prev = rest; // <=== Stores previous
        rest = rest->next;
        printf("next rest value: %s\n", rest->node_str); //next rest value: name
    }
    rest = node;
    printf("new rest value %s\n", rest->node_str);

When the head is changed you don't need that since, by definition, there is no node before head.

Thank you man this explains it. I was struggling with my code for so long and I think you just resolved it. — yung_tesla, Nov 19 '20 at 09:36

Appending nodes alphabetically to create linked list. Can't get nodes to link (C program)

2 Answers2