Java : les collections
Plan
• Introduction
• List
• ArrayList
• LinkedList
• Généricité et construction d’une liste
• Set
• HashSet
• LinkedHashSet
• TreeSet
• Map
• Hashtable
• HashMap
• Construction d’entrée et de map
• Remarques
JAVA
• Les collections, c’est quoi?
• sont des objets
• permettent de regrouper et gérer plusieurs objets
• Pourquoi ne pas utiliser les tableaux?
• Plusieurs raison
• Il faut connaitre à l’avance la taille du tableau
• Si on veut dépasser la taille déclarée, il faut créer un nouveau tableau puis copier
l’ancien (certains langages ont proposés l’allocation dynamique mais ça reste difficile à
manipuler)
• Il est difficile de supprimer ou d’ajouter un élément au milieu du tableau
• Il faut parcourir tout le tableau pour localiser un élément (problème d’indexation)
• Les tableaux ne peuvent contenir des éléments de type différent
JAVA
• Plusieurs types de collections proposés
• List : tableaux extensibles à volonté, accessibles via leurs indice ou valeur
• Set : collection qui n’accepte pas de doublons
• Map : collection qui exige une clé unique pour chaque élément
• Queue : collection gérée comme une file d’attente (FIFO : First In First Out)
• Tous les imports de ce chapitre sont de [Link].*;
JAVA- LIST
ArrayList
• Pas de limite de taille
• Possibilité de stocker tout type de données (y compris null)
• Pour créer un ArrayList
• ArrayList list = new ArrayList();
• Pour ajouter la valeur 3 à la liste
• [Link](3);
• Pour récupérer la taille de la liste
• [Link]([Link]()); // affiche 1
• Pour récupérer un élément de la liste
• [Link]([Link](0)) // affiche 3
Exemple avec ArrayList
Autres méthodes de ArrayList
• add(index,value) : insère value à la position d’indice index
• remove(index) : supprime l’ élément d’indice index de la liste (l’index doit
être de type primitif : int)
• remove(object) : supprime l’objet object de la liste
• removeAll() : supprime tous les éléments de la liste
• set(index, object) : remplace la valeur de l’ élément d’indice index de la
liste par object
• isEmpty() : retourne true si la liste est vide, false sinon.
• contains(object) : retourne true si object appartient à la liste, false sinon.
•…
Qu’affiche le programme suivant?
• 0 bonsoir
Exercices (1/3)
• Ecrire un programme Java qui
• demande à l’utilisateur de remplir une liste avec des nombres positifs de son
choix, il s’arrête à la saisie de zéro
• demande à l’utilisateur de saisir une valeur à supprimer de la liste
• supprime la première occurrence de cette valeur de la liste
• affiche la nouvelle liste (après suppression de la valeur demandée)
Exercices (2/3)
• Ecrire un programme Java qui
• demande à l’utilisateur de remplir une liste avec des nombres positifs de son
choix, il s’arrête à la saisie de zéro
• demande à l’utilisateur de saisir une valeur à supprimer de la liste
• supprime toutes les occurrences de cette valeur de la liste
• affiche la nouvelle liste (après suppression de la valeur demandée)
Exercices (3/3)
• Ecrire un programme Java qui
• demande à l’utilisateur de remplir une liste avec des nombres positifs de son
choix, il s’arrête à la saisie de zéro
• demande à l’utilisateur de saisir une valeur
• affiche les positions (de toutes les occurrences) de cette valeur dans cette
liste
ArrayList : Identifions problème
• Considérons le programme suivant
Solution : interface Iterator
• implémentée par la plupart des collections ayant les méthodes
suivantes
• permettant de parcourir une collection
• ayant les méthodes suivantes
• hasNext() : retourne true si l’itérateur contient d’autres éléments
• next() : retourne l’ élément suivant de l’itérateur
• remove() : supprime le dernier objet obtenu par next()
• …
ArrayList : Résolvons le problème précédent avec les
itérateurs
LinkedList (liste chaînée)
• C’est une liste dont chaque élément a deux références : une vers l’
élément précédent et la deuxième vers l’ élément suivant.
• Pour le premier élément, l’ élément précédent vaut null
• Pour le dernier élément, l’ élément suivant vaut null
Java – LinkedList - Exemple
Java – LinkedList
• Autres méthodes de LinkedList
• addFirst(object) : insère l’ élément object au début de la liste
• addLast(object) : insère l’ élément object comme dernier élément de la liste
(exactement comme add())
• Remarques
• On peut parcourir une liste chaînée avec un Iterator
• Un itérateur est un objet qui a pour rôle de parcourir une collection
LinkedList : parcours avec un itérateur
LinkedList : Qu’affiche le programme suivant?
JAVA - List
• On peut utiliser la généricité pour imposer un type à nos listes
• LinkedList<Integer> liste = new LinkedList<Integer>();
• Ou
• List<Integer> liste = new LinkedList<Integer>();
• La même chose pour ArrayList
• List<Integer> liste = new ArrayList<Integer>();
Convertir Tableau en List
• Considérons le tableau suivant
• Integer [] tab = { 2, 3, 5, 1, 9 };
• Pour convertir le tableau tab en liste
• List<Integer> liste = new LinkedList([Link](tab));
• Ou en plus simple
• List<Integer> ent = [Link](tab);
Convertir Tableau en List
• On peut le faire aussi sans création de tableau
• List<Integer> liste = [Link](2, 7, 1, 3);
• Ou
• List<Integer> liste = [Link](2, 7, 1, 3);
Exercice
• Etant donnée la liste suivante
• ArrayList<Integer> liste = new ArrayList([Link](2, 7, 2, 1, 3, 9, 2, 4, 2));
• Ecrire un programme Java qui permet de supprimer l’avant dernière
occurrence du chiffre 2 de la liste précédente
• Solution
• [Link]([Link](0,[Link](2)).lastIndexOf(2));
JAVA - SET
HashSet
• Collection utilisant une table de hachage
• Possibilité de parcourir ce type de collection avec un objet Iterator
• Possibilité d’extraire de cet objet un tableau d’Object
Exemple avec HashSet
Java - HashSet
• Les éléments ne sont pas ordonnés
• HashSet utilise une valeur de hachage (difficile à prédire) calculée pour
chaque élément.
• Cette valeur de hachage détermine l’indice de l’élément dans un tableau
conteneur.
• Ainsi, l’ordre des éléments insérés n’est naturellement pas conservé.
• Ceci permet d’accéder aux éléments souhaités avec une complexité O(1) en
temps (mais reste coûteux en espace).
• Remarques :
• Pour avoir un affichage ordonné selon l’ordre d’insertion, on peut utiliser
LinkedHashSet.
HashSet : exemple avec conversion en tableau
Exemple avec LinkedHashSet
TreeSet
• Possibilité de parcourir ce type de collection avec un objet Iterator
• Les éléments enregistrés sont automatiquement triés
Exemple avec TreeSet
TreeSet
• Les éléments ne sont pas ordonnés
• TreeSet ordonne les données insérées
• Elle n’accepte qu’un seul type.
MAP
Hashtable
• Hashtable fonctionne avec un couple (clé,valeur)
• Elle utilise une table de hachage
• Elle n’accepte pas la valeur null
• La clé doit être unique
• Pour la parcourir, on utilise l’objet Enumeration
Hashtable
Hashtable : put ajoute si la clé n’existe pas, modifie sinon.
Hashtable : Autres méthodes de la classe Hashtable
• isEmpty() retourne true si l’objet est vide, false sinon.
• contains(value) retourne true si la valeur existe dans la Hashtable,
false sinon
• containsKey(key) retourne true si la clé existe dans la Hashtable, false
sinon
• elements() retourne une énumération des éléments de l’objet
• keys() retourne la liste des clés sous forme d’ énumération
HashMap
• HashMap fonctionne aussi avec un couple (clé, valeur)
• Elle utilise aussi une table de hachage
• HashMap accepte la valeur null
• La clé doit être unique
• Pour la parcourir, on utilise un objet Set
Exemple avec HashMap
Pour afficher la clé et la valeur, on peut utiliser l’Entry
HashMap
Exercice
• Etant donnée la liste suivante :
• List list = [Link](2,5,"Bonjour",true,’c’,"3" ,"b",false,10);
• Ecrire un programme Java qui permet de stocker dans un dictionnaire
(Map) les types contenus dans la liste list ainsi que le nombre d’ éléments
de cette liste appartenant à chaque type.
• Résultat attendu :
• Integer=3
• Character=1
• String=3
• Boolean=2
HashMap
Construction d’entrée et de map
• Pour créer une entrée, on utilise la méthode entry()
• var x = [Link](3, "JavaScript");
• Pour créer une Map en utilisant plusieurs entrées prédéfinies
• var x = [Link](3, "JavaScript");
• var y = [Link](2, "HTML");
• var z = [Link](1, "CSS");
• Map<Integer, String> map = [Link](x,y,z);
• Pour afficher
• for (Entry<Integer, String> entry : [Link]()) {
[Link]([Link]() + " " + [Link]());
}
Pour créer une Map et l’initialiser, on peut
utiliser la méthode of
Remarques
Remarques
• ArrayList vs LinkedList
• ArrayList est plus rapide pour l’opération de recherche (get)
• LinkedList est plus rapide pour des opérations d’insertion et de suppression
• LinkedList utilise un chaînage double (deux pointeurs) d’où une consommation de
mémoire plus élevée.
• Remarques
• Map à utiliser lorsqu’on veut rechercher ou accéder à une valeur via une clé de
recherche
• Set à utiliser si on n’accepte pas de doublons dans la collection
• List accepte les doublons permet l’accès à un élément via son indice et les éléments
sont insérés dans l’ordre (pas forcément triés)
References
• Achref El Mouelhi
