Allocating memory for new element in linked list in C

Question

Hi, I'm trying to create a linked list, I've got it working, but I'm still a little confused. I'm using the following struct:

typedef struct _MList
{
    int dx;
    int dy;
    struct _MList *next;
} MList_t, *MList_p;

I've tested that this structure makes sense, and I've got a function to print out a list:

void mListPrint(MList_t *mList)
{
    MList_p node = mList;
    while (node->next != NULL)
    {
        printf("[%i,%i] ",node->dx,node->dy);
        node = node->next;
    }
    printf("[%i,%i]\n",node->dx,node->dy);
}

And a function to create the first node:

MList_t mListNew(int dx, int dy)
{
    MList_t newNode;
    newNode.dx = dx;
    newNode.dy = dy;
    newNode.next = NULL;    
    return newNode;
}

With this working fine I thought I'd try and make a function which adds a node at the end of the list. My first attempt was this:

void mListAdd(int dx, int dy, MList_t *mList)
{
    MList_p node = mList;

    while (node->next != NULL)
    {
        node = node->next;  
    }

    MList_t newNode = mListNew(dx,dy);
    node->next = &newNode;
}

This was looking good, until I added more than one element. After much debugging it turned out that the memory address of a "newNode" created in mListAdd was always the same. And so the list ended up linking back onto itself. Why is this?

I instead implemented mListAdd by using a pointer to a new node, as follows:

void mListAdd(int dx, int dy, MList_t *mList)
{
    MList_p node = mList;

    while (node->next != NULL)
    {
        node = node->next;
    }
    MList_p newNode = malloc(sizeof(MList_t));
    *newNode = mListNew(dx,dy);
    mListPrint(newNode);
    node->next = newNode;
}

This works perfectly, but I feel the other way should work too. Or am I missing something obvious? I'm trying to learn C for an interview by implementing different data structures I learnt in Java and ML.

I'm sorry about the amount of code, but I thought it was best to explain my question as thoroughly as possible. Thank you for you help in advance!

Answer 1

You have to explicitely allocate memory using malloc() or calloc(). What you do is to use the struct that only lives on the stack, and isn't really alive any more after mListAdd returns; it just happens that it hasn't been overwritten yet.

Answer 2

The first example allocates memory on the stack, so it is only usable while inside the function, hence you SHOULD NOT use its memory address in a linked list that may survive outside the function.

Answer 3

In mListNew you are using a local variable:

MList_t newNode;

This goes out of scope as soon as you return from the function. So you are on undefined territory. The code looks as if it's working only because the memory manager does not overwrite the memory block occupied by that local variable.

You should allocate the new list node with malloc inside mListNew and return the pointer to the new node, like this:

MList_p mListNew(int dx, int dy)
{
    MList_p newNode = malloc(sizeof(MList_t));
    newNode->dx = dx;
    newNode->dy = dy;
    newNode->next = NULL;    
    return newNode;
}

Answer 4

Sorry, I am sure that there is more, but I didn't read beyond "And a function to create the first node"

MList_t mListNew(int dx, int dy)
{
    MList_t newNode;
    newNode.dx = dx;
    newNode.dy = dy;
    newNode.next = NULL;    
    return newNode;
}

newNode is created on the stack. It's definition is local to the function mListNew() and when that returns it is "undefined".

Best practise says that you require your caller to allocate (and free) the memory before calling. E.g,

void mListNew(int dx, int dy, MList_t *newNode)
{
    newNode->dx = dx;
    newNode->dy = dy;
    newNode->next = NULL;    
}

I haven't looked at the rest of it yet...