Insert node in a linkedlist

Question

I'm new to C and I'm stuck with the insert function in a linked list. When I try printing the list. The result isn't what I expect. I know it has something to do with pointers but I just can't get my head around it. What am I doing wrong here?

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>

typedef struct CELL_NODE CellNode;
struct CELL_NODE {
    int row;
    int column;
    CellNode *next;
};

struct LinkedList {
    CellNode *head;
};
typedef struct LinkedList LinkedList;

void printList(LinkedList *myList) {
    CellNode *curr = (*myList).head;
    if (curr != NULL) {
        printf("(%d,%d)", (*curr).row, (*curr).column); 
        if ((*curr).next != NULL) {
            curr = (*curr).next;
            printf(" - (%d,%d)", (*curr).row, (*curr).column);
        }
    } else {
        printf("The list is empty");
    }
    printf("\n");
}

void insert(LinkedList *myList, CellNode *node) {
    CellNode *ref = (*myList).head;
    if (ref == NULL) {
        (*myList).head = node;
    } else {
        while ((*ref).next != NULL) {
            ref = (*ref).next;
        }
        (*ref).next = node;
    }
}

int main(int argc, char *argv[]) {
    LinkedList myList = { NULL };
    for (int k = 0; k < 2; k++) {
        CellNode myNode = { 1, k, NULL };
        insert(&myList, &myNode);
        printList(&myList);
        printf("\n");
    }
    return 1;
}

The result I get is:

(1,0)
(1,1) - (1,1)

I'm expecting:

(1,0)
(1,0) - (1,1)

Answer 1

You repeatedly insert a node into the linked list from a local variable that immediately goes out of scope. The behavior is undefined, your program might fail in many unpredictable ways.

You should modify the code this way:

• change the insert function to take the element data as arguments and allocate a new node with malloc().
• make printList() print the full list, not just the first couple of cells.
• change the clumsy (*pointer).member notation into the equivalent but more idiomatic pointer->member notation.
• return 0 from main for successful operation.

Here is a modified version:

#include <stdio.h>
#include <stdlib.h>

typedef struct CellNode CellNode;
struct CellNode {
    int row;
    int column;
    CellNode *next;
};

typedef struct LinkedList LinkedList;
struct LinkedList {
    CellNode *head;
};

void printList(LinkedList *myList) {
    CellNode *curr = myList->head;
    if (curr != NULL) {
        printf("(%d,%d)", curr->row, curr->column); 
        while (curr->next != NULL) {
            curr = curr->next;
            printf(" - (%d,%d)", curr->row, curr->column);
        }
    } else {
        printf("The list is empty");
    }
    printf("\n");
}

CellNode *insert(LinkedList *myList, int row, int column) {
    CellNode *node = malloc(sizeof(*node));
    CellNode *ref = myList->head;

    if (node != NULL) {
        if (ref == NULL) {
            myList->head = node;
        } else {
            while (ref->next != NULL) {
                ref = ref->next;
            }
            ref->next = node;
        }
    }
    return node;  // return node pointer to allow the caller to detect out of memory error
}

int main(int argc, char *argv[]) {
    LinkedList myList = { NULL };
    CellNode *node;

    for (int k = 0; k < 2; k++) {
        insert(&myList, 1, k);
        printList(&myList);
        printf("\n");
    }
    // free the nodes
    while ((node = myList->head) != NULL) {
        myList->head = node->next;
        free(node);
    }
    return 0;
}

Answer 2

With

 CellNode myNode = {1,k,NULL};
 insert(&myList,&myNode);

you are passing a pointer to a local variable. The life time of this variable is just as long as the respective iteration of the loop, i.e. in the second iteration, the object of the first iteration is out of scope. So you will access an object which's life time has already ended by the pointer you stored in your list. This yields undefined behaviour.

Use dynamically generated objects instead (and don't forget to free them later on):

CellNode *myNode = malloc(sizeof(CellNode));
myNode->row = ...

Answer 3

You should first change every instance of (*x).y to x->y to make your code much more readable.

Then, look at this code:

int main(int argc, char *argv[])
{
    LinkedList myList = {NULL};
    for(int k = 0 ; k<2 ; k++) {
        CellNode myNode = {1,k,NULL};
        insert(&myList,&myNode);
        printList(&myList);
        printf("\n");
    }
    return 1;
}

You create myNode as a local variable inside the for loop. That means that each iteration of the loop gets a new instance of myNode, destroying the previous one. So you've connected myNode to your linked list through pointers, and then you let it get destroyed the next time through the for loop.

If you're going to let some piece of code stash a pointer to something, you must ensure that something remains valid until there is no longer any possibility of those pointers being dereferenced.

You need to make a decision -- what will own the objects that the linked list contains pointers to? When will that lifetime end? And when they end, what will destroy them?

You haven't done this. So you have objects whose lifetimes end too early.