Exercice java corrigé: Liste chainée générique-structures de données abstraites

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 <valeur>
        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;
    }

}
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é:

Lire aussi  Exercice Java: Opération sur les tableaux Java

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.

Lire aussi  Exercice Java: Programme de conversion majuscules minuscules

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *