6.3 Réalisations d'une collection

Les interfaces spécialisées spécifiant les collections disposent d'une ou de plusieurs réalisations, toutes membres du paquet java.util :

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

Après avoir choisi 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 ?), il faut 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 la réalisation. 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 en temps amorti constant, c'est-à-dire que $n$ opé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 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 de réalisation 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 Duplications {
  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);
  }
}

6.3.0.0.1 Réalisation des piles

Ces classes, réalisations des collections, servent à leur tour à réaliser certaines structures de données. Voici par exemple une réalisation de l'interface Pile

package structures;

public interface Pile {

  boolean estVide();
  void empiler(Object o);
  Object sommet();
  Object dépiler();
}

Un objet de classe PileParListe a un champ privé de type List auquel toutes les opérations sur les piles seront déléguées :

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

6.3.0.0.2 Réalisation des files

La classe LinkedList définit des méthodes supplémentaires (c'est-à-dire des méthodes qui ne sont pas déclarées dans l'interface List). Ce sont les méthodes permettant d'accéder aux deux extrémités de la liste : addFirst, addLast, getFirst, getLast, removeFirst et removeLast. Elles permettent par exemple de réaliser des files, dont voici l'interface :

package structures;

public interface File {

  boolean estVide();
  void enfiler(Object o);
  Object tête();
  Object défiler();
}

Pour utiliser ces méthodes supplémentaires, il est nécessaire de déclarer la référence de type LinkedList et non de type List comme le voudrait la discipline d'abstraction :

import java.util.List;
import java.util.LinkedList;

class FileParListe implements File {

  private LinkedList contenu;    // et non List ...

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

  public boolean estVide() {
    return contenu.isEmpty();
  }
  
  public void enfiler(Object o) {
    contenu.addFirst(o);
  }

  public Object tête() {
    return contenu.getLast();
  }
  
  public Object défiler() {
    return contenu.removeLast();
  }
}

6.3.0.0.3 D'une collection à l'autre

Toutes les classes réalisant Collection disposent d'un constructeur ayant un paramètre de type Collection. Ces constructeurs permettent de transformer une collection quelconque en une nouvelle collection d'un type donné.

Ainsi, si l'on souhaite indexer les éléments d'un ensemble, il suffit de le transformer en un objet de type List ; inversement, si l'on souhaite considérer une liste d'éléments comme un ensemble, il suffit de la transformer en un Set, ce qui a pour effet de supprimer les éléments dupliqués de la liste :

  Set s1 = ... ;
  List l1 = ... ;
  Set s2 = new HashSet(l1);
  List l2 = new ArrayList(s1);

Bien que les tables ne soient pas des instances de Collection, trois méthodes permettent de voir une table comme une collection :

• keySet retourne l'ensemble des clés ;
• values retourne la collection des valeurs ;
• entrySet retourne l'ensemble des associations clé/valeur ; les éléments de cet ensemble sont de type Map.Entry (il s'agit d'une interface interne, membre de Map) ; les méthodes getKey et getValue permettent d'obtenir les deux composantes d'une association.

  Map m = ...;
  Set 
    clés = m.keySet(), 
    associations = m.entrySet();
  Collection valeurs = m.values();

Les collections constituent un moyen à la fois beaucoup plus souple et plus puissant que les tableaux pour stocker des données. Il est souvent commode de réaliser des ``conversions'' entre tableaux et collections.

La méthode Object[] toArray() retourne un nouveau tableau d'objets contenant tous les éléments d'une collection :

  Collection c = ...;
  Object[] t = c.toArray();

Si l'on souhaite spécifier le type du tableau ainsi créé, on doit utiliser une autre méthode Object[] toArray(Object[] a). Par exemple, pour créer un tableau de String (et non un tableau d'objets), il suffit de passer comme argument à cette méthode un tableau de String (même de taille nulle), et ensuite de faire un transtypage vers String[] :

  String[] t = (String[]) c.toArray(new String[0]);

Cette forme retorse est due au fait que le type d'une référence à un tableau n'est jamais déterminé par le type de ses éléments : par exemple, le tableau désigné par a dans l'exemple suivant est de type Object[], et non String[], alors que l'instance définie par s est de type String :

  Object[] a = {"p", "q"};
  Object s = "p";

De plus, si le tableau passé en argument à toArray est de taille suffisante, il est utilisé pour copier les éléments de la collection, de sorte qu'aucun autre objet n'est créé en mémoire :

  String[] s = new String[c.size];
  Object[] x =  (String[]) c.toArray(s);  // x == s

Inversement, la fonction List asList(Object[] a) de la classe java.util.Arrays construit une liste basée sur un tableau d'objets :

  Object[] t = ...;
  List l = Arrays.asList(t);

La documentation précise que la liste l est de taille fixe (ce n'est donc une instance ni de ArrayList, ni de LinkedList) et que le tableau et la suite ont les mêmes éléments (toute modification faite à un élement de l modifie l'élément correspondant de t).