inserting new element in linked list with sorting C

Question

I have a problem in inserting string in right position (insert sorting) in linked list. When i add some positions in linked list and end program by typing ' 0 ', program show me only first position. Also i have doubts about "(strcmp(tmp->ch,new->ch)>0)" it is working as i'm thinking?(compare new element with current (i mean it should be '>' or '<')). I will be really grateful for any advices ;) .There is my code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_L 30

typedef struct elem{
    char ch[MAX_L];
    struct elem *next;
    struct elem *prev;
}   list_elem;

void add_to_list (list_elem *first, char ch[MAX_L])
{
    list_elem *new=(list_elem*)malloc(sizeof(list_elem));

    strcpy(new->ch, ch);
    list_elem *tmp=first;
    do
    {
        if(tmp->next==NULL)
        {
            tmp->next=new;
            new->prev=tmp;
            new->next=NULL;
        }
        if (strcmp(tmp->ch,new->ch)>0) //guess here should be inserted new element
        {
            new->prev=tmp->prev;
            new->next=tmp;
            tmp->prev=new;
        }
        else
        tmp=tmp->next;

    }while (tmp->next!=NULL);

}


void print_list(list_elem *first)
{
    first=first->next;
    if(first->ch==NULL)
    printf("lista jest pusta!!\n");
    while(first->next!=NULL){
    printf("%s\n",first->ch);
    first=first->next;}
    printf("%s\n",first->ch);
}



int main()
{
    list_elem *first=(list_elem*)calloc(1,sizeof(list_elem));
    first->next=NULL;
    first->prev=NULL;

    char a;
    char ch[MAX_L];
    printf("write ' 0 ' to end program.\n");
    printf("write smth to add it to list: \n");
        while(ch[0]!='0'){
        scanf("%s",&ch);
        add_to_list(first,ch);}
    print_list(first);
    return 0;
}

Hint 1: What happens after you inserted in the middle of the linked list?. Hint 2: Turn on all your compiler warnings. If using gcc, be sure to set -Wall — Missaka Wijekoon, Jan 08 '16 at 23:30

score 2 · Answer 1 · edited Jan 09 '16 at 04:33

list_elem *first=(list_elem*)calloc(1,sizeof(list_elem));

How do you know whether calloc succeeded or not?
Check whether first is NULL or not and then only access first->next.

while(ch[0]!='0')

Till this point ch array contains garbage. So how you can compare it with ch[0] with '0'?

scanf("%s",&ch);

%s expects argument of char * type whereas type of &ch is char (*)[30].

Also you may want to avoid the accidental buffer overflow if user enters the string with length > sizeof(ch). Specify maximum field width to remedy that.

first=first->next; in print_list()

Here you just skipped the very first element.

if(first->ch==NULL)

What you really want to do here? Most probably you want to check whether the string first->ch is empty or not. If yes then this is not the way to check that. Instead check first->ch[0] == '\0'

while(ch[0]!='0')

For checking whether user entered 0 or other string, this is incorrect way. This will reject strings starting from 0 (e.g. "0bar")

Correct way would be:

while((ch[0]!='0') || (strlen(ch) > 1))

Break out of the loop once you inserted the new node in the list
```
if (strcmp(tmp->ch,new->ch)>0) 
{  
     new->prev=tmp->prev;
     new->next=tmp;
     tmp->prev=new;
}
```
Here after inserting the new node the if expression strcmp(tmp->ch,new->ch)>0 will remain true in all subsequent loop iterations as we haven't change tmp and new. So this will lead to an infinite loop.

The only exception to this if tmp is the last node.

Solution:

break out of the loop as soon as the new node is inserted into the list. Just write break; as the last statement in above strcmp if

1. Well i don't know about this that it can be not "NULL" i thought calloc will do that first will be "NULL" 2. Dunno it's working for me so i'm happy for that and didn't think about that :f — shiro, Jan 09 '16 at 00:58
3. again don't know about that i just thought when something is introduced by keyboard i thought there should be & 5 . yea i want to check if its a empty but in that way it was working so again i was happy that it works :c 6. well i forget about that way thanks :D — shiro, Jan 09 '16 at 01:02

score 0 · Answer 2 · edited May 23 '17 at 12:15

It looks like when you're inserting before tmp you aren't setting tmp->prev->next to new

For clarity:

if (strcmp(tmp->ch,new->ch)>0) //guess here should be inserted new element
    {
        new->prev=tmp->prev;
        new->next=tmp;
        tmp->prev=new;
    }

Should be:

if (strcmp(tmp->ch,new->ch)>0) //guess here should be inserted new element
    {
        tmp->prev->next=new;
        new->prev=tmp->prev;
        new->next=tmp;
        tmp->prev=new;
    }

Side note: using new for a variable name is generally frowned upon as it isn't immediately recognizable as a variable since most programmers will have experience in Java/C#/C++ etc. where new is a keyword.

Side note #2: don't cast malloc. I did it until recently when I read this stack thread. It's a very good read.

score 0 · Accepted Answer · answered Jan 08 '16 at 23:49

There's problems in the add_to_list loop :

do {
    if(tmp->next==NULL)
    {
        tmp->next=new;
        new->prev=tmp;
        new->next=NULL;
        break; // you must exit here, you don't want to go the "if" below...
    }
    if (strcmp(tmp->ch,new->ch)>0) 
    {
        if( tmp->prev != NULL ) 
        {
            tmp->prev->next = new; // link from previous to the new element 
        }
        new->prev=tmp->prev;
        new->next=tmp;
        tmp->prev=new;
        break; // you should exit here, work is done
    }
    else {
        tmp=tmp->next;
    }
} while (1); // try again

A problem also here:

scanf("%s",&ch); // should be scanf("%s",ch);

And for your question:

Also i have doubts about "(strcmp(tmp->ch,new->ch)>0)" it is working as i'm thinking?

If you're wrong you'll sort in the reverse order, so it'll be easy to fix.

thanks ! its working but its putting one position in incorrect order anyway again thanks for help! :D — shiro, Jan 09 '16 at 01:03

inserting new element in linked list with sorting C

3 Answers3