Discussion :

[schwuleur]

Bonjour,

Je dois réaliser la fusion de deux listes chaînées. J'ai une contrainte qui m'impose de réaliser la fusion en temps constant.

J'ai donc implémenté ma liste chainée qui possède deux références :
- une sur mon maillon de tête (front)
- une sur ma maillon de fin (tail)

Mes données contenues dans mes maillons possède un objet et lien vers le maillon suivant (next).

Pour fusionner une liste (list2) à une autre (list1), je fais

Code :

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

1
2
3
 
list1.tail.setNext(list2.front);
list1.tail = list2.tail

La fusion se passe correctement en temps constant.
Mon problème vient du fait que je dois par la suite modifier ma deuxième liste. Cela engendre des changements dans ma première liste que je ne souhaite pas.
J'aimerais spécifier que le list1.tail.next est différent du list2.tail.next mais je ne trouve pas de solution.

Qqn aurait-il une idée?
Si je n'ai pas été clair, faites le savoir!

merci d avance!

[Ivelios]

Soit tu modifies la seconde liste avant de la fusionner avec la première.
Soit tu stockes list2.front quelque part. Et pour la modification, tu commences à list2.front puis tu fais des next().

Il n'y a pas d'autres solutions.

[schwuleur]

Je ne comprends pas vraiment ta réponse!
Justement mon but est d'éviter que les changements apportés sur la deuxieme liste ne se repercute sur la première.

Soit tu modifies la seconde liste avant de la fusionner avec la première.

En faitsant comme ça, vu que les changements sont déjà apportés à la deuxième liste, d'office les éléments apportés seront dans ma première liste.

Soit tu stockes list2.front quelque part. Et pour la modification, tu commences à list2.front puis tu fais des next().

Et si je parcours la list2 à partir de list2.front en faisant des next(), ca fait exactement ce que je ne souhaite pas!?
Donc je ne comprends pas très bien le but de faire ca!

Merci d'avoir lu ma question

[Ivelios]

Je pense comprendre pourquoi je n'ai pas compris.
Pour toi la première liste est aussi la liste fusionné.

Bref, si je comprend bien :
1/ Soit une liste L1
2/ Soit une liste L2
3/ Soit une liste L3 = L1|L2 ( où | = fusion )

Problème, quand tu modifie L2, L3 est aussi modifié.

Si c'est bien ça c'est normal. L3 et L2 possèdent des références vers les mêmes objets. Donc quand tu modifie dans un, ça modifie forcément dans l'autre.
Solution : Créer une L2bis, qui est la copie exact de L2. Et c'est L2bis que tu fusionne avec L1 (L1|L2bis = L3)
Pour créer une copier, tu parcours ta liste(L2) et tu en crée une autre(L2bis) en même temps en la remplissant.

[Rei Ichido]

Je ne vois pas de solution qui puisse être en temps constant et qui remplisse tes deux conditions, car de ce que je comprend tu souhaites pouvoir cloner tes objets ... ce qui nécessite forcément de la parcourir (donc, temps linéaire).

[Logan Mauzaize]

Je ne vois pas de solution qui puisse être en temps constant et qui remplisse tes deux conditions, car de ce que je comprend tu souhaites pouvoir cloner tes objets ... ce qui nécessite forcément de la parcourir (donc, temps linéaire).

Je proposes un "lenient-cloning"
+1

A la rigueur on peut "limiter" l'impact linéaire sur une liste non chaînée avec System.arraycopy.