Liste triée en Java

[AliFirat91]

Bonsoir tout le monde, voila j'ai un soucis à propos des liste chainées.
Je travaille sur des listes triées, l'ajout d'un élément se fait toujours au bon endroit.
Et j'ai un soucis à propos de la méthode d'ajout, j'ai du mal à l'implémenter (du point vu algorithmique je l'ai) donc si vous pouvez me donner quelques pistes (je remet aussi peut-être en cause la manière dont je vois les listes chainées en java, j'ai l'impression d'être en C par moment ou leurs implémentations est vachement plus simple!).
Voici ma classe Liste (classe abstraite car je code plusieurs types listes : les listes triées, liste chainée acceptant les doublons et liste chainée qui n'accepte pas les doublons). Dans cette classe se trouve une classe static Node (qui represente un noeud de ma chaine):

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
 
/**
 * Classe abstraite pour representant les listes chainées/
 *
 */
public abstract class Liste {
	/**
	 * Classe interne pour representer un Noeud (un entier, un pointeur sur l'element suivant)
	 *
	 */
	public static class Node {
		private int val;
		private Node next;
 
		public Node(int x) {
			this.val = x;
			this.next = null;
		}
 
		public Node(int x, Node l) {
			this.val = x;
			this.next = l;
		}
 
 
		public int getVal() {
			return val;
		}
 
		public void setVal(int val) {
			this.val = val;
		}
 
		public Node getNext() {
			return next;
		}
 
		public void setNext(Node next) {
			this.next = next;
		}
	}  // Fin de la classe Interne
 
	protected Node deb;
 
	public Liste() {
		deb = null;
	}
 
	public Liste(Node l) {
		this.deb = l;
	}
 
	public boolean estVide() {  /* retourne si la liste est vide */
		return deb == null; 
	}
}

et voici ma classe Liste_simple qui n'accepte pas les doublons( pour l'instant on s'en fiche,moi je veux juste insérer dans l'ordre) :

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
public class List_S extends Liste implements Operations {
 
 
 
	public List_S() {
		super();
	}
 
	public List_S(Node l) {
		super(l);
	}
 
	public Liste ajouteElement(int x) {
		return null;
	}
 
 
 
	public String toString() {
		if(this.estVide()) return "Liste vide";
		String res = "";
		Node l = deb;
		while(l != null) {
			res += l.getVal() + " --> ";
			l = l.getNext();
		}
		return res += "NULL";
	}
 
 
	@Override
	public Liste supprimerElement(int x) {
		// TODO Auto-generated method stub
		return null;
	}
 
	@Override
	public Liste union(Liste l1, Liste l2) {
		// TODO Auto-generated method stub
		return null;
	}
 
	@Override
	public void union(Liste l) {
		// TODO Auto-generated method stub
 
	}
 
	@Override
	public Liste intersection(Liste l1, Liste l2) {
		// TODO Auto-generated method stub
		return null;
	}
 
	@Override
	public void intersection(Liste l) {
		// TODO Auto-generated method stub
 
	}
 
}

Est-ce que vous pensez que j'ai besoin de plus d'information pour faire une telle méthode d'ajout (je parle par exemple d'ajouter des attributs)?
Merci bcp de votre aide

[tchize_]

Envoyé par AliFirat91

Bonsoir tout le monde, voila j'ai un soucis à propos des liste chainées.
Je travaille sur des listes triées, l'ajout d'un élément se fait toujours au bon endroit.
Et j'ai un soucis à propos de la méthode d'ajout, j'ai du mal à l'implémenter (du point vu algorithmique je l'ai)

En même temps, dans le code que tu nous donne tu n'a carrément rien implémenter, tes méthode d'ajout / suppression se contentent de retourne null :s

les listes triées, liste chainée acceptant les doublons et liste chainée qui n'accepte pas les doublons).

Les liste chainées sont loin d'être la structure idéale pour stocker des liste triées :s

[AliFirat91]

Le problème c'est que je suis obligé de passer par des listes triées (c'est imposé par mon projet). Ajouter dans une liste non trié, facile mais par contre ajouter dans un element dans une liste triée, je vois comment le faire à peu près en algo mais en java (et surtout dans la manière dont je represente les listes triées).
Est-ce que par exemple je peux passer par les piles pour representer une liste chainée triée ?

[painfulBetrayal]

Je ne pense pas que passer par des piles soit la solution... tu vas te compliquer la vie en faisant ça.
Pour trier ta liste au moment de l'ajout peut être qu'en utilisant un algorithme dichotomique ça serait plus simple?

[tchize_]

painfulBetrayal: on ne sais pas utiliser de manière performante des algo dichotomiques sur des listes chainées, parce que le principe de ces algo c'est de sauter à des endroit précis de la liste et de s'orienter progressibmenet, on est obligé, dans une liste chainée, de parcourir la moitié de la chaine juste pour la première étape de l'algo dichotomique. Ca occupe un temps o(n) alors qu'avec un tableau ca occupe un temps o(1). On peux améliorer avec les skip-list, mais je pense qu'on est au delà de la demande initiale

[Malinaka]

Bonjour,

basiquement je ferais quelquechose tel que:

• si next node est < element à ajouter, continuer
• sinon creer un nouveau node de valeur element, avec next node= next node de l'element actuel, et ajouter le nouveau node à l'element actuel

Apres c'est un algo trivial, qui doit pouvoir être amélioré