Liste doublement chainée

Fermé
stampia02
Messages postés
95
Date d'inscription
samedi 30 juillet 2011
Statut
Membre
Dernière intervention
13 mai 2017
- 14 mars 2017 à 17:52
stampia02
Messages postés
95
Date d'inscription
samedi 30 juillet 2011
Statut
Membre
Dernière intervention
13 mai 2017
- 19 mars 2017 à 17:29
Bonjour,

Je dois implémenter une liste doublement chainée, y a t'il des exemples fiable + des explications sur les pointeurs etc?

Je ne sais pas très bien par ou commencer

Merci

2 réponses

KX
Messages postés
16526
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
18 mai 2022
2 954
Modifié par KX le 14/03/2017 à 19:25
Bonjour,

"des explications sur les pointeurs"
Il n'y a pas de pointeurs en Java...

"y a t'il des exemples fiable"
Voici une structure de liste qui devrait fonctionner :

public class ListeDoublementChainee<E> {
    private Chaine<E> premiere, derniere;

    private class Chaine<E> {
        private E element;
        private Chaine<E> precedente, suivante;
    }
}

La confiance n'exclut pas le contrôle
0
stampia02
Messages postés
95
Date d'inscription
samedi 30 juillet 2011
Statut
Membre
Dernière intervention
13 mai 2017
1
15 mars 2017 à 19:12
Merci, et comment je rajoute une chaine sans perdre la référence vers la suivante ou la précédente?
0
KX
Messages postés
16526
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
18 mai 2022
2 954
15 mars 2017 à 19:19
C'est la chaîne suivante qui portera la référence sur la chaîne précédente (et réciproquement), c'est le principe de la liste chaînée.
0
stampia02
Messages postés
95
Date d'inscription
samedi 30 juillet 2011
Statut
Membre
Dernière intervention
13 mai 2017
1
16 mars 2017 à 21:54
Je pense avoir compris, cependant je ne suis pas sur de ma logique, qu'en pense tu de cette méthode?

	public void insererEnTete(E element) { 
		Chaine n = new Chaine(null, element, null);
		n.precedent = tete.suivant;
		n.suivant = queue.precedent;
		tete.suivant = n;
		queue.precedent = n;
		numVersion++;
		taille++;
	}
0
KX
Messages postés
16526
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
18 mai 2022
2 954
Modifié par KX le 16/03/2017 à 22:23
n.precedent = tete.suivant;
n.suivant = queue.precedent;
Cela veut dire que n est à la fois le suivant de la tête et le précédent de la queue, c'est à dire qu'il est au milieu des deux ? Ça ne peut pas être correct.

Quelques remarques/questions ?
  • Pourquoi mettre null dans
    new Chaine(null, element, null);
    si c'est pour après affecter les valeurs
    n.precedent
    et
    n.suivant
    ?
  • En terme de nommage
    tete
    et
    queue
    sont de mauvais choix car cela correspond au vocabulaire des files, pas des listes.
  • Il te manque les cas initiaux, que se passe-t-il si
    queue
    ou
    tete
    sont null ?
  • À quoi sert
    numVersion
    ?

Il faudrait que tu testes ton code, tu peux commencer par faire la méthode
toString()
de la liste, ça te sera utile pour l'afficher et voir ses modifications successives.
0
stampia02
Messages postés
95
Date d'inscription
samedi 30 juillet 2011
Statut
Membre
Dernière intervention
13 mai 2017
1
Modifié par stampia02 le 16/03/2017 à 22:49
J'utilise
numVersion
pour un itérateur que j'implémente également.
J'ai fais un
toString()
, au départ après 2 insertions javai bien
taille == 2
mais mon toString n'affichai que le dernier element de ma liste.

Exemple: insere "a" puis "insere "b"
Je fais
liste.toString()
et il m'affiche uniquement "b"
Maintenant après modification il m'affiche plus rien

 public void insererEnTete(E element) {
  Chaine n = new Chaine(tete, element, tete.suivant);
  n = tete.suivant;
  numVersion++;
  taille++;
 }


J'ai également mis au début et à la fin une chaine "bidon" sur laquelle la tete pointe histoire de ne jamais avoir de cas null quand j'ajoute un élément.
0