Allocation de mémoire dynamique pour le nœud dans la liste liée

Question

Pourquoi quand je dois déclarer un pointeur vers un nœud (tête), je dois aussi allouer de la mémoire avec mallocou callocpour lui? J'ai vu que le code qui génère une liste (non importée ici) fonctionne bien aussi sans allouer de mémoire pour cela et juste déclarer node *head.

typedef struct str_node{
    int data;
    struct str_node *next;
}node;

int main(){

    node *head;

    head = (node*) malloc(sizeof(node));
    head = NULL;

Et pourquoi quand j'alloue de la mémoire comme ci-dessus, je dois écrire (node*)? N'est-il pas déjà alloué à un nœud struct depuis que je le fais sur la tête? Quelle est la signification de cette ligne de code exactement? De plus, lorsque j'écris, head = NULLsuis-je défini l'adresse de la tête du pointeur sur NULL ou quoi?

Answer 1

Cet extrait de code

node *head;

head = (node*) malloc(sizeof(node));
head = NULL;

produit une fuite de mémoire.

Au début, une mémoire pour un objet du type a nodeété allouée et son adresse a été attribuée au pointeurhead

head = (node*) malloc(sizeof(node));

puis aussitôt la valeur du pointeur a été écrasée.

head = NULL;

En conséquence, l'adresse de la mémoire allouée a été perdue et la mémoire allouée ne peut pas être libérée.

L'extrait de code n'a aucun sens. Il suffira d'écrire

node *head = NULL;

Dans ce cas, vous aurez initialement une liste vide.

Et pourquoi quand j'alloue de la mémoire comme ci-dessus, je dois écrire (node ​​*)?

La fonction mallocrenvoie un pointeur du type void *. Un pointeur du type void *peut être affecté à un pointeur de tout autre type d'objet. Donc en C le casting est redondant.

En C ++, vous devez convertir explicitement un pointeur du type void *vers le type du pointeur d'objet auquel le pointeur du type void *est affecté.

De plus, lorsque j'écris head = NULL, je mets l'adresse de la tête du pointeur sur NULL ou quoi?

Vous n'avez pas défini l'adresse du pointeur lui-même. Le pointeur a été alloué par le compilateur et a la durée de stockage automatique. Vous définissez la valeur de la variable de headtype node *NULL.

Answer 2

En C, les pointeurs sont des valeurs, tout comme les entiers. Lorsque vous écrivez:

int a;
a = 3;

vous stockez la valeur 3 dans la variable a.

Lorsque vous écrivez:

int* p;
p = NULL;

vous stockez la valeur NULLdans la variable p. Les pointeurs n'ont rien de spécial. L'affectation ne dépend en aucun cas de la valeur de p, c'est-à-dire de ce qu'elle pourrait ou non pointer. (Dans ce cas, cela ne pointe vers rien, mais ce n'est pas pertinent.)

mallocrenvoie un pointeur vers une région mémoire, qui, comme indiqué ci-dessus, est une valeur. Le pointeur n'a pas de métadonnées intrinsèques; mallocne nécessite aucune information au-delà de la taille de la région mémoire. En particulier, il ne sait pas (ou ne se soucie pas) à quoi la région mémoire sera utilisée. Une fois cette valeur produite, vous pouvez la gérer comme bon vous semble, par exemple:

int* p;
p = malloc(sizeof *p);

Puisque pest déclaré comme un pointeur vers an int, il est attendu que la mémoire pointée par ppuisse contenir un int. (Ce n'est pas encore le cas, mais c'est possible.) Mais vous pouvez passer le pointeur (en tant que valeur) sans que cela n'ait d'effet sur l'entier (le cas échéant) stocké dans la mémoire pointé. Par exemple, après

int* q = p;

qet ppointez sur le même souvenir.

Si vous trouvez quelque chose de déroutant, c'est probablement parce que vous vous attendez à ce qu'un pointeur soit autre chose qu'une simple valeur. Cependant, ce sont des valeurs simples et vous avez besoin d'un modèle mental basé sur cette simple réalité.