C linked list circular reference

Question

So I'm pretty new to C, but not to programming. I am trying to learn C and so I decided to try implementing a simple linked list.

Here is the code:

#include <stdio.h>

typedef struct node node;
struct node {
    char *word;
    node *next;
};

// Returns a node.
node node_new(char *word) {
    node n;
    n.word = word;
    n.next = NULL;
    return n;
}

// Traverses the linked list, spitting out the
// words onto the console.
void traverse(node *head) {
    node *cur = head;

    while (cur != NULL) {
        printf("I have %s.\n", cur->word);
        cur = cur->next;
    }

    printf("Done.\n");

    return;
}

// In here I get circular references whenever I pass a second argument.
void dynamic(int argc, char **argv) {
    printf("DYNAMIC:\n");

    node n = node_new("ROOT");
    node *cur = &n;

    int i;
    for (i = 0; i < argc; i++) {
        node next = node_new(argv[i]);
        cur->next = &next;
        cur = &next;
    }

    traverse(&n);
}

void predefined(void) {
    printf("PREDEFINED:\n");

    node n = node_new("ROOT");
    node a = node_new("A");
    node b = node_new("B");
    node c = node_new("C");

    n.next = &a;
    a.next = &b;
    b.next = &c;

    traverse(&n);
}

int main(int argc, char **argv) {
    predefined();
    dynamic(argc, argv);
    return 0;
}

If I just run it without arguments ("./test") the output is:

PREDEFINED:
I have ROOT.
I have A.
I have B.
I have C.
Done.
DYNAMIC:
I have ROOT.
I have ./test.
Done.

but if I put any arguments on, instead of "I have ./test." it gives an infinite loop of whatever the last argument on the command line was ("./test one two three" gives "i have three." over and over ignores the "one" and "two", but the preceding lines are the same).

I think it has to do with bad pointer management in the dynamic function, but I can't figure out why it's setting itself to its own "next" node.

Answer 1

The problem is here:

for (i = 0; i < argc; i++) {
    node next = node_new(argv[i]);
    cur->next = &next;
    cur = &next;
}

By allocating next like this, it remains tied to the stack and doesn't actually change address on each iteration. It should be a new object each time:

for (i = 0; i < argc; i++) {
    node *next = malloc (sizeof node);
    next->word = argv[i];
    next->next = NULL;
    cur->next = next;
    cur = next;
}

Also, node_new() can't be used because it doesn't allocate any lasting new memory either.

Answer 2

The problem is in your for loop. Every iteration uses the same memory location on the stack to store the next variable. So, effectively, the memory location given by &next is a constant for your entire for loop, and by the time you run traverse, that memory location contains last value of next.

Your for loop is equivalent to this version, which might shed more light:

int i;
node next;  // note this line
for (i = 0; i < argc; i++) {
    next = node_new(argv[i]);
    cur->next = &next;
    cur = &next;
}

You'll need to create new nodes on the heap, if you want to be able to pass their addresses around, or store their addresses in other data structures. Read up on malloc and free.