Discussion :

[bipbip2006]

Je recherche l'algorithme pour concatener 2 listes chainées en 1.
Je ne sais pas par où commencer car je ne suis pas très bon en algo, et un petit coup de pousse me serait bien utile.
Merci d'avance

[Jedai]

Il y a deux algorithmes légèrement différents selon que tu veux conserver l'accès aux deux listes chaînées originale ou juste à la version concaténée (et la liste chaînée concaténée à la fin, puisque cela ne coûte rien). Lequel veux-tu ?

--
Jedaï

[bipbip2006]

Le second s'il te plait, j'ai cherché bien evidement sur le net jusqu'à présent mais je n'ai rien trouvé de fameu, c'est pour cela que je viens poser ma question ici, merci pour ta réponse aussi rapide

[Jedai]

Pour concaténer L2 à la fin de L1, il suffit de faire pointer le dernier noeud de L1 vers le premier noeud de L2. Selon ta structure de donnée, ça peut même être fait en O(1).

--
Jedaï

[bipbip2006]

C'est justement la où je coince...
Si par exemple j'ai une liste chainée dont le deuxieme donc pointe vers le premier, comment faire (d'un point de vue algo) pour dire plutot que de pointe vers le premier élément, pointe sur celui la.
J'ai besoin d'un petit coup de pouce, les pointeurs ne sont pas ma tasse de thé...

[ToTo13]

Bonjour,

si tu as deux listes, A(a1->a2->...->aN->NULL) et B(b1->b2->...->bM->NULL) :
- parcourir A jusqu'à son dernier élément (tant que a->suivant != NULL)
- on fait alors pointé le dernier élément de A vers le premier de B. a->suivant = b1

[Alikendarfen]

Souvent, il est utile (pratique, efficace), de maintenir le premier et le dernier élément d'une liste chainée.

Dans l'exemple de Toto13, on aurait :

A(a1->a2->...->aN->NULL , aN)
et
B(b1->b2->...->bM->NULL, bM)

Ce qui évite de faire une boucle pour retrouver le dernier élément (l'opération de récupération du dernier est alors en O(1), au prix du maintient du pointeur sur les opérations d'ajout et de suppression dans la liste).

Il faut aussi que tu prennes en compte le fait que ta première liste puisse être vide.

Ca donne :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
Si A est vide
   A.Premier = B.Premier
   A.Dernier = B.Dernier
Sinon
   A.Dernier.Suivant = B.Premier
   A.Dernier = B.Dernier

Mais attention : comme les deux listes sont maintenant 'mélangées', modifier l'une va modifier l'autre, ce qui peut compliquer les choses sur la façon d'écrire tes opérations générales sur ces listes. Par exemple, on ne peut plus assurer que A.Dernier ait 'null' comme suivant dès qu'on ajoute un élément à la fin de B.
De même, si après avoir mis B à la fin de A, on ajoute un élément à B, le résultat pour A ne sera pas le même, selon que B était vide au départ ou non...

Bref, mélanger les listes peut conduire à des effets de bord difficiles à gérer.

[bipbip2006]

Ok, merci beaucoup, j'ai compris maintenant

[schwuleur]

Mais attention : comme les deux listes sont maintenant 'mélangées', modifier l'une va modifier l'autre, ce qui peut compliquer les choses sur la façon d'écrire tes opérations générales sur ces listes. Par exemple, on ne peut plus assurer que A.Dernier ait 'null' comme suivant dès qu'on ajoute un élément à la fin de B.
De même, si après avoir mis B à la fin de A, on ajoute un élément à B, le résultat pour A ne sera pas le même, selon que B était vide au départ ou non...

Bref, mélanger les listes peut conduire à des effets de bord difficiles à gérer.

Je rebondis sur cette (vieille) conversation. J'ai exactement ce problème d'effet de bord. Y a -t-il une solution pr éviter ce genre de problème?

[Alikendarfen]

Effectivement, ça date un peu !

En fait, ça correspond à ce que disait Jedai, au début (conserver l'accès aux deux listes originales ou pas).

Pour éviter ces mélanges, pour par exemple mettre B à la suite de A, il est nécessaire de créer de nouveaux noeuds à la fin de A (autant de noeuds qu'il y en a dans B) et de reporter les valeurs des noeuds de B dans ces noeuds qu'on vient de créer.

Quelque chose du genre :

Pour chaque noeud b de B

Créer un nouveau neud n

Affecter la valeur de b à celle de n

Ajouter n à la fin de A