next up previous contents index
Next: Collections et tableaux Up: Patterns Previous: Les collections

   
Implémentations d'une collection

 

Les interfaces spécialisées spécifiant les collections et les tables disposent d'une ou de plusieurs implémentations :

Ces deux niveaux permettent de découpler l'implémentation de l'interface. Il faut d'abord choisir les fonctionnalités souhaitées, ce qui détermine l'interface (par exemple, souhaite-t-on utiliser une relation d'ordre sur les éléments ?), puis choisir la représentation de la structure de données (quelles sont les opérations qui doivent être les plus efficaces ?), ce qui détermine l'implémentation. Il faut savoir que dans une ArrayList, les opérations get() et set() se font en temps constant, mais l'opération add() peut se faire en temps linéaire dans le pire des cas (elle se fait cependant se fait en temps amorti constant, c'est-à-dire que nopérations se font en temps O(n)) ; dans une LinkedList, les opérations get() et set() se font en temps linéaire, mais l'opération add() se fait en temps constant. On adoptera donc la discipline d'abstraction suivante :

Ainsi, on déclarera par exemple :

  List l = new ArrayList();
  Set s = new HashSet();
  Map m = new HashMap();

Voici un exemple d'utilisation qui insère dans un ensemble les mots figurant sur la ligne de commande, ce qui permet de détecter les mots apparaissant plusieurs fois comme étant ceux qui ont déjà été insérés ; ce sont les mots m tels que s.add(m) retourne false :

import java.util.Set;
import java.util.HashSet;

class Test {
  public static void main(String[] args) {
    Set s = new HashSet();
    for (int i=0; i<args.length; i++)
      if (!s.add(args[i]))
        System.out.println("mot dupliqué : "+args[i]);
    System.out.println(s.size() + " mots distincts : " + s);
  }
}

Les implémentations des collections servent à leur tour à implémenter certaines structures de données. Voici par exemple une implémentation de l'interface Pile par la classe PileParListe ; un objet de classe PileParListe a un champ privé de type java.util.Liste :

import java.util.List;
import java.util.ArrayList;

class PileParListe implements Pile {

  private List contenu;

  PileParListe() {
    contenu = new ArrayList(); 
  }

  public boolean estVide() {
    return contenu.isEmpty();
  }

  public void empiler(Object o) {
    contenu.add(o);
  }
  
  public Object sommet() {
      return contenu.get(contenu.size()-1);
  }

  public Object dépiler() {
      return contenu.remove(contenu.size()-1);
  } 
}



 
next up previous contents index
Next: Collections et tableaux Up: Patterns Previous: Les collections
R. Lalement
2000-10-23