liste chaînée ajoutant à la queue, confusion

Visual Studio 2008 C

Ce que je ne comprends pas à propos de cette liste chaînée, c’est l’ajout à la queue dans l’autre partie de l’instruction if.

Lorsque la tête et la queue sont assignées, l’adresse de la mémoire de node_temp à la fois la queue et la tête désignent le même emplacement mémoire.

Cependant, dans la partie restante, la tête pointe en fait toujours vers la queue. Il y a juste quelque chose que je ne peux pas expliquer et que je ne comprends pas à propos du rest?

J’espère que quelqu’un pourra mieux expliquer pour moi.

static struct convert_temp { size_t cel; size_t fah; struct convert_temp *next; } *head = NULL, *tail = NULL; /** Add the new converted temperatures on the list */ void add(size_t cel, size_t fah) { struct convert_temp *node_temp = NULL; /* contain temp data */ node_temp = malloc(sizeof(*node_temp)); if(node_temp == NULL) { fprintf(stderr, "Cannot allocate memory [ %s ] : [ %d ]\n", __FUNCTION__, __LINE__); exit(0); } /* Assign data */ node_temp->cel = cel; node_temp->fah = fah; node_temp->next = NULL; if(head == NULL) { /* The list is at the beginning */ head = node_temp; /* Head is the first node = same node */ tail = node_temp; /* Tail is also the last node = same node */ } else { /* Append to the tail */ tail->next = node_temp; /* Point the tail at the end */ tail = node_temp; } } 

La première fois que vous ajoutez un élément (appelons-le A ) à la liste, la head est nulle et vous passez par la partie if . Cela signifie que la head et la queue sont définies pour pointer sur A lors de l’ajout de ce premier élément.

Ajoutons maintenant un autre élément B Cette fois, la head n’est pas nulle, elle passe donc par la partie else et se met à pointer vers B mais la head pointe sur A

C’est comme prévu, vous avez maintenant la head pointant vers A , A pointant vers B , B pointant vers rien (null) et la tail pointant vers B

Allons-y pas à pas.

 Initial state: head -+-> null | tail -+ Insert item A: head -+-> A ---> null | tail -+ Insert item B: head ---> A -+-> B ---> null | tail --------+ Insert item C: head ---> A ---> B -+-> C ---> null | tail ---------------+ 

Vous pouvez voir à chaque étape (autre que l’initiale) que la queue actuelle est définie pour pointer vers le nouveau nœud (qui pointe déjà sur NULL pour son nœud suivant), puis le pointeur de queue est mis à jour pour pointer vers le nouveau dernier nœud.

En fait, passons à l’ajout de C de manière encore plus détaillée (ligne par ligne) pour que vous puissiez voir ce que fait chaque ligne de code (j’ai renommé node_temp en node simplement pour aider à la mise en forme):

 Starting state: head ---> A -+-> B ---> null | tail --------+ node = malloc(sizeof(*node)); node ---> C ----------> ? (allocate node C) head ---> A -+-> B ---> null | tail --------+ node->next = NULL; node ---> C --------+ (ignore payload cel/fah | for now since it's not head ---> A -+-> B -+-> null relevant to the list | structure) tail --------+ tail->next = node; node ---------------+ (first in else clause) | head ---> A -+-> B -+-> C ---> null | tail --------+ tail = node; node ---------------+ (second in else clause) | head ---> A ---> B -+-> C ---> null | tail ---------------+ 

Puis finalement, le node disparaît puisqu’il s’agit d’une variable locale et que vous avez votre état final:

  head ---> A ---> B -+-> C ---> NULL | tail ---------------+ 

L’avantage de conserver un pointeur de tail dans une liste à lien unique est d’éviter de devoir parcourir toute la liste pour trouver la fin lorsque vous essayez d’append un élément à la fin.

En parcourant toute la liste, l’insertion à la fin est une opération O(n) time (le temps pris dépend du nombre d’éléments de la liste). L’utilisation du pointeur tail fait qu’une opération de temps O(1) (même temps quelle que soit la taille de la liste).

De plus, une liste doublement chaînée a une utilité supplémentaire pour un pointeur de tail – elle permet de commencer rapidement un parcours de bout en bout, de la fin au début de la liste, en utilisant la tail et les pointeurs prev au lieu de la head et les next .

La partie else met simplement à jour la tail de la liste, car l’en-tête ne change pas lorsque vous ajoutez une liste liée.

Il s’agit d’une optimisation consistant à conserver un pointeur sur l’élément queue mis en mémoire tampon afin que vous n’ayez pas à parcourir la liste complète à partir de l’en-tête de chaque annexe.

Ce n’est pas que la tête pointe toujours vers la queue. La tête pointe vers l’ ancienne queue. Lorsque la liste ne contenait qu’un seul élément, il s’agissait à la fois de la tête et de la queue. Lorsque le nouveau noeud a été ajouté, le pointeur arrière a été mis à jour. Le pointeur principal pointe toujours sur le premier noeud, ce qui est correct.

Au premier appel, add, head et tail désignera un bloc de mémoire nouvellement créé. Tous les appels à append suivants tomberont dans la partie else, ce qui ne changera que le pointeur de queue, en modifiant fondamentalement l’ancienne queue-> suivant pour pointer vers le nouveau bloc de mémoire, puis mettre à jour la queue pour pointer également vers ce nouveau bloc de mémoire. .

C’est un moyen efficace d’append. Si seul head était utilisé, chaque fois que vous ajoutez un nouveau node_temp, vous devez parcourir tous les pointeurs suivants en commençant par head jusqu’à atteindre le node_temp ajouté précédemment (dont le pointeur suivant serait NULL), puis append le nouveau nœud. . Ce serait alors un algorithme O (n), plutôt que le O (1) ci-dessus.