Est-ce que je me suis trompé en essayant d'insérer un nouveau nœud au milieu d'une liste doublement chaînée?

Question

Structure ressemblait: Maintenant, j'ai

class DList{ 
private: 
     struct Elem { 
     Elem *prev, *next; 
     }; 
     Elem *_head, *_tail; 
} 

deux nœud existant: CUR et Cur-> prochaine et je veux insérer une nouvelle ins de noeuds entre eux. Voici ce que j'ai fait:

cur->next = ins;//step-1-1 cur 
    ins->prev = cur;//step-1-2 cur 

    ins->next = cur->next;//step-2-1 cur->next 
    cur->next->prev = ins;//step-2-2 cur->next 

Le problème est dans la boucle de traverse supplémentaire de mon programme mon pointeur ne peut plus atteindre _tail. Ai-je mal quelque chose dans ma partie insertion? (La boucle fonctionne parfaitement une fois que je commente l'insertion aux codes du milieu ci-dessus)

Answer 1

Eh oui, il y a une mauvaise connexion ici. Dessinez des images!

Imaginer les choses ressembler à ceci, d'abord:

   curr 
       | 
       v 
     +----------+       +----------+ 
     | next | ----------------------> | next | --> ... 
     +----------+       +----------+ 
... <-- | prev | <---------------------- | prev | <-- ... 
     +----------+       +----------+ 
          +----------+ 
          | next | 
          +----------+ 
          | prev | 
          +----------+ 
           ^
           | 
           ins 

Tout d'abord, vous exécutez cur->next = ins;, qui fait cela:

   curr 
       | 
       v 
     +----------+       +----------+ 
     | next | -----------+   | next | --> ... 
     +----------+   |   +----------+ 
... <-- | prev | <----------+----------- | prev | <-- ... 
     +----------+   v   +----------+ 
          +----------+ 
          | next | 
          +----------+ 
          | prev | 
          +----------+ 
           ^
           | 
           ins 

Notez que nous n'avons plus un pointeur sur l'élément qui était à l'origine après curr - oups! Ce sera un problème plus tard.

Maintenant, nous faisons ins->prev = curr;, qui ressemble à ceci:

   curr 
       | 
       v 
     +----------+       +----------+ 
     | next | -----------+   | next | --> ... 
     +----------+   |   +----------+ 
... <-- | prev | <----------+----------- | prev | <-- ... 
     +----------+   v   +----------+ 
      ^   +----------+ 
       |   | next | 
       |   +----------+ 
       +---------- | prev | 
          +----------+ 
           ^
           | 
           ins 

Maintenant, nous écrivons ins->next = curr->next;. Mais oups! Notez que curr->next points ins, donc nous venons d'ajouter un cycle ici:

   curr 
       | 
       v 
     +----------+       +----------+ 
     | next | -----------+   | next | --> ... 
     +----------+   |   +----------+ 
... <-- | prev | <----------+----------- | prev | <-- ... 
     +----------+   v   +----------+ 
      ^   +----------+ 
       |   | next | --+ 
       |   +----------+ | 
       +---------- | prev | <-+ 
          +----------+ 
           ^
           | 
           ins 

Et enfin, vous écrivez cur->next->prev = ins; Mais oups!curr->next est encore prev, donc nous obtenons un autre cycle:

   curr 
       | 
       v 
     +----------+       +----------+ 
     | next | -----------+   | next | --> ... 
     +----------+   |   +----------+ 
... <-- | prev | <----------+----------- | prev | <-- ... 
     +----------+   v   +----------+ 
          +----------+ 
         +-> | next | --+ 
         | +----------+ | 
         +-- | prev | <-+ 
          +----------+ 
           ^
           | 
           ins 

Le problème ici est que vous perdez la trace de la cellule pointée par curr->next après la première affectation, de sorte que vous perdez la possibilité de regarder au bon endroit.

Et si vous démarrez en écrivant quelque chose comme ça?

DList* next = curr->next; 

puis utilisez next au lieu de curr->next dans certains de ces contextes?

Answer 2

La clé est de ne pas perdre les valeurs qui vont être utilisées plus tard. Votre première ligne de code cur->next = ins; vous fait perdre la valeur d'origine (cur->next); par la suite, vous ne savez vraiment pas qui sera next à ins.

Utilisez cette logique pour insérer un nouveau nœud au milieu. Disons d'abord,

cur - cur->next 
    | 
    [ins] 

Do,

ins->next = cur->next; 

(roquet) (ins) - (Cur-> suivante) {Assume - pour la prochaine, et pour = next et prev}

cur->next = ins; 

(roquet) - (ins) - (Cur-> suivante)

ins->prev = cur; 

CUR = ins - (Cur-> suivant)

ins->next->prev = ins; 

= ins = cabot (Cur-> suivante)