Different types of memory allocation of structure used for linked list in c

Question

I am writing the program for single-linked-list in 'c' in two ways(They differ in the way memory is being allocated for structure).

1.

struct SingleLinkedList
{
    int data;
    struct SingleLinkedList* next;
};

typedef struct SingleLinkedList sll;

sll* createNode()
{
    sll* node = (sll*) malloc(sizeof(sll));
    node -> next = NULL;
    return node;
}

2.

struct SingleLinkedList
{
    int data;
    struct SingleLinkedList* next;
};

typedef struct SingleLinkedList sll;

sll createNode()
{
    sll node;
    node.next = NULL;
    return node;
}

I want to know is the way second program is written, is correct or not?
If incorrect, why is this so?
If correct, why can I not find a program like this in the internet?

Answer 1

For starters the both functions should be declared with a parameter the value of which is used to initialize the data member data of the created node.

For example the functions can be defined the following way

sll * createNode( int data )
{
    sll *node = malloc( sizeof( sll ) );

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

    return node;
}

and

sll createNode( int data )
{
    sll node = { data, NULL };
    return node;
}

The both code snippets are correct. Whether your program will be incorrect depends on whether you will correctly use the functions.

For example the second function can be used in the following context (appending a new node to the tail of the list):

int append( sll **head, int data )
{
    while ( *head != NULL )
    {
        head = &( *head )->next;
    }

    *head = malloc( sizeof( sll ) );

    if ( *head ) **head = createNode( data );

    return *head != NULL;
}

The only drawback of the second code snippet is that in most cases it is better to combine in one function a node allocation and its initialization in one function instead of splitting these two operations as it is done in the second code snippet.

However sometimes it is make sense to place the initialization itself in a separate function because the initialization can be enough compound. This will make the code in whole more readable.

By the way in C++ this is done exactly in this way due to using constructors. That is it is the constructor (separate function) that is responsible for the initialization.

So you may consider this function

sll createNode( int data )
{
    sll node = { data, NULL };
    return node;
}

as a constructor of an object of the type sll.

So the purposes of the functions from the presented two code snippets are different. The first one dynamically allocates a node. And the second one is used to initialize an already existent node.

Answer 2

Your first program returns a pointer to the (allocated) structure. The caller of createNode now has the responsibility of free()ing its memory before the pointer goes out of scope, and the benefit of the node existing until it is thusly free()d.

Your second program returns a structure, by value, without having "allocated" memory at all. As a matter of fact, the structure node created inside the createNode function ceases to exist as the function returns; the caller of the function gets a copy of that (local) structure. (Although most compilers will optimize that to nothing.)

You don't see the second type too often because:

1) it is really a redundant function call; instead of...

ssl node = createNode();

...just call...

ssl node = { 0, NULL };

2) That node would, again, only exist until the end of the current scope. If you build a linked list like that in function initList(), which e.g. returns a pointer to the first node in that list, as soon as initList() returns all those nodes would go out of scope, and your pointer would point at nothing. Well, not allocated node structures, in any case. ;-) And if you initialize those nodes in a loop, each individual node will go out of scope at the end of its loop iteration... all this is very likely not what you want. ;-)