Link List Generation with malloc()

Question

How is malloc being used in linked list generation? I do not see how it is being used to generate new linked lists, rather than reserve memory for linked lists

Tip: press Ctrl + F and look for "(***)" (without quotes) to find the exact code location

Example 1:

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

struct LinkedList {
    int data;                   /* The data part of the linked list */
    struct LinkedList *next;    /* The pointer part of the linked list */
};  

int main(void) {

    /* Generate the 1st node ("head")  */
    struct LinkedList *head     /* I am not sure what this pointer */  
    head = NULL;                /* is doing to the struct*/
    head = malloc(sizeof(struct LinkedList));   /* Head points to null. Now
                                                 * malloc() is being called  
                                                 * and is assigned to head. 
                                                 * Next line implies head is 
                                                 * already pointing to a 
                                                 * linked list, which means 
                                                 * malloc() is making a new 
                                                 * strucuture (***) */

    /* Generate the second node */
    head -> data = 1; // This implies head is already pointing to a linked list
    head -> next = malloc(sizeof(struct LinkedList));

    /* Generate the third node */
    head -> next -> data = 2;
    head -> next -> next = malloc(sizeof(struct LinkedList));

    /* Generate the fourth node */

    head -> next -> next -> data = 3;
    head -> next -> next -> next = NULL;

    return 0;
}

Example 2:

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

struct LinkedList {
    int data;
    struct LinkedList *next;
}; // notice the semi-colon!


int main(void) {

    struct LinkedList *head = NULL;     /* why is it doing this? */
    struct LinkedList *second = NULL;
    struct LinkedList *third = NULL;

    // Generate the node structure:
    /* how does (struct LinkedList*) affect malloc? (***) */
    head = (struct LinkedList*)malloc(sizeof(struct LinkedList));
    second = (struct LinkedList*)malloc(sizeof(struct LinkedList));
    third = (struct LinkedList*)malloc(sizeof(struct LinkedList));

    // Now fill the first node with info:
    head->data = 1;         /* assign data to the first node */
    head->next = second;    /* Link the first node ("head") with the second 
                             * node ("second") */

    // Now fill the second node with info:
    second->data = 2;       /* assign data to the second node */
    second->next = third;   /* Link the second node to the third node */

    // Now fill the second node with info:
    third->data = 3;        /* assign data to the second node */
    third->next = NULL;     /* Since node 3 is our last node to the link list, 
                             * we give it the value of NULL */

    return 0;
}

The textbook describes a link list as being a chain structure. Malloc() is used for dynamic memory management. However, malloc is being used to declare a new structure in these examples and I do not understand why. I thought it only reserves memory

For example, in example 1, malloc() reserves the space for the structure, but does not "create" it (struct LinkedList var would create a new linked list and store it in var)

For example, in example 2, it looks like malloc() is being affected by (struct LinkedList*) (i.e. (struct LinkedList*)malloc(sizeof(struct LinkedList));), but I am unsure

Answer 1

You can look at linked list like on boxes connected with each other:

 ______        ______        ______
| data |      | data |      | data |
|______|      |______|      |______|
| next |      | next |      | next |
|______|----->|______|----->|______|----->NULL

Where each box is your:

struct LinkedList
{
    int data; /* The data part of the linked list */
    struct LinkedList *next; /* The pointer part of the linked list */

};

The size of your "boxes" (depends on arch) let's take x64 Linux machine is equal to 16 bytes. To create linked list data type you need to store this boxes in memory (stack/heap) and connect them.

As I noticed the size is 16 byte for one "box" and it should be store in memory. For memory managment in userspace you can use malloc(), important thing here there malloc() is not "declare" anything it only allocate part of memory for your one "box" on the heap and you ask for exactly 16 bytes for your "box" using sizeof() operator.

struct LinkedList *head = malloc(sizeof(struct LinkedList));

It allocate memory for your "box" and now it look like this:

 ______ 
| data |
|______|
| next |
|______|----->NULL

When you do this:

head->next = malloc(sizeof(struct LinkedList));

Your allocate memory for another "box" and connect them:

 ______        ______  
| data |      | data |      
|______|      |______|      
| next |      | next |      
|______|----->|______|

When you do this one:

struct LinkedList *head = malloc(sizeof(struct LinkedList));     
struct LinkedList *second = malloc(sizeof(struct LinkedList));
struct LinkedList *third = malloc(sizeof(struct LinkedList));

You create three "boxes" somewhere in memory 16 bytes each. And they not connected for now, they only located in memory;

   head         second      third
  ______        ______      _____
 | data |      | data |    | data |
 |______|      |______|    |______|   
 | next |      | next |    | next |
 |______|      |______|    |______|

And you connected them doing this one:

head->next = second;
second->next = third;
third->next = NULL;

 head          second        third
 ______        ______        ______
| data |      | data |      | data |
|______|      |______|      |______|
| next |      | next |      | next |
|______|----->|______|----->|______|----->NULL

Usually second approach used in function like for ex add_node_front()

void add_node_front(struct LinkedList **head_ref, int data) 
{ 
    /* 1. allocate node */
    struct LinkedList *new_node = malloc(sizeof(struct LinkedList)); 

    /* 2. put in the data  */
    new_node->a  = data; 

    /* 3. Make next of new node as head */
    new_node->next = (*head_ref); 

    /* 4. move the head to point to the new node */
    (*head_ref)    = new_node; 
} 

Answer 2

In the second example you also could allocate the memory statically:

struct LinkedList head;
struct LinkedList second;
struct LinkedList third;

Then you need to access with the dot-operator:

head.data = 1; //assign data to the first node
head.next = &second;

You could also use an array

struct LinkedList nodes[3];
node[0].data = 1;
node[0].next = &node[1];

and so on.

So, the malloc command is not essential to the concept of linked list. But for many applications you do not know before, how big your linked list will be. And elements and the order will change during runtime. So, in this case the dynamic memory allocation with malloc/free is really helpful.

Answer 3

How is malloc being used in linked list generation?

malloc is used for allocating memory dynamically. When you are creating linked list, you can use malloc for allocating memory for the nodes of the list. Read more about malloc here.

From Example 1:

head = malloc(sizeof(struct LinkedList));

From Example 2:

head = (struct LinkedList*)malloc(sizeof(struct LinkedList));

The only difference is, in Example 2, you are explicitly casting the malloc result. The malloc return type is void * and void * can be cast to the desired type, but there is no need to do so as it will be automatically converted. So the cast is not necessary. In fact, its not desirable to cast malloc return. Check this.

Your both the examples are functionally same except the memory allocation sequence. In Example 1, you are allocating memory to head pointer and then to head -> next pointer and then to head -> next -> next pointer.

In Example 2, you are allocating memory to head, second and third pointer and later assigning second to head -> next and third to head -> next -> next.

---

Additional:

Always check the malloc return, like this:

head = malloc(sizeof(struct LinkedList));
if (NULL == head) {
    fprintf (stderr, "Failed to allocate memory");
    exit(EXIT_FAILURE);
}

Also, make sure to free the dynamically allocated memory once you are done with it. Follow good programming practice.