Listes génériques


Comme nous l'avons vu précédemment, une liste d'objets peut être représentée via un attribut pointant sur l'élément suivant. Cet attribut jouant le rôle de pointeur doit être déclaré dans la classe associée aux objets de la liste.

Il existe en Java un autre moyen de procéder, bien plus pratique: l'utilisation de listes génériques, c'est à dire indépendante de la représentation des objets de la liste. Un des intérêts de cette représentation est la gestion automatique des pointeurs.

Nous allons voir ici comment utiliser la classe prédéfinie LinkedList de Java pour représenter et manipuler des listes d'objets. Notez que pour pouvoir accéder à cette classe, il est nécessaire d'importer le package java.util (par import java.util.*; par exemple).


Déclaration et instanciation

Reprenons notre exemple de liste de villes en le représentant cette fois à l'aide d'une liste générique. A présent, il n'y a plus de pointeur dans la classe Ville:

          
class Ville {
  String Nom;
  String CodePostal;
}

La variable L contenant la liste, est déclarée comme suit:

          
LinkedList <Ville> L;

Le type des objets de la liste doit être spécifié entre les symboles < et >. Ce peut être n'importe quelle classe, mais pas un type primitif. Vous ne pouvez donc pas déclarer une liste de int ou de double. Par contre, vous pouvez contourner ce problème en utilisant les classes enveloppes (Integer pour int ou Double pour double par exemple).

Notez qu'après la déclaration précédente, L contient la valeur null. Or, pour les listes génériques, null ne représente pas une liste vide. Pour créer une liste vide, il faut instancier un objet de la classe LinkedList comme suit:

          
 L =  new LinkedList <Ville> ( );

Parcours d'une liste générique

Pour effectuer un traitement sur chaque élément d'une liste, il existe une structure de contrôle spéciale. Il s'agit d'une variante très pratique de la boucle for :


for (Ville v : L) {

     Traitement de l'élément v 

}

Cela signifie: pour chaque élément v de la liste L, effectuer le traitement figurant entre les accolades. Le type de la variable v est déclaré dans les parenthèses.

Exemple

Remarque: cette nouvelle structure de contrôle, que je nommerais la boucle pour chaque, fonctionne également pour les tableaux. Pour effectuer un traitement sur chaque élément e d'un tableau T on écrira:


for (type e : T) {

     Traitement de l'élément e

}

type représente le type des éléments du tableau.

Méthodes utiles

Avec les listes génériques, la manipulation d'une liste est simplifiée grâce à l'utilisation des méthodes de la classe LinkedList. En voici quelques unes (les exemples associés sont tous issus du même projet présenté à la section suivante):

Exemple

L'exemple de projet présenté ici se trouve dans le dossier Exemple-Java-ProgObjet2/ListeVille. Voici son interface graphique:

ListeVille.jpg, 47kB

Noms des composants: CT_Nom, CT_CodePostal, CT_Pos et ZT_ListeVille (zone de texte prévue pour afficher la liste des villes).

La classe Ville est déclarée comme suit:

          
class Ville {
  String Nom;
  String CodePostal;
  Ville (String n, String CP) {Nom = n; CodePostal = CP;}
  
  public boolean equals (Object v) { 
    
    return (Nom.equals(((Ville)v).Nom)) 
           && (CodePostal.equals(((Ville)v).CodePostal)) ; 
  }   
}

Nous avons redéfinie la méthode equals afin que les méthodes indexOf et lastindexOf fonctionnent correctement. Deux objets de la classe Ville seront donc considérés comme identiques s'ils ont les mêmes noms et les mêmes codes postaux.

Notez l'utilisation obligatoire du cast (Ville) v, afin que la variable v soit considérée comme une variable de type Ville à l'intérieur de la méthode. Le paramètre formel de equals, quand à lui, est forcément de type Object, car pour redéfinir une méthode, il faut nécessairement reprendre les types des paramètres formels de la méthode d'origine (dans notre cas, il s'agit de celle de la classe Object.)

La liste des villes est représentée la variable L dont voici la déclaration:


LinkedList <Ville> L =  new LinkedList <Ville> ( );

Au démarrage du projet, la liste L est donc vide.

Affichage de la liste à l'aide de la boucle for

La méthode suivante affiche la liste des villes dans la zone de texte ZT_ListeVille:

 void AfficherListe () {   
 int i = 0;
  
 es.Effacer(ZT_ListeVille);
    
 for (Ville v : L) {
   es.Afficher(i+" : "+v.CodePostal+"-"+v.Nom, ZT_ListeVille);  
   i++;  }
}

Nous utilisons ici la boucle for adaptée aux listes pour parcourir la liste L.

Initialisation de la liste - méthodes clear et push

La méthode suivante vide la liste L à l'aide de la méthode clear, puis y ajoute successivement quatre villes à l'aide de la méthode push :

void Initialiser () {
   
   L.clear();
   L.push(new Ville("Nancy","54000"));
   L.push(new Ville("Strasbourg","67000"));
   L.push(new Ville("Kingersheim","68260"));
   L.push(new Ville("Ribeauvillé","68150"));
  
} 

Comme push ajoute en début de liste, les villes seront donc finalement dans l'ordre inverse, c'est à dire Ribeauvillé en position 0, Kingersheim en position 1, ... etc.

Utilisation des méthodes get et size

Le bouton Afficher permet de retrouver une ville de position donnée. Voici le code de la procédure évènementielle associée:

private void BT_AfficherActionPerformed(...) {                                            
int pos = es.LireEntier(CT_Pos);
Ville v;
if ((pos >=0) && (pos < L.size())) {
   v = L.get(pos);
   es.Afficher(v.Nom, CT_Nom);
   es.Afficher(v.CodePostal, CT_CodePostal);
  }
  else
   es.AfficherMessage("Position inexistante!");
}  

La méthode size nous permet ici de tester si la position demandée ne dépasse pas la fin de la liste. Notez bien que le premier élément est celui de position 0.

Suppression du premier élément

Le bouton Enlever le premier permet de supprimer le premier élément de la liste. Voici le code de la procédure évènementielle associée:

private void BT_Enlever_PremierActionPerformed...) {                                                   
     
if (L.isEmpty())
  es.AfficherMessage("La liste est vide!");
else {
   L.pop();
   AfficherListe ();
   }
}      

Nous utilisons ici la méthode pop pour supprimer le premier élément et la méthode isEmpty, pour tester si la liste est vide.

Suppression d'un élément quelconque avec remove

Pour supprimer un élément de position quelconque, c'est le bouton Supprimer. Voici la procédure évènementielle associée:

private void BT_SupprimerActionPerformed(...) {                                             
int pos = es.LireEntier(CT_Pos);
 
if ((pos>=0) && (pos < L.size())) {
  L.remove(pos);
  AfficherListe ();
  }
else
   es.AfficherMessage("Position non valide");
}     
Insertion avec la méthode add

L'insertion d'une ville à une position donnée de la liste se fait à l'aide du bouton Insérer dont voici la procédure évènementielle:

private void BT_InsererActionPerformed(...) {                                           
String nom = es.Lire (CT_Nom);
String cp = es.Lire(CT_CodePostal);
int pos = es.LireEntier(CT_Pos);
  if ((pos>=0) && (pos <= L.size())) {
      L.add(pos, new Ville(nom,cp));
      AfficherListe (); }
  else es.AfficherMessage("Position d'insertion non valide");
}   
Utilisation de indexOf

Une même ville peut se retrouver plusieurs fois dans la liste. On ne peut donc pas parler de la position d'une ville donnée dans la liste, mais plutot de ses positions où occurrences. Le bouton Première occurence permet de retrouver la première position d'une ville donnée dans la liste. Voici le code de la procédure évènementielle associée:

private void BT_Premiere_OccurenceActionPerformed(...) {                                                      
String nom = es.Lire (CT_Nom);
String cp = es.Lire(CT_CodePostal);
int pos = L.indexOf(new Ville(nom,cp));
      
 if (pos == -1) 
   es.AfficherMessage("Ce morceau n'est pas dans la liste");
 else es.Afficher(pos,CT_Pos);
}    

Implementation

Dans une liste représentée par la classe LinkedList, les pointeurs entre les éléments de la liste ne sont pas directement accessible au programmeur, mais ils existent belle et bien !

Voici, par exemple la représentation qui se cache derrière la liste de ville du projet précédent:

ImplementationLinkedList.jpg, 64kB

Chaque élément de la liste L est un objet, que nous nommerons paire de pointeurs, car il contient deux attributs jouant le rôle de pointeur:

La liste L ne contient donc en réalité que des pointeurs ! Je pense qu'il est utile d'avoir cette représentation à l'esprit lorsque l'on travaille avec des listes génériques. Cela permet de savoir ce qu'il se passe lorsque vous supprimez ou ajoutez des éléments (voir section précédente sur la manipulation des listes représentées à l'aide de pointeurs). Et cela pourra peut être vous aidez à comprendre l'origine de certains bugs.