Liste circulaire généricité

Version imprimable

Bonjour,

J'ai programme qui s'occupe de liste circulaire avec la notion de généricité.
J'ai donc commencé à faire quelque chose mais je n'arrive pas à modifier les méthodes pour ajouter, supprimer, se déplacer
Voici le code:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
 
 
public class CelluleEntierCirculaire<X> {
	private X valeur;
	private CelluleEntierCirculaire<X> celluleSuivante;
	private CelluleEntierCirculaire<X> cellulePrecedente;
 
	//Creation d’une cellule contenant la valeur n
	CelluleEntierCirculaire(X n){
		this.valeur = n;
		this.celluleSuivante = null;
		this.cellulePrecedente = null;
	}
 
	//Creation d’une cellule contenant la valeur n et ayant comme cellule suivante la cellule c
	CelluleEntierCirculaire(X n, CelluleEntierCirculaire<X> c){
		this.valeur = n;
		this.celluleSuivante = c;
	}
 
	//Renvoie la valeur contenue dans la cellule
	public X valeur(){
		return this.valeur;
	}
 
	//Renvoie la cellule suivante
	public CelluleEntierCirculaire<X> celluleSuivante(){
		if(this.celluleSuivante != null)
			return this;
		else
			return this.celluleSuivante;
	}
}

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
 
 
public class ListeDEntiersCirculaire<X>{
	private CelluleEntierCirculaire<X> cellule;
 
	//Liste vide
	ListeDEntiersCirculaire(){
		this.cellule = null;
	}
 
	//Liste d’un élément
	ListeDEntiersCirculaire(X n){
		this.cellule = new CelluleEntierCirculaire<X>(n);
	}
 
	//Construction d’une liste par ajout d’un élément en tête d’une liste
	ListeDEntiersCirculaire(X n, ListeDEntiersCirculaire<X> l){
		this.cellule = new CelluleEntierCirculaire<X>(n,l.cellule);
	}
 
	//Renvoie la valeur de la tête de la liste
	public X tete(){
		assert(this.cellule!=null);
		return this.cellule.valeur();
	}
 
	//Supprime la premier valeur de la liste
	public void queue(){
		assert(this.cellule!=null);
		this.cellule = this.cellule.celluleSuivante();
	}
 
	//Ajoute un entier en tête de liste
	public void ajoute(X n){
		this.cellule = new CelluleEntierCirculaire<X>(n, this.cellule);
	}
 
	//Indique si la liste est vide
	public boolean estVide(){
		return cellule==null;
	}
 
	//Renvoie la longueur de la liste
	public int longueur(){
		int longueur = 0;
		CelluleEntierCirculaire<X> c = this.cellule;
		while (c!=null) {
			longueur = longueur + 1;
			c = c.celluleSuivante();
		}
		return longueur;
	}
 
	//Renvoie une chaîne de caractères représentant la liste
	public String toString(){
		String s = "[";
		CelluleEntierCirculaire<X> c = this.cellule;
		while (c!=null) {
			s = s + c.valeur();
			c = c.celluleSuivante();
			if (c!=null) s = s +"; ";
		}
		s = s + "]";
		return s;
	}
}

Merci de votre aide

11/10/2015, 16h17
eulbobo

Ce que tu essayes de mettre place, ça ressemble à une liste chaînée. Va regarder de ce côté pour voir les différents algo possible.
Sinon, tu peux aller voir le code de la LinkedList qui est une liste chainée.

Pour se déplacer, implémentes Iterable et fourni un iterateur de ton cru qui puisse parcourir ta liste (qui en gros récupère l'élément courant, puis qui appelle "suivant" à chaque next)
Pour l'ajout/suppression, il faut refaire les liens entre des éléments

Exemple, tu as la chaine A-B-C-D, et tu veux insérer un élément X après le B
Tu vas sur B, tu récupères une instance de C, puis tu fais
B.suivant = X
C.precedent = B
C.suivant = D
D.precedent = X

Autre point : dans ton code tu utilises des tests avec assert. Il faut savoir que ces testes ne fonctionnent qu'avec les assertions activées au moment de l'exécution, que par défaut elles sont désactivées, et que c'est censé être des tests de développement, pas de fonctionnement normal de l'application : un assert qui échoue renvoie une java.lang.Error qu'on ne DOIT PAS essayer de traiter (le but est le plantage rapide et direct de l'application)

Code:

1 2 3 4 5 6 7 //Renvoie la cellule suivante public CelluleEntierCirculaire<X> celluleSuivante(){ if(this.celluleSuivante != null) return this; else return this.celluleSuivante; }
est ce que ce n'est pas plutot :
Code:

1 2 3 4 if (this.celluleSuivante != null) return this.celluleSuivante; else return null
Je ne vois pas de code qui rattache la queue de la liste a la tete de liste pour avoir la propriete de "circulaire" ?

En tout cas si tu veux travailler sur une simple liste, eulbobo a raison pour LinkedList

12/10/2015, 21h47
totot

Justement le code que j'ai c'est pour des listes simple et je souhaiterais l'utiliser pour des listes circulaire mais je n'y arrive pas

Qu'est-ce que tu appelles une liste circulaire?

Dans l'idée, moi je vois ça comme un ensemble d'éléments qui forment une chaine sans fin, donc pas de début et pas de fin.
Chaque élément est lié à deux autres : un avant, un après, et un élément utilisé dans l'une des positions ne peut pas l'être ailleurs dans la même position.

Du coup, il n'y a pas de notion de position dans la liste (du coup, au mieux tu devras implémenter les méthodes de collection), chaque élément est unique dans ta collection par design (du coup on se rapproche d'une implémentation de type Set).

Pour le fait, tu as donc besoin
D'une classe ListeCirculaire<T> qui contiendra comme propriétés
- des méthodes génériques de List pour manipuler les objets
- un objet ListCirculaireElement<T> qui sera le premier élément de ta liste (le premier ajouté)
- Un HashSet<T> privé qui contient la liste de tous les éléments de ta liste circulaire (on revient sur l'intérêt après)

La classe ListCirculaireElement<T> (classe interne, c'est une bonne solution) qui contiendra
- Un élément (de type T)
- Un lien vers le ListCirculaireElement précédent getPreviousElement/setPreviousElement
- Un lien vers le ListCirculaireElement suivant getNextElement/setNextElement

Quand tu crées le premier élément, tu lui attribue lui même en suivant et en précédent.
Quand tu ajoutes un élément, tu dois forcement l'ajouter en référence à un autre élément :
- addBefore(T elementInList, T elementToAdd)
- addAfter(T elementInList, T elementToAdd)
Dans ces méthodes, tu modifies les liens de tes éléments

Pour addBefore par exemple, tu
Code:

1 2 3 4 5 6 7 ListCirculaireElement<T> elementInList = findElement(circularElement ); ListCirculaireElement<T> previousElement = elementInList.getPreviousElement(); previousElement.setNextElement(elementToAdd); elementToAdd.setPreviousElement(previousElement); elementToAdd.setNextElement(elementInList); elementInList.setPreviousElement(elementToAdd);
Il faut aussi rajouter un test pour vérifier qu'un élément que tu ajoutes (elementToAdd) n'est pas déjà présent dans ta liste. C'est là qu'intervient notre HashSet privé qui contient les éléments de ta liste : tu n'autorise un ajout que si ton élément elementToAdd n'est pas déjà présent dans ton HashSet

Pour la suppression d'un élément, la méthode est simple : removeElement
Première étape : tu parcours tes éléments jusqu'à trouver l'élément que tu veux supprimer, puis tu refais les liens entre le previous et le after (et tu supprimes ton élément de ton hashet)
Code:

1 2 3 4 5 6 ListCirculaireElement<T> elementToDelete= findElement(circularElement ); ListCirculaireElement<T> previousElement = elementToDelete.getPreviousElement(); ListCirculaireElement<T> nextElement = elementToDelete.getNextElement(); previousElement.setNextElement(nextElement); nextElement.setPreviousElement(previousNext);
Essayes d'implémenter Iterable pour parcourir simplement ta liste (en vérifiant de bien l'arrêter une fois que l'itérateur a bouclé).
Tu peux même fournir une interface de ton cru qui étend Iterator et qui permette de faire de l'iteration inversée

Tu ne pourras pas ajouter la méthodes addAll par design à moins de faire le choix que ces éléments sont ajoutés tel quels dans l'ordre de l'iteration à la "fin" de ta liste (avant le premier élément en gros)
containsAll et removeAll c'est faisable

Les performances en insertion seront rapidement désastreuses à moins d'avoir un autre moyen de récupérer rapidement un élément depuis sa valeur (une HashMap<T, ListCirculaireElement<T>>, ce qui supprimerai le besoin d'avoir un premier élément et un HashSet des éléments contenus dans la liste)

J'ai avancé mais je bloque pour certains points et je voudrais qu'on me dise si c'est bon ce que j'ai fais:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public class CelluleCirculaire<X> {
	private X valeur;
	private CelluleCirculaire<X> celluleSuivante;
	private CelluleCirculaire<X> cellulePrecedente;
 
	//Creation d’une cellule contenant la valeur n
	CelluleCirculaire(X n){
		this.valeur = n;
		this.celluleSuivante = null;
		this.cellulePrecedente = null;
	}
 
	public X getValeur() {
		return valeur;
	}
 
	public void setValeur(X valeur) {
		this.valeur = valeur;
	}
 
	public CelluleCirculaire<X> getCelluleSuivante() {
		return celluleSuivante;
	}
 
	public void setCelluleSuivante(CelluleCirculaire<X> celluleSuivante) {
		this.celluleSuivante = celluleSuivante;
	}
 
	public CelluleCirculaire<X> getCellulePrecedente() {
		return cellulePrecedente;
	}
 
	public void setCellulePrecedente(CelluleCirculaire<X> cellulePrecedente) {
		this.cellulePrecedente = cellulePrecedente;
	}
}

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
public class ListeCellulesCirculaire<X>{
	private CelluleCirculaire<X> debut;
	private CelluleCirculaire<X> fin;
 
	//Liste vide
	ListeCellulesCirculaire(){
		this.debut = null;
		this.fin = null;
	}
 
    public void ajouterDebut(CelluleCirculaire<X> cellule){
		cellule.setCellulePrecedente(null); // au cas ou
		cellule.setCelluleSuivante(this.debut);
		if(this.debut == null)
		    this.fin = cellule;
		else 
		    this.debut.setCellulePrecedente(cellule);
		this.debut = cellule;
    }
 
    public void ajouterFin(CelluleCirculaire<X> cellule){
		cellule.setCelluleSuivante(null); // au cas ou
		cellule.setCellulePrecedente(this.fin);
		if (this.fin == null)
		    this.debut = cellule;
		else
		    this.fin.setCelluleSuivante(cellule);
		this.fin = cellule;
    }
 
	//Renvoie la longueur de la liste
	public int longueur(){
		int longueur = 0;
		CelluleCirculaire<X> c = this.debut;
		while (c!=null) {
			longueur = longueur + 1;
			c = c.getCelluleSuivante();
		}
		return longueur;
	}
 
	//Renvoie une chaîne de caractères représentant la liste
	public String toString(){
		String s = "[";
		CelluleCirculaire<X> c = this.debut;
		while (c!=null) {
			s = s + c.getValeur();
			c = c.getCelluleSuivante();
			if (c!=null) s = s +"; ";
		}
		s = s + "]";
		return s;
	}
 
	public CelluleCirculaire<X> getDebut() {
		return debut;
	}
 
	public void setDebut(CelluleCirculaire<X> debut) {
		this.debut = debut;
	}
 
	public CelluleCirculaire<X> getFin() {
		return fin;
	}
 
	public void setFin(CelluleCirculaire<X> fin) {
		this.fin = fin;
	}
}

Je voudrais savoir ceci comme fonction:
- lire l'élément en cours
- se décaler sur l'élément suivant
- ajouter et supprimer un élément
- calculer la longueur de la liste
- rechercher un élément dans la liste

En supposant qu'une liste circuaire est une liste dans laquel le dernier element est relie au premier, je commencerai par corriger ta fonction ajouterDebut(). Il faudra adopter la meme logique pour ajouterFin();
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 public void ajouterDebut(CelluleCirculaire<X> cellule){ if (this.isEmptyList()) { debut = cellule; fin = cellule; cellule.setCellulePrecedente(debut); // liste circulaire : le dernier element pointe sur le premier cellule.setCelluleSuivante(fin); // liste circulaire : le premier element pointe sur le dernier } else { cellule.setCelluleSuivante(this.debut); // on lie le nouvel element a la tete de liste existante. cellule.setCellulePrecedente(this.fin); // on lie le nouvel element se trouvant en debut de liste au dernier element de la liste (Propriete circulaire) this.debut.setCellulePrecedente(cellule); // on lie l'ancien element debut au nouvel element ajoute this.fin.setCelluleSuivante(cellule); // La dernier element deja existant pointe sur le nouvel element ajoute en debut de liste. this.debut = cellule; } }
- pour la fonction "lire l'element en cours" : Qu'entend tu pars la ? Si tu retiens le dernier element lu, alors il te faudra creer une variable Cellule (nomme par exemple "currentCell" qui pointera soit sur le dernier element lu soit sur le prochain a lire.
- "se decaler sur l'element suivant" : Si on se base sur la variable cite precedement alors tu auras :
Code:

1 2 3 4 private Cellule getNextCell() { currentCell = currentCell.getElementSuivant(); return currentCell }
- "ajouter et supprimer un élément" : je te renvoi a ajoutDebut() car c'est la meme logique.

- "calculer la longueur de la liste" : Pour ma part j'aurai defini une variable de classe qui augmenterai de 1 lors de l'ajout et se reduirait de 1 lors de la suppression. Si tu veux vraiment parcourir ta liste alors :
Code:

1 2 3 4 5 6 7 8 Cellule c = debut; int size = 0; while (c != fin || c.celluleSuivant != debut) { size++; c = c.celluleSuivante(); } return size;
- "rechercher un élément dans la liste" : une simple boucle comme le while precedent en ajoutant le if qui te convient.

Je n'ai pas teste mais cela devrait etre bon.