Home > Blockchain >  Why do we use malloc in linkedlist while inserting a node?
Why do we use malloc in linkedlist while inserting a node?

Time:10-14

void push(struct Node** head_ref, int new_data)
{
    
    struct Node* new_node = (struct Node*) malloc(sizeof(struct Node)); // WHY this?
    new_node->data = new_data;
    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}

CodePudding user response:

It's about lifetime of objects.

The C standard describes this as "storage duration". The 3 most common types are

  1. automatic storage duration

  2. allocated storage duration

  3. static storage duration

The lifetime of objects with automatic storage duration is limited to the block where the object is defined. For instance a variable defined in a function will only exist inside the function. So if you did

void push(struct Node** head_ref, int new_data)
{
    
    struct Node new_node;         // new_node has automatic storage duration
                                  // so it only exist within this function
    new_node.data = new_data;
    new_node.next = (*head_ref);
    (*head_ref) = &new_node;      // Very bad... never do this
}

you would end up in a situation where *head_ref points to a dead object.

So for a linked list, you just can't use a local variable.

The lifetime of objects with allocated storage duration is from malloc (or friends) return and until your code explicit kills the object by calling free. That is exactly what you would want for a linked list. An object where you can control it's lifetime.

Notice: when you do

struct Node* new_node = malloc(sizeof(struct Node));

there are two objects in play. new_node itself is still an object with automatic storage duration (and will only exist inside the function) but it's value (i.e. the value returned by malloc) is a pointer to a node object with allocated storage duration. Therefore you can save the value of new_node in the linked list and have a pointer to an object that still exist when the function returns.

The lifetime of objects with static storage duration is from program start to program end. So such objects can be used for linked lists. You can write a program with a pool of static nodes and whenever you need a new node in the linked list, you can take a node from that pool. It's doable but will require extra code to maintain the pool of available nodes (i.e. kind of implementing your own version of Node-malloc/Node-free). Another downside is that it limits the max length of your list to a fixed number (i.e. to the number of static node objects in the pool at start-up).

So using objects with allocated storage duration is by far the simplest approach. When you need a new node just call malloc. When you are done with a node just call free.

In some special cases you may go for a pool of objects with static storage duration.

  • Related