Linked list implementation mistake in C

Question

I have a program written in C. And I struggle with the effect I can't understand. The app reads a sequence of words as a command line input. While reading an input it puts one-by-one words into a list. And then it prints the list. What blows my mind is why values added ouside the loop are printed correctly whilst values added inside the loop aren't. I mean whichever values are input by user, only the last one will be printed. And furthermore it will be printed as many times as the number of values were input is. The two primary suspects are push and printList methods:

void push(struct List * list, char* newValue){
    assert(list != NULL);
    assert(newValue != NULL);

    Node* node = createNode();
    node->data = newValue;
    node->next = NULL;
    if(list->firstNode != NULL){
        node->next = list->firstNode;
        list->firstNode = node;
    }
    else list->firstNode = node;
}

void printList(struct List * list){
    assert(list != NULL);
    Node *node = list->firstNode;
    while(node->next != NULL){
        printf("%s ", node->data);
        node = node->next;
    }
    if(node != NULL) printf("%s ", node->data);
}

But I couldn't find any bugs in there. What I did is I compared the behaviour with and without a while loop:

int main(){
    struct List* list = createList();
    char s[256];
    int a;
    push(list, "he");
    push(list, "bee");
    push(list, "gee");
    while(scanf("%s", &s) == 1) push(list, s);
    printList(list);
}

The output I got is:

c c c gee bee he

Whilst the input is:

a b c

So I expected to get

c b a gee bee he

What did I miss? Any suggestion is highly appreciated.

P.S. The type defs and methods used above are:

typedef struct Node {
    char* data;
    struct Node *next;
} Node;

typedef struct List {
    struct Node *firstNode;
} List;

Node *createNode(){
    Node* node = malloc(sizeof(struct Node));
    assert(node != NULL);

    node->data = "";
    node->next = NULL;
    return node;
}

List *createList(){
    List* list = malloc(sizeof(struct List));
    list->firstNode = NULL;
    assert(list != NULL);
    return list;
}

As an aside, in createList you put your assertion in the wrong place, so it will have no effect: If list is null, you will seg fault before you even reach the assertion. Always check the return value of malloc before attempting to access the pointer it returns. — Tom Karzes
– Tom Karzes, Commented Oct 11, 2017 at 8:09
You are missing the fact that there is no string data type in C. node->data = newValue assigns a pointer, and when you call push(list, s); you are passing the same pointer each time. — n. m. could be an AI
– n. m. could be an AI, Commented Oct 11, 2017 at 8:10
You need to allocate storage for the strings before calling push. In the case of string constants, it's not an issue, but for the string read by scanf, you're using an automatic array s over and over. You can use strdup to allocate storage and copy the strings. — Tom Karzes
– Tom Karzes, Commented Oct 11, 2017 at 8:13

David Schwartz · Accepted Answer · 2017-10-11 08:12:17Z

5

while(scanf("%s", &s) == 1) push(list, s);

Every time you call push you're pushing s into the list. So every entry will contain precisely the same pointer value, which probably is not what you want.

When you go to print, s contains "c". Each node has a pointer to s, so you print the "c" three times, once for each node.

edited Oct 11, 2017 at 8:12

answered Oct 11, 2017 at 8:09

David Schwartz

184k18 gold badges229 silver badges293 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

UnholySheep Over a year ago

Also scanf("%s", &s) should be scanf("%s", s) as s is a char array

ceving Over a year ago

Also never use scanf for anything.

Tony Tannous Over a year ago

@ceving could you please elaborate ?

user694733 Over a year ago

Any answer that deals with scanf and %s, must warn about missing width limit. Otherwise it's as bad as gets.

klutt · Accepted Answer · 2017-10-11 08:58:06Z

The field data in the struct is a pointer, so you need to treat it as such. You're not using it correct. Try something like this:

node->data = strdup(newValue);

Study documentation for strdup so you know exactly how it works.

Also

if(list->firstNode != NULL){
    node->next = list->firstNode;
    list->firstNode = node;
}
else list->firstNode = node;

can be changed to

if(list->firstNode != NULL){
    node->next = list->firstNode;
}
list->firstNode = node;

or even better just

node->next = list->firstNode;
list->firstNode = node;

Another comment is that you should choose if you want to set node->next to NULL in createNode or outside. Don't do both. That just clutters up your code. I would choose to do it in createNode. I would also set node->data to NULL in the same function. It's a pointer and should be treated as such.

Collectives™ on Stack Overflow

Linked list implementation mistake in C

2 Answers 2

4 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related