Exercice liste chainée générique JAVA - Structures de données abstraites
But: | Ecrivez une liste chaînée générique capable de stocker des objets de n'importe quel type | |||
Thème: | Structures de données abstraites, class Object | |||
Fichiers: | ListeChaineeDouble.java, MoyenneListe.java |
La classe ListeChaineeDouble de l'exercice 1 de la série 12 n'est pas "générique" : la liste chainée implémentée ne permet de stocker que des doubles.
Transformez le code des fichiers ListeChaineeDouble.java et MoyenneListe.java de sorte à parer à cet inconvénient.
Indications: Avant la version JDK 5.0 de Java, la seule façon de mettre en oeuvre la généricité consistait à utiliser la classe Object. Comme toute classe dérive de cette classe, et donc hérite de son type, il est possible de stocker dans un objet de type Object n'importe quel autre type d'objets. C'est cette façon de procéder que vous aller utiliser dans cet exercice.
Question: Citez un problème lié à cette façon de mettre en oeuvre la généricité.
ListeChainee.java, MoyenneListe2.java
ListeChainee.java
| 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101 | class ListeChainee { private Noeud debut = null; private Noeud fin = null; private Noeud courant = null; //constructeurs public ListeChainee() {}; public ListeChainee(Object valeur) { courant = new Noeud(valeur); fin = courant; debut = courant; } /** ajouter un élément à la liste */ public void ajouterElement(Object valeur) { // on crée un nouvel élément de la liste // contenant le double Noeud nouvelleFin = new Noeud(valeur); if (debut == null) { //c'est le tout premier élément de la liste // i.e. la liste était vide debut = nouvelleFin; fin = nouvelleFin; courant = nouvelleFin; } else { // la liste contenait déjà des éléments fin.setSuivant(nouvelleFin); fin = nouvelleFin; } } /** tester si l'élément courant n'est pas null */ public boolean aCourant() { return (courant != null); } // retourner la valeur de l'élément courant de la liste public Object valeur() { if (aCourant()) { return (courant.getValeur()); } else { return null; } } /** retourner le premier élément de la liste */ public Noeud premier() { courant = debut; if (debut == null) { return null; } else { return debut; } } /** retourner l'élément suivant dans la liste */ public Noeud suivant() { if (courant != null) { courant = courant.getSuivant(); } if (courant == null) { return null; } else { return courant; } }}class Noeud { /** la valeur stockée */ private Object valeur; /** la référence à l'élément suivant de la liste */ private Noeud suivant; public Noeud(Object valeur) { this.valeur = valeur; suivant = null; } public Object getValeur() { return valeur; } public void setValuer(Object newValeur) { valeur = newValeur; } public Noeud getSuivant() { return suivant; } public void setSuivant(Noeud newSuivant) { suivant = newSuivant; }} |
MoyenneListe2.java
| 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657 | class MoyenneListe2 { public static void main(String[] args) { ListeChainee notes = new ListeChainee(); /* Notre liste chaînée est programmée pour contenir des "Object"s. Si on veut travailler avec des valeurs numériques, il serait donc normalement nécessaire de stocker dans la liste, des objets de type Double (qui sont des Objects) et non pas de type double (qui ne sont pas des Objects). Bref, il faudrait "emballer" nos doubles dans des Doubles: notes.ajouterElement(new Double(2.0)); C'est en fait comme cela qu'il faut procéder dans toutes les version de Java antérieures à la 1.5. Dans Java 1.5, le compilateur fait automatiquement l'emballage/déballage pour vous, (c'est ce qu'on appelle l'"autoboxing"). Ec ceci nous permet d'écrire sans souci le code suivant: */ notes.ajouterElement(2.0); notes.ajouterElement(1.0); notes.ajouterElement(6.0); notes.ajouterElement(5.5); notes.premier(); // on se positionne au début // de la liste // (notes.courant pointe sur le 1er noeud) double moyenne = 0.0; int n = 0; // tant que notes.courant n'est pas null // on avance dans le liste en calculant // la somme des notes while (notes.aCourant()) { // notes.valeur() donne le double stocké dans // notes.courant Double note = (Double)notes.valeur(); if (note == null){ note = Double.NaN; // Double.NaN est définie dans // la classe Double et signifie // "Not a Number" } moyenne += note.doubleValue(); // En utilisant à nouveau l'autoboxing (JDK 5.0), // on peu écrire la ligne précédente comme suit: // moyenne += note; notes.suivant(); n++; } System.out.println("La moyenne est: " + moyenne / n); }} |
Citez un problème lié à cette façon de mettre en oeuvre la généricité:
Les structures de données génériques codées de cette façon sont moins efficaces que leurs contreparties spécialisées : chaque accès à une donnée nécessite un transtypage entre le type effectif de l'objet et Object.
Ces transtypage ne peuvent évidemment pas se faire au moment de la compilation car le type effectif de la donnée n'est connu qu'au moment de l'exécution. Pour chaque opération de transtypage, l'interpréteur doit vérifier la compatibilité de type des objets lors de l'exécution.
Par exemple, si un String est stocké comme élément d'une structure de données et que l'on cherche à le transtyper en Integer, la machine virtuelle Java va déclencher une exception (plus précisément une ClassCastException).
Si le contenu d'une structure de données générique est accédé de façon intensive (par exemple lors d'un tri), toutes les opérations de transtypage nécessaires vont engendrer une dégradation substantielle de la performance. De plus, un code plein d'opérations de transtypage est beaucoup plus difficile a comprendre et, de facto, à maintenir.
D'un autre point de vue, les structures de données génériques sont très utiles puisqu'elles évitent d'écrire sans cesse le même code pour des types de données différents (ListeChainee pour les double, pour les int, pour les char, pour MesObjetsPreferesAMoi etc..). En fait de nombreuses structures de données génériques sont définies dans l'API de Java (listes, piles, tables de hashage etc..). C'est ce que l'on appelle le "Collection Framework". Dans les versions de Java antérieures à la 1.5, ces structures de données étaient programmées en utilisant des objets de type Object (comme vous l'avez fait dans cet exercice). Java 1.5, a introduit une nouvelle notion, les classes génériques (generics), permettant de contourner, en partie, les problèmes précités.