Quartz 4

Notes S3

7 min read

Notes S3

Notes sur les Collections Java

1. Introduction aux Collections

Une collection est un objet qui groupe plusieurs éléments en une seule unité.

  • Listes (List): Collection ordonnée qui autorise les doublons.
    • Exemples : ArrayList, LinkedList.
  • Ensembles (Set): Collection non ordonnée qui n’autorise pas les doublons.
    • Exemples : HashSet, TreeSet.
  • Tables associatives (Map): Groupe d’associations clé/valeur. Les clés sont uniques.
    • Exemples : HashMap, TreeMap.

2. L’interface Collection<E>

C’est l’interface racine de la hiérarchie des collections. Elle est générique, E représentant le type des éléments.

Attention: ne pas confondre l’interface Collection (sans s) et la classe utilitaire Collections (avec un s).

public interface Collection<E> extends Iterable<E> {
    // Méthodes de consultation
    int size();
    boolean isEmpty();
    boolean contains(Object o);
    boolean containsAll(Collection<?> c);
 
    // Méthodes de modification
    boolean add(E e);
    boolean addAll(Collection<? extends E> c);
    boolean remove(Object o);
    boolean removeAll(Collection<?> c);
    boolean removeIf(Predicate<? super E> filter);
    boolean retainAll(Collection<?> c);
    void clear();
 
    // Itération
    Iterator<E> iterator();
}
  • Pourquoi add(E e) retourne-t-il un boolean ?
    • La méthode retourne true si la collection a été modifiée suite à l’appel.
    • Pour une List, c’est (presque) toujours true.
    • Pour un Set, si l’élément est déjà présent (doublon), add ne fait rien et retourne false.
  • UnsupportedOperationException: Certaines méthodes de modification peuvent lancer cette exception si la collection n’est pas modifiable (p.ex., une liste créée via Collections.unmodifiableList).

Les méthodes qui modifient une collection (add, remove, etc.) sont “optionnelles”: une collection peut choisir de les supporter ou de lever UnsupportedOperationException.

3. Les Listes (List<E>)

Une liste est une collection ordonnée (une séquence). On peut accéder aux éléments par leur index.

Implémentations principales

  • ArrayList: Basée sur un tableau redimensionnable.
    • Accès direct (get/set) : Très rapide, en temps constant O(1).
    • Ajout/Suppression : Lent, surtout au début ou au milieu, car il faut décaler les éléments. Temps linéaire O(n).
  • LinkedList: Basée sur une liste doublement chaînée (chaque élément a une référence vers le suivant et le précédent).
    • Accès direct (get/set) : Lent, car il faut parcourir la liste depuis le début ou la fin. Temps linéaire O(n).
    • Ajout/Suppression : Très rapide (si on a déjà une référence à l’élément), surtout en début ou fin de liste. Temps constant O(1).

Quand choisir ?

  • ArrayList : Le choix par défaut. Idéal si vous accédez souvent aux éléments par leur index.
  • LinkedList : Idéal si vous faites de nombreux ajouts/suppressions en début/fin de liste.

Attention: l’ajout/suppression en LinkedList est O(1) seulement si on est déjà au bon endroit (via un ListIterator) ou en tout début/fin.

Méthodes notables de List<E>

public interface List<E> extends Collection<E> {
    // Accès par index
    E get(int index);
    E set(int index, E element);
 
    // Ajout/Suppression par index
    void add(int index, E element);
    E remove(int index);
 
    // Recherche
    int indexOf(Object o);
    int lastIndexOf(Object o);
 
    // Vues
    List<E> subList(int fromIndex, int toIndex);
}

4. Itération

À éviter: parcourir une LinkedList avec get(i) dans une boucle for → coût total O(n²). Préférer for-each/itérateur → O(n).

Iterable et Iterator

  • L’interface Iterable<E> oblige une classe à fournir un Iterator. Toutes les collections standard sont Iterable.
  • Elle permet d’utiliser la syntaxe “for-each” : for (Element e : collection) { ... }.

L’interface Iterator<E> fournit une manière standard de parcourir une collection :

public interface Iterator<E> {
    boolean hasNext(); // Y a-t-il un élément suivant ?
    E next();          // Retourne l'élément suivant et avance
    void remove();     // Supprime le dernier élément retourné par next()
}

For-each vs. Iterator

La boucle for-each est réécrite par Java en utilisation d’un Iterator: même complexité, mais plus lisible.

Règle: utiliser for-each sauf si on a besoin d’accéder directement à l’itérateur (p.ex. pour supprimer pendant le parcours).

  • Boucle for-each: Plus simple et lisible. À utiliser dans la majorité des cas. java for (String s : myList) { System.out.println(s); }
  • Iterator explicite: Nécessaire quand on doit modifier la collection pendant l’itération.
    • Utiliser iterator.remove() est la seule manière sûre de supprimer un élément d’une collection pendant qu’on la parcourt. Tenter de le faire avec collection.remove() dans une boucle for-each lèvera une ConcurrentModificationException.
    Iterator<String> it = myList.iterator();
while (it.hasNext()) {
    String s = it.next();
    if (s.isEmpty()) {
        it.remove(); // OK
    }
}

5. Les Ensembles (Set<E>)

Un Set est une collection qui ne contient aucun élément en double.

  • HashSet:
    • Stocke les éléments dans une table de hachage.
    • Performances: Très rapide (temps constant O(1) en moyenne) pour add, remove, et contains.
    • Ordre: Ne garantit aucun ordre d’itération.
  • TreeSet:
    • Stocke les éléments dans un arbre équilibré (rouge-noir).
    • Performances: Moins rapide (O(log n)) pour add, remove, et contains.
    • Ordre: Maintient les éléments triés selon leur ordre naturel ou un Comparator fourni.

6. Piles, Files et Deques

  • Pile (Stack): Logique LIFO (Last-In, First-Out). On ajoute (push) et retire (pop) des éléments au même bout (le sommet).
  • File (Queue): Logique FIFO (First-In, First-Out). On ajoute (offer) à une extrémité et on retire (poll) de l’autre.
  • Deque (Deque): “Double-ended queue”. Combine les deux : on peut ajouter et retirer des deux côtés (addFirst, removeFirst, addLast, removeLast).

L’implémentation ArrayDeque est la classe à privilégier pour implémenter une pile ou une file. Elle est plus performante que les anciennes classes Stack (qui est synchronized) et LinkedList.

Règle: pile/file/deque → ArrayDeque. Liste “générale” → plutôt ArrayList (si get/set dominent ou ajouts en fin), sinon LinkedList.

7. Vues sur les collections

Une vue est un objet qui offre une représentation alternative d’une autre collection. Les modifications via la vue modifient la collection d’origine, et vice-versa.

  • subList(b, e): Crée une vue sur une portion d’une liste.
    • Toute modification structurelle (ajout/suppression) sur la liste d’origine invalide la subList.
  • Arrays.asList(a): Crée une vue de type List sur un tableau.
    • On peut modifier les éléments (set), mais pas la taille (pas de add/remove). Le tableau sous-jacent est modifié.
  • Collections.unmodifiableList(l): Crée une vue non modifiable d’une liste.
    • Toute tentative de modification via cette vue (add, set, remove) lèvera une UnsupportedOperationException.
    • Attention: Si la liste d’origine est modifiée, les changements sont visibles dans la vue non modifiable.
    Règle: pour obtenir une liste réellement immuable à partir d’une liste quelconque, utiliser List.copyOf(...) (copie immuable) et pas seulement unmodifiableList (vue).

8. Cas pratique : LongestWord

Problème: Charger un dictionnaire de mots dans une liste, puis trouver le mot le plus long.

  1. Avec ArrayList et addFirst:
    • Si on charge les mots un par un en les ajoutant au début (list.add(0, word)), chaque ajout coûte O(n) car il faut décaler tout le tableau. Le chargement total est très lent : O(n²).
  2. Avec LinkedList:
    • Le chargement avec addFirst (ou addLast) est instantané : O(1) pour chaque mot. Le chargement total est donc rapide : O(n).
    • MAIS, si on cherche ensuite le mot le plus long avec une boucle for classique et des appels à get(i): java // ANTI-PATTERN pour LinkedList for (int i = 0; i < list.size(); i++) { if (list.get(i).length() > maxLength) { /* ... */ } } Chaque appel à list.get(i) coûte O(n). La boucle entière devient O(n²).
  3. La bonne solution (LinkedList + for-each):
    • On utilise une LinkedList pour le chargement rapide O(n).
    • On parcourt la liste avec une boucle for-each, qui utilise un itérateur en coulisses. java // Solution efficace for (String word : list) { if (word.length() > maxLength) { /* ... */ } }
    • Le parcours avec un itérateur est linéaire. La recherche du mot le plus long coûte donc O(n).
    • Le coût total (chargement + recherche) est O(n).

Graph View

Backlinks