Aller au contenu

Les Collections

Ce sont des classes qui permettent de stocker, manipuler et parcourir des groupes d’objets.

Il existe plusieurs types de collections qui ont chacune leurs propres caractéristiques et utilisations.

Listes (implémentation de List)

Une liste est un ensemble ordonné d’éléments qui peuvent se répéter.

Il existe plusieurs implémentations de listes :

Exemple de code :

List<String> liste = new ArrayList<>();
liste.add("Java");
liste.add("C++");
liste.add("Python");
System.out.println(liste); // Affiche "[Java, C++, Python]"

Laquelle utiliser entre LinkedList et ArrayList ?

La LinkedList est une implémentation de List qui utilise des liens entre les éléments pour stocker les données.

Principe : Chaque élément contient une référence à l’élément précédent et suivant, permettant ainsi de parcourir la liste dans les deux sens.

Elle permet d’insérer ou supprimer des éléments à n’importe quelle position dans la liste, mais elle rend les accès aléatoires plus lents que dans une ArrayList.

Remarque : C’est pratique si vous devez souvent insérer ou supprimer des éléments à des positions spécifiques de la liste, ou si vous devez parcourir la liste dans les deux sens. Cependant, attention, si vous avez besoin d’accéder fréquemment à des éléments spécifiques de la liste, il est préférable d’utiliser une ArrayList car elle sera plus rapide pour les accès aléatoires.

Petit exemple concret en utilisant une LinkedList pour stocker une liste d’entiers :

LinkedList<Integer> liste = new LinkedList<>();
liste.add(1);
liste.add(2);
liste.add(3);
liste.add(4);

System.out.println(liste); // Affiche : [1, 2, 3, 4]

liste.add(1, 5);
System.out.println(liste); // Affiche : [1, 5, 2, 3, 4]

liste.remove(2);
System.out.println(liste); // Affiche : [1, 5, 3, 4]

La liste de course

Si je fais une liste de course, quelle liste utiliser ?

Les 2 sont possibles, tout dépend de ce que l’on souhaite manipuler.

Si on choisit une ArrayList, elle sera plus rapide pour les opérations d’accès par index, car elle utilise un tableau interne pour stocker les éléments. mais, elle sera plus lente pour les opérations d’ajout et de suppression, car il faut déplacer les éléments suivants lorsqu’un élément est ajouté ou supprimé au milieu de la liste.

Si on utilise la LinkedList, sachant qu’elle utilise des noeuds pour stocker les éléments, elle sera plus lente pour les opérations d’accès par index, mais plus rapide pour les opérations d’ajout et de suppression. Ce type de LinkedList est particulièrement utile lorsqu’on doit ajouter ou supprimer des éléments de manière fréquente soit en début de liste, soit en fin de la liste !

On va stocker notre liste de course dasns une ArrayList :

import java.util.ArrayList;

public class ListeCourses {

    public static void main(String[] args) {
        ArrayList<String> listeCourses = new ArrayList<>();

        listeCourses.add("Pain");
        listeCourses.add("Lait");
        listeCourses.add("PQ");
        listeCourses.add("Oeufs");
        listeCourses.add("Beurre");

        // Affiche la liste de courses
        System.out.println("Liste de courses : " + listeCourses);

        // Ajout d'un élément à la fin de la liste
        listeCourses.add("Fruits");
        System.out.println("Liste de courses : " + listeCourses);

        // Suppression d'un élément de la liste
        listeCourses.remove("Lait");
        System.out.println("Liste de courses : " + listeCourses);
    }
}

Maintenant, on va stocker notre liste de course dans une LinkedList :

import java.util.LinkedList
...

LinkedList<String> listeCourses = new LinkedList<>();
listeCourses.add("Pommes");
listeCourses.add("Poires");
listeCourses.add("Bananes");
listeCourses.add("Ordinateur");
listeCourses.add("Lait");

System.out.println("Liste de courses : " + listeCourses);

// Ajout d'un élément à la fin de la liste
listeCourses.addLast("Pain");
System.out.println("Liste de courses avec pain ajouté : " + listeCourses);

// Ajout d'un élément au début de la liste
listeCourses.addFirst("Beurre");
System.out.println("Liste de courses avec beurre ajouté : " + listeCourses);

// Suppression d'un élément
listeCourses.remove("Poires");
System.out.println("Liste de courses après suppression des poires : " + listeCourses);

Cette dernière (LinkedList) est une liste doublement liée !

L’intérêt du Linked est que chaque noeud possède des informations sur le noeud précédent s’il existe et le noeud suivant s’il y en a un. Commme je le précise un peu plus loin, on peut naviguer dans les 2 sens au sein de ce type de collection.

En fin de compte, la LinkedList permet d’insérer ou de supprimer des éléments rapidement à n’importe quel emplacement de la liste.

C’est donc une bonne option pour les utilisations qui nécessitent de nombreuses opérations d’insertion et de suppression, comme dans l’exemple de notre liste de courses !

En revanche, si vous avez besoin de rechercher fréquemment des éléments dans une liste, il est préférable d’utiliser une ArrayList plus rapide pour les recherches car elle utilise un tableau pour stocker les éléments.

Ensembles (Set)

C’est un ensemble non ordonné d’éléments uniques.

Il existe plusieurs implémentations d’ensembles :

Exemple de code :

Set<Integer> set = new HashSet<>();
set.add(5);
set.add(7);
set.add(5); // 5 ne sera pas ajouté car déjà présent, ouf ! donc pas besoin de contrôler
System.out.println(set); // Affichera {5, 7}

Files

C’est une liste d’éléments qui respecte une ordre d’arrivée et de sortie le fameux FIFO (First In, First Out, soit Premier entré, premier sorti) ne pas confondre avec la FIFA !

Il existe plusieurs implémentations ce ces files :

Exemple de code :

Queue<String> queue = new ArrayDeque<>();
queue.add("Java");
queue.add("C++");
queue.add("Python");
System.out.println(queue.poll()); // affiche : Java et retire l'élément de la queue
System.out.println(queue.poll()); // affiche : C++ et le retire de la queue

Maps

C’est une collection permettant de stocker des paires clé-valeur.

Il existe plusieurs implémentations de Map :

Différences entre HashMap et LinkedHashMap

La HashMap et la LinkedHashMap sont toutes les deux des implémentations de l’interface Map.

La principale différence entre les deux est l’ordre des éléments.

La HashMap stocke les éléments dans un ordre qui n’est pas garanti.

Les éléments sont stockés en utilisant une fonction de hachage qui permet d’accéder rapidement à un élément en utilisant sa clé.

La HashMap est optimisée pour les opérations de recherche et de suppression, mais pas pour les opérations d’itération !

Voici un exemple de code pour créer une HashMap :

HashMap<String, Integer> monMap = new HashMap<>();
monMap.put("Clé1", 1);
monMap.put("Clé2", 2);
monMap.put("Clé3", 3);

La LinkedHashMap stocke ses éléments dans l’ordre dans lequel ils ont été ajoutés.

ça veut dire qu’elle maintient une liste chaînée des éléments ce qui permet une itération dans l’ordre d’insertion.

Attention : Ce n’est pas conseillé pour les opérations de recherche et de suppression (plus lentes qu’avec la HashMap)

Voici un exemple de code pour créer une LinkedHashMap et ajouter des éléments :

LinkedHashMap<String, Integer> monMap = new LinkedHashMap<>();
monMap.put("Clé1", 1);
monMap.put("Clé2", 2);
monMap.put("Clé3", 3);

En résumé :

Remarque : Comment sait-on que la HashMap ne garantie pas l’ordre des éléments ajoutés ? en quoi cela est-il gênant ?

La HashMap utilise une fonction de hachage pour stocker ses éléments. Cette fonction prend en compte la clé de l’élément pour le stocker à un emplacement précis dans la table de hachage. Cependant, ça veut dire que l’ordre dans lequel les éléments ont été ajoutés n’est pas pris en compte lors de la stockage. Ainsi, lorsque l’on parcourt les éléments d’une HashMap, ils peuvent être retournés dans un ordre différent de celui dans lequel ils ont été ajoutés !

Attention : Cela peut être gênant dans les cas où l’ordre dans lequel les éléments ont été ajoutés est important !

Exemple : Si vous utilisez une HashMap pour stocker les étapes d’un processus, et que vous voulez les parcourir dans l’ordre où ils ont été ajoutés. Dans ce cas, il est préférable d’utiliser une LinkedHashMap qui maintient l’ordre d’insertion des éléments !

C’est quoi une table de Hashage ?

Une table de hachage est une structure de données qui utilise une fonction de hachage pour associer des clés à des valeurs.

Le but de cette fonction est de transformer la clé en un indice de table de sorte qu’on puisse accéder rapidement à la valeur correspondante.

La table de hachage est souvent utilisée pour implémenter des tableaux associatifs (comme en Php), des caches, des index de base de données, etc.

Elles sont souvent plus rapides que les structures de données alternatives pour les opérations de recherche, d’insertion et de suppression, car elles ont un temps d’accès constant.

Exemple :

A chaque fois qu’une clé est ajoutée à une table de hachage, elle est d’abord passée à travers une fonction de hachage qui génère un index ou un emplacement où la valeur associée à cette clé sera stockée.

Du coup, lorsqu’une valeur est recherchée dans la table, la clé est à nouveau passée à travers la fonction de hachage pour trouver l’emplacement où la valeur est stockée.

Exemple d’utilisation d’une HashMap :

HashMap<String, Integer> notes = new HashMap<>();
// ajout de quelques éléments à la HashMap
notes.put("Marie", 15);
notes.put("Paul", 12);
notes.put("Lucie", 18);
notes.put("Mathieu", 14);

// affichage de tous les éléments
// ici on récupère des objets de type Map.Entry pour récupérer
// la clef et la valeur en même temps. C'est un peu fastidieux à écrire.
for (Map.Entry<String, Integer> entry : notes.entrySet()) {
    System.out.println(entry.getKey() + " : " + entry.getValue());
}

// ou de cette manière, plus simplement
// avec une boucle foreach()
for( String key : notes.keyset())
{
    System.out.println(key + " : " + notes.get(key));
}

Explication :

Récapitulatif des Collections en Java

Liste de quelques unes des méthodes fréquemment utilisées

Liste de méthodes spécifiques selon les Collections

Comment fonctionnent PriorityQueue et ArrayDeque ?

Elle permet de stocker des éléments en respectant un ordre de priorité. Cet ordre est défini en fonction de la méthode compareTo() des éléments contenus dans la PriorityQueue. Si cette méthode n’est pas surchargée, donc redéfinie, les éléments seront triés en fonction de leur ordre naturel.

Exemple de code :

PriorityQueue<Integer> queue = new PriorityQueue<>();
queue.offer(30);
queue.offer(20);
queue.offer(10);
System.out.println(queue.poll()); // affiche 10
System.out.println(queue.poll()); // affiche 20
System.out.println(queue.poll()); // affiche 30

Elle permet de stocker des éléments de manière doublement chaînée, ça veut dire qu’on peut ajouter et supprimer des éléments à la fois au début et à la fin de ArrayDeque. Cette classe permet un accès rapide aux éléments du début et de la fin de la collection mais sans la possibilité de donner une priorité comme avec PriorityDeque.

Pour info, Deque** est une abréviation qui veut dire *Double-Ended Queue (file à double extrémité ou entrée en français). C’est une interface de la bibliothèque standard de Java qui définit un type de données permettant de stocker une série d’éléments ordonnés avec la possibilité d’ajouter ou retirer des éléments à la fois en tête et en queue. Cette interface permet de manipuler des éléments de la fil avec une certaine flexibilité.

Exemple :

ArrayDeque<String> deque = new ArrayDeque<>();
deque.addFirst("Premier");
deque.addFirst("Milieu");
deque.addLast("Dernier");
System.out.println(deque.pop()); // affiche le Premier
System.out.println(deque.pollLast()); // affiche le Dernier

En gros, si vous voulez un ordre d’éléments dans une collection, vous pouvez utiliser PriorityQueue, si vous voulez un accès rapide aux éléments du début et de la fin de la collection, vous pouvez utiliser ArrayDeque.

PriorityQueue<Task> tasks = new PriorityQueue<>();
tasks.add(new Task("Tâche 1", Priority.HIGH));
tasks.add(new Task("Tâche 2", Priority.MEDIUM));
tasks.add(new Task("Tâche 3", Priority.LOW));

Task task = tasks.poll();
System.out.println("Tâche en tête de file : " + task.getName()); // affiche : Tâche en tête de file : Tâche 1

Ci-dessus, on crée une file d’attente de tâches avec des priorities différentes avec la méthode poll() qui récupére la tâche de plus haute priority et la supprimer de la file d’attente. philippe.bouget@laposte.net comment la méthode poll() supprime l’élément ?

La méthode poll() de PriorityQueue et ArrayDeque supprime et renvoie l’élément en tête de la file. Cela signifie que c’est l’élément qui a la priorité la plus élevée dans la file de priorité (PriorityQueue) ou l’élément en tête de la file (ArrayDeque) qui est supprimé !

PriorityQueue est basé sur l’ordre naturel de ses éléments (si aucun comparateur n’est spécifié) ou sur le comparateur spécifié lors de sa création.

Pour ArrayDeque, cela supprime l’élément de tête de la file.

Exemple :

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(5);
pq.offer(3);
pq.offer(1);
pq.offer(4);
pq.offer(2);
int element = pq.poll();
System.out.println("l'element en tête de file est : " + element);

Ci-dessus, l’élément en tête de file est 1 qui est supprimé de la file.

ArrayDeque<Integer> arrayDeque = new ArrayDeque<>();
arrayDeque.add(5);
arrayDeque.add(3);
arrayDeque.add(1);
int element = arrayDeque.poll();
System.out.println("l'element en tête de file est : " + element);

Ci-dessus, l’élément en tête de file est 5 qui est supprimé de la file.

Conclusion

En conclusion, les collections en Java offrent une variété d’options pour stocker et organiser les données de différentes manières en fonction de vos besoins, et il est important de comprendre leurs différentes fonctionnalités et utilisations pour choisir la meilleure option pour votre application !