Collections : listes

Pour chaque type de collection (liste, ensemble, etc.), la bibliothèque Java contient généralement :

• une interface, qui décrit les opérations offertes par la collection en question,
• plusieurs classes implémentant l'interface et qui sont les mises en œuvre de la collection, ayant chacune leurs caractéristiques propre.

De plus, il arrive parfois que les classes de mise en œuvre, ou en tout cas certaines d'entre elles, héritent d'une classe abstraite fournissant le code commun.

La figure 1 présente une vision simplifiée de la hiérarchie de collections que nous étudierons. Les classes abstraites fournissant le code commun ont été omises de cette hiérarchie, car elles ne constituent qu'un détail de mise en œuvre.

En plus des méthodes définies dans les interfaces des différentes collections, on trouve des méthodes statiques relatives aux collections dans les classes Collections et Arrays. Ces deux classes ont pour seul but de regrouper des méthodes statiques, et ne sont donc pas instanciables — leur constructeur est privé. Leurs principales méthodes seront présentées en même temps que les collections concernées.

Attention : ne confondez pas l'interface Collection (sans s) et la classe Collections (avec un s) !.

Une vue (view) est un type particulier de collection qui expose une partie d'une autre collection.

Par exemple, il est possible d'obtenir une vue sur une sous-liste d'une liste au moyen de la méthode subList.

Attention : une vue ne copie pas la collection à laquelle elle donne accès. Donc toute modification à la collection originale est reflétée dans la vue, et inversement !

Les interfaces des différents types de collection contiennent des méthodes permettant de modifier la collection. Par exemple, l'interface List contient une méthode add permettant l'ajout d'un élément à la fin d'une liste.

On pourrait en conclure que les collections sont toujours modifiables, mais ce n'est pas le cas : toutes les méthodes de modification sont désignées comme optionnelles, ce qui signifie qu'elles ont le droit de simplement lever l'exception UnsupportedOperationException pour signaler que l'opération en question n'est pas offerte.

Ce concept de méthode optionnelle n'est pas un concept du langage Java, seulement une convention — au demeurant discutable — utilisée par les concepteurs de la bibliothèque.

Par convention, et à quelques exceptions près, une collection donnée est toujours soit :

• modifiable, auquel cas aucune de ses méthodes optionnelles ne lève l'exception UnsupportedOperationException, soit
• non modifiable, auquel cas toutes ses méthodes optionnelles lèvent l'exception UnsupportedOperationException.

Toutes les classes de mise en œuvre des collections de la bibliothèque Java (ArrayList, LinkedList, HashSet, etc.) sont modifiables. Pour obtenir une collection non modifiable, on peut soit :

• utiliser une méthode retournant une collection immuable, et donc non modifiable (p.ex. emptyList de Collections, qui retourne une liste immuable vide), ou
• obtenir une vue non modifiable sur une collection via les méthodes de Collections dont le nom commence par unmodifiable (unmodifiableList, etc.).

Attention toutefois : les vues non modifiables ne sont pas forcément immuables ! Nous y reviendrons.

L'interface Collection sert d'interface mère aux interfaces List, représentant les listes, et Set, représentant les ensembles.

Comme nous l'avons vu, les listes sont ordonnées mais les ensembles ne le sont pas. Dès lors, seules les méthodes ne dépendant pas d'une notion d'ordre sont définies dans l'interface Collection. Par exemple, Collection ne contient pas de méthode pour insérer un élément à une position donnée, puisque cette opération n'a un sens que si ceux-ci sont ordonnés. Une telle méthode existe par contre dans l'interface List, comme nous le verrons.

L'interface Collection représente donc une collection dont on ne sait pas si elle est ordonnée ou non. Elle est bien entendu générique, son paramètre de type représentant le type des éléments de la collection :

public interface Collection<E> {
  // … méthodes
}

Ses méthodes les plus importantes sont présentées ci-après, parfois avec un type simplifié pour des raisons pédagogiques.

Le concept de liste est représenté dans la bibliothèque Java par l'interface List du paquetage java.util. Tout comme Collection — dont elle hérite — cette interface est générique et son paramètre de type représentant le type des éléments de la liste :

public interface List<E> extends Collection<E> {
  // … méthodes
}

Les principales méthodes que cette interface ajoute à celles de Collection sont présentées ci-après, parfois avec un type simplifié pour des raisons pédagogiques.

La bibliothèque Java offre deux mises en œuvres principales de l'interface List, à savoir les tableaux-listes, ou tableaux dynamiques, (classe ArrayList) et les listes chaînées (classe LinkedList).

Le choix de l'une ou l'autre de ces mises en œuvre dans une situation donnée dépend de l'utilisation qui est faite de la liste. La table ci-dessous, qui compare les complexités des opérations les plus fréquentes pour les deux mises en œuvre, peut servir de guide.

Mais attention : les complexités données ci-dessus ne sont valables que dans des cas bien précis !

En particulier, l'ajout et la suppression d'un élément dans une liste chaînée est en O(1) uniquement s'il n'est pas nécessaire de parcourir la liste en premier lieu pour accéder au point d'ajout ou de suppression. En pratique, cela n'est donc vrai que si on utilise les méthodes add et remove d'un itérateur de liste (voir §8.3), ou si l'ajout ou la suppression se font en début ou en fin de liste (premier ou dernier élément).

D'autre part, l'ajout et la suppression d'un élément dans un tableau-liste sont en O(1) lorsqu'elles se font à la fin de la liste.

En programmation, les queues et les deques sont souvent utilisés pour échanger des données entre un producteur — qui produit des valeurs et les place dans une queue — et un consommateur — qui utilise les valeurs produites en les obtenant de la queue.

Cette organisation permet au producteur et au consommateur de travailler indépendamment l'un de l'autre, chacun à son rythme.

Lorsque producteur et consommateur travaillent à leur rythme et ne communiquent que via une queue, le risque existe que le producteur travaille beaucoup plus vite que le consommateur, faisant grossir la queue de communication jusqu'à utiliser toute la mémoire à disposition.

Pour éviter ce problème, les queues et les deques peuvent être bornées (bounded), c-à-d que leur capacité peut être limitée.

Avec une telle queue, le producteur ne place une valeur dans la queue que si celle-ci n'est pas pleine, et attend que ce soit le cas sinon. Le consommateur, quant à lui, continue à vider la queue à son rythme.

L'interface Queue, qui hérite de l'interface Collection, n'ajoute (ou ne redéfinit) que trois paires de méthodes.

Les deux méthodes formant une paire se distinguent par la manière dont elles signalent une erreur, c-à-d le fait que la queue soit pleine ou vide : la première méthode utilise une exception, la seconde une valeur de retour spéciale.

La version utilisant une valeur de retour spéciale est généralement plus facile à utiliser en présence d'une queue bornée, car il est alors relativement normal que celle-ci soit pleine ou vide.

L'interface Deque ne fait (presque) que généraliser l'interface Queue en offrant deux variantes de chacune des méthodes de Queue, une par extrémité de la deque.

Ces méthodes ne sont donc pas présentées en détail mais résumées dans la table ci-dessous :

Une liste chaînée peut servir de relativement bonne mise en œuvre d'une queue ou d'une deque, raison pour laquelle LinkedList implémente l'interface Deque — et donc Queue.

ArrayList, par contre, serait une très mauvaise mise en œuvre d'une queue ou d'une deque, car l'ajout ou la suppression d'élément au début de la liste est en O(n). Pour cette raison, une mise en œuvre légèrement différente mais aussi basée sur un tableau redimensionné au besoin est fournie dans la classe ArrayDeque.

Un itérateur (iterator) ou curseur (cursor) est un objet qui désigne un élément d'une collection.

Un itérateur permet d'une part d'obtenir l'élément qu'il désigne, et sait d'autre part se déplacer efficacement sur l'élément suivant — et parfois précédent — de la collection.

Dans la bibliothèque Java, le concept d'itérateur est décrit par l'interface générique Iterator. Son paramètre de type représente le type des éléments de la collection parcourue par l'itérateur :

public interface Iterator<E> {
  // … méthodes
}

L'interface Iterator est très simple et ne contient que trois méthodes, dont une (remove) est optionnelle :

• boolean hasNext(), retourne vrai ssi il reste au moins un élément à parcourir,
• E next(), retourne l'élément suivant et avance l'itérateur sur son successeur, ou lève une exception s'il ne reste plus d'éléments,
• void remove(), supprime le dernier élément retourné par next, ou lève une exception si next n'a pas encore été appelée, ou si remove a déjà été appelée une fois depuis le dernier appel à next.

Les collections dont on peut parcourir les éléments offrent toutes une méthode iterator permettant d'obtenir un nouvel itérateur désignant le premier élément. Au moyen de cette méthode, la boucle d'impression ci-dessus peut s'écrire également ainsi :

List<String> l = …;
Iterator<String> i = l.iterator();
while (i.hasNext()) {
  String s = i.next();
  System.out.println(s);
}

Nous connaissons maintenant deux techniques (efficaces) pour parcourir une liste : la boucle for-each et les itérateurs. Laquelle préférer ?

En termes d'efficacité, ces deux techniques sont rigoureusement équivalentes, la boucle for-each étant récrite par le compilateur Java en une boucle basée sur un itérateur.

Par contre, la boucle for-each est plus concise et facile à comprendre. Elle est toutefois moins générale, puisqu'il n'est p.ex. pas possible de supprimer un élément de la collection lors du parcours, comme le permet la méthode remove de l'itérateur.

La boucle for-each peut en fait être utilisée sur n'importe quel objet qui implémente l'interface Iterable, ce qui est entre autre le cas de Collection.

L'interface Iterable, très simple, ne possède qu'une seule méthode abstraite, la méthode iterator vue précédemment :

public interface Iterable<E> {
  public Iterator<E> iterator();
}

Son paramètre de type (E) représente le type des éléments parcourus par l'itérateur.

En plus de cette méthode abstraite, l'interface Iterable offre une méthode par défaut, forEach(Consumer<E> c), destinée à être utilisée avec une lambda. Elle applique le consommateur à chaque élément fourni par l'itérateur retourné par iterator, dans l'ordre. On peut p.ex. l'utiliser pour afficher tous les éléments d'une liste, chacun sur une ligne séparée :

List<Integer> l = Arrays.asList(1, 2, 3, 4, 5);
l.forEach(System.out::println); // affiche 1, puis 2, etc.

Cette méthode offre une troisième technique de parcours des collections en O(n) ! Son utilisation est toutefois à réserver aux cas où le corps de la boucle est très petit, p.ex. un simple appel de méthode comme ci-dessus. Dans les cas plus complexes, une boucle for-each est généralement plus claire.

En plus de la méthode iterator qui fournit un itérateur de type Iterator, l'interface List définit une méthode nommée listIterator fournissant un itérateur de type ListIterator offrant des méthodes additionnelles pour :

• se déplacer en arrière (hasPrevious et previous),
• connaître l'index des éléments voisins de l'itérateur (nextIndex, previousIndex),
• insérer un élément dans la liste, à l'endroit désigné par l'itérateur (add),
• changer l'élément désigné par l'itérateur (set).

Logiquement, add et set sont optionnelles.