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 :

• les classes ArrayList  (recommandée) et LinkedList  implémentent l'interface List ;
• la classe HashSet  (recommandée) implémente l'interface Set ;
• la classe TreeSet  implémente l'interface SortedSet ;
• la classe HashMap  (recommandée) implémente l'interface Map ;
• la classe TreeMap  implémente l'interface SortedMap.

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 :

• les champs, les paramètres des méthodes, les variables locales sont toujours déclarées avec comme type une interface (Set, List, etc.) ;
• les classes d'implémentation ne sont utilisées que par l'intermédiaire de leurs constructeurs (HashSet, ArrayList, etc.).

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