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
automatic storage duration
allocated storage duration
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.