Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Linked list implementation mistake in C

Tags:

c

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;
}
like image 954
Eugene Mamaev Avatar asked Jan 30 '23 10:01

Eugene Mamaev


2 Answers

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.

like image 128
David Schwartz Avatar answered Feb 08 '23 19:02

David Schwartz


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.

like image 36
klutt Avatar answered Feb 08 '23 20:02

klutt