Les collections génériques en Java

L’interface List (1)

Cette interface, ajoutée à Java 1.2,

étend l'interface Collection.

Pour simplifier, les objets de type

List sont des tableaux extensibles à

volonté.

Pas de crainte de débordement.

vous pouvez récupérer les

éléments de la liste via leurs indices.

Anissa CHALOUAH

17

L’interface List(2)

List est une collection ordonnée d’objets qui permet :

de contenir des doublons

d'interagir avec un élément de la collection en utilisant sa

position (indice)

d'insérer des éléments null

Pour les listes, une interface particulière est définie

pour permettre le parcours dans les deux sens de la

liste et réaliser des mises à jour : l'interface

ListIterator

Anissa CHALOUAH

18

L’interface List : Méthodes

Méthode

void add(int index, E e)

E get(int index)

int indexOf(Object o)

int lastIndexOf(Object o)

Rôle

Ajouter un élément à la position fournie en paramètre

Retourner l'élément à la position fournie en paramètre

Retourner la première position dans la liste du premier élément fourni en paramètre.

Elle renvoie -1 si l'élément n'est pas trouvé

Retourner la dernière position dans la liste du premier élément fourni en paramètre.

Elle renvoie -1 si l'élément n'est pas trouvé

ListIterator<E> listIterator()

Renvoyer un Iterator positionné sur le premier élément de la liste

ListIterator<E> listIterator(int indx)

Renvoyer un Iterator positionné sur l'élément dont l'index est fourni en paramètre

E remove(int index)

E set(int index, E e)

List<E> subList(int fromIndex, int

toIndex)

Supprimer l'élément à la position fournie en paramètre

Remplacer l'élément à la position fournie en paramètre

Obtenir une liste partielle de la collection contenant les éléments compris entre les

index fromIndex inclus et toIndex exclus fournis en paramètres

Anissa CHALOUAH

19

La classe ArrayList<E>

ArrayList<E> est un tableau dynamique : la taille

(nombres d’éléments) du tableau n’est pas fixe et peut

varier en cours d’exécution

Une instance de la classe ArrayList<E> est une sorte de

tableau qui peut contenir un nombre quelconque

d’instances d’une classe E

Comme pour un tableau l’accès à ses éléments est direct.

Les emplacements sont indexés par des nombres entiers

(à partir de 0)

Anissa CHALOUAH

20

La classe ArrayList<E> : Constructeurs

Constructeur

ArrayList()

ArrayList(Collection<? extends E> c)

ArrayList(int initialCapacity)

Rôle

Créer une instance vide de la collection avec une capacité initiale de 10

Créer une instance contenant les éléments de la collection fournie en paramètre dans l'ordre

obtenu en utilisant son iterator

Créer une instance vide de la collection avec la capacité initiale fournie en paramètre

ArrayList <Personne> l1 = new ArrayList<>();

ArrayList <Personne> l2 = new ArrayList<>(5);

ArrayList <Personne> l3=new ArrayList<>(l1);

Anissa CHALOUAH

21

La classe ArrayList<E> : Méthodes

Méthode

boolean add(E elt)

void add(int indice, E elt)

E get(int indice)

int indexOf(Object obj)

Iterator<E> iterator()

E remove(int indice)

E set(int indice, E elt)

int size()

Rôle

Ajouter un élément à la fin du tableau

Ajouter un élément à l’indice passé en paramètre

Renvoyer l'élément du tableau dont la position est précisée

Renvoyer la position de la première occurrence de l'élément fourni en

paramètre

Renvoyer un itérateur sur le tableau

Supprimer dans le tableau l'élément fourni en paramètre

Remplacer l'élément à la position indiquée par celui fourni en paramètre

Renvoyer le nombre d'éléments du tableau

Anissa CHALOUAH

22

La classe ArrayList<E> : Exemple(1)

ArrayList <Personne> l1 = new ArrayList<>();

l1.add(new Personne(1234,"amri","Salah"));

l1.add(new Personne(5678,"mekni","mohamed"));

System.out.println("\n * Parcours liste 1 avec une bouble for *");

for(int i=0;i<l1.size();i++)

System.out.println(l1.get(i));

* Parcours liste 1 avec une bouble for *

Personne [cin=1234, nom=amri, prenom=Salah]

Personne [cin=5678, nom=mekni, prenom=mohamed]

Anissa CHALOUAH

23

La classe ArrayList<E> : Exemple (2)

ArrayList <Etudiant> l2 = new ArrayList<>(5);

l2.add(new Etudiant(5555,"Toki","Sarra","DSI",2));

l2.add(new Etudiant(3333,"Jmili","Houda","RSI",3));

System.out.println("\n * Parcours liste 2 avec bouble for each*");

for (Personne p : l2)

System.out.println(p);

* Parcours liste 2 avec une bouble for each*

Etudiant [filiere=DSI, niveau=2, toString()=Personne [cin=5555, nom=Toki, prenom=Sarra]]

Etudiant [filiere=RSI, niveau=3, toString()=Personne [cin=3333, nom=Jmili, prenom=Houda]]

Anissa CHALOUAH

24

La classe ArrayList<E> : Exemple (3)

ArrayList <Personne> l3=new ArrayList<>(l1);

System.out.println("Taille liste 3 = "+l3.size());

System.out.println("\n * Parcours liste 3 avec un itérateur *");

Iterator<Personne> i3=l3.iterator();

while (i3.hasNext()){

System.out.println(i3.next());

Taille liste 3 = 2

* Parcours de la liste 3 avec un itérateur *

Personne [cin=1234, nom=amri, prenom=Salah]

Personne [cin=5678, nom=mekni, prenom=mohamed]

Anissa CHALOUAH

25

import java.util.ArrayList;

import java.util.Collections;

import java.util.List;

import java.util.ListIterator;

public class ArrayListExemple2 {

public static void main(String[] args) {

List<String> list = new

ArrayList<String>();

list.add("a");

list.add("b");

list.add("c");

list.add("d");

list.add("e");

list.add("f");

//On récupère une sous-liste

List<String> sub = list.subList(2, 5);

System.out.println(sub);

Collections.reverse(sub);

System.out.println(sub);

//On récupère un ListIterator

ListIterator<String> it = list.listIterator

while(it.hasNext()){

String str = it.next();

if(str.equals("d"))

it.set("z");

}

while(it.hasPrevious())

System.out.print(it.previous());

//On met la liste dans le désordre

Collections.shuffle(list);

System.out.println(list);

}

}

//On la remet dans l'ordre

Collections.sort(list);

System.out.println(list);

Collections.rotate(list, -1);

System.out.println(list);

[b, d, f, e, a, c]

[a, b, c, d, e, f]

[b, c, d, e, f, a]

[d, e, f]

[f, e, d]

azefcb

La classe LinkedList <E>

La classe LinkedList est une implémentation d'une liste doublement chaînée dans

laquelle les éléments de la collection sont reliés par des pointeurs.

La liste peut être parcourue par un itérateur bidirectionnel ListIterator

la classe LinkedList se prête bien à l’implémentation des collections ordonnées, c’est-

à-dire

pile

queue (file d’attente)

séquence

Anissa CHALOUAH

27

La classe LinkedList <E> : Constructeurs

Constructeur

LinkedList()

LinkedList(Collection<? extends E> c)

Rôle

Créer une nouvelle instance vide

Créer une nouvelle instance contenant les éléments de la collection fournie en paramètre triés

dans l'ordre obtenu par son Iterator

LinkedList <String> ll = new LinkedList<>();

ll.add("element 1");

ll.add("element 2");

ll.add("element 3");

Iterator<String> iterator = ll.iterator();

while (iterator.hasNext()) {

System.out.println("objet = "+iterator.next());

objet = element 1

objet = element 2

objet = element 3

}

Anissa CHALOUAH

28

La classe LinkedList <E> : Méthodes

Méthode

void addFirst(Object)

void addLast(Object)

Object getFirst()

Object getLast()

Object removeFirst()

Object removeLast()

Rôle

Insèrer l'objet au début de la liste

Insèrer l'objet à la fin de la liste

Renvoyer le premier élément de la liste

Renvoyer le dernier élément de la liste

Supprimer le premier élément de la liste et renvoie l'élément qui est devenu le premier

Supprimer le dernier élément de la liste et renvoie l'élément qui est devenu le dernier

Anissa CHALOUAH

29

La classe LinkedList <E> : itérateur ListIterator

L'interface ListIterator définit des fonctionnalités d'un Iterator permettant aussi le

parcours en sens inverse de la collection, l'ajout d'un élément ou la modification du

courant.

Anissa CHALOUAH

30

La classe LinkedList <E> : itérateur ListIterator

En plus des méthodes définies dans l'interface Iterator dont elle hérite, l'interface

ListIterator définit plusieurs méthodes :

Méthode

Rôle

void add(E e)

Ajouter un élément dans la collection

boolean hasPrevious()

Retourner true si l'élément courant possède un élément précédent

int nextIndex()

E previous()

Retourner l'index de l'élément qui serait retourné en invoquant la méthode next()

Retourner l'élément précédent dans la liste

int previousIndex()

Retourner l'index de l'élément qui serait retourné en invoquant la méthode previous()

void set(E e)

Remplacer l'élément courant par celui fourni en paramètre

Anissa CHALOUAH

31

La classe LinkedList <E> : Exemple

LinkedList<Integer> list=new LinkedList<Integer>();

list.add(1);

list.add(2);

list.add(3);

list.add(9);

list.add(5);

Iterator<Integer> iterator = list.iterator();

while (iterator.hasNext()) {

System.out.print(" "+iterator.next());

}

System.out.println();

ListIterator<Integer> li=list.listIterator();

while (li.hasNext()){

if (li.next()==9)li.set(4);}

list.addFirst(0);

list.addLast(10);

for(int i=0;i<list.size();i++)

System.out.print(" "+list.get(i));

1 2 3 9 5

0 1 2 3 4 5 10

Anissa CHALOUAH

32

Les collections de type Set :

les ensembles

Anissa CHALOUAH

33

Les ensembles : L’interface Set

Un ensemble est une collection non ordonnée d’éléments de type E, aucun élément ne

peut apparaître plus d’une fois dans un ensemble

Problème: comme deux objets distincts ont des références différentes, on ne pourra

jamais avoir deux objets égaux même si toutes leurs valeurs sont identiques -> Il faudra

définir un comparateur qui sera capable de tester l’égalité de deux objets (equalset

compareTo)

L’utilisateur devra définir, pour l’utilisation d’un

HashSet -> les méthodes hashCodeet equalsdans la classe des éléments E

TreeSet -> la méthode compareTodans la classe E

Anissa CHALOUAH

34

Méthode

boolean add(E e)

Rôle

Ajouter l'élément fourni en paramètre à la collection si celle-ci ne le contient pas déjà et renvoyer un

booléen qui précise si la collection a été modifiée (l'implémentation de cette opération est

optionnelle)

boolean equals(Object o)

int hashCode()

Iterator<E> iterator()

boolean remove(Object o)

int size()

Object[] toArray()

<T> T[] toArray(T[] a)

Anissa CHALOUAH

Comparer l'égalité de la collection avec l'objet fourni en paramètre. L'égalité est vérifiée si l'objet

est de type Set, que les deux collections ont le même nombre d'éléments et que chaque élément

d'une collection est contenu dans l'autre

Retourner la valeur de hachage de la collection

Renvoyer un Iterator sur les éléments de la collection

Retirer l'élément fourni en paramètre de la collection si celle-ci le contient et renvoyer un booléen

qui précise si la collection a été modifiée (l'implémentation de cette opération est optionnelle)

Renvoyer le nombre d'éléments de la collection. Si ce nombre dépasse Integer.MAX_VALUE alors la

valeur retournée est MAX_VALUE

Renvoyer un tableau des éléments de la collection

Renvoyer un tableau des éléments de la collection dont le type est celui fourni en paramètre

35

L’interface SortedSet

L'interface SortedSet, ajoutée à Java 1.2, définit les

fonctionnalités pour une collection de type Set qui

garantit l'ordre ascendant du parcours de ses

éléments.

Anissa CHALOUAH

36

L’interface SortedSet

Méthode

Rôle

E first()

E last()

SortedSet headSet(E toElement)

SortedSet tailSet(E fromElement)

SortedSet subSet(E fromElement, E toElement)

Comparator< ? super E> comparator()

Retourner le premier élément de la collection

Retourner le dernier élément de la collection

Retourner un sous-ensemble des premiers éléments de la collection jusqu'à l'élément fourni

en paramètre exclus

Retourner un sous-ensemble contenant les derniers éléments de la collection à partir de

celui fourni en paramètre inclus

Retourner un sous-ensemble des éléments dont les bornes sont ceux fournis en

paramètres. fromElement est inclus et toElement est exclus. Si les deux éléments fournis en

paramètres sont les mêmes, la méthode renvoie une collection vide

Renvoyer l'instance de type Comparator associée à la collection ou null s'il n'y en a pas

Anissa CHALOUAH

37

La classe HashSet

La classe HashSet, ajoutée à Java 1.2, est une

implémentation simple de l'interface Set .

La classe HashSet présente plusieurs

caractéristiques :

elle ne propose aucune garantie sur l'ordre de

parcours lors de l'itération sur les éléments

qu'elle contient

elle ne permet pas d'ajouter des doublons mais

elle permet l'ajout d'un élément null

Anissa CHALOUAH

38

La classe HashSet : Exemple

import java.util.HashSet;

import java.util.Iterator;

public class HashSetExemple {

public static void main(String[] args) {

HashSet set = new HashSet();

set.add("CCCCC");

set.add("BBBBB");

set.add("DDDDD");

set.add("BBBBB");

set.add("AAAAA");

Iterator iterator = set.iterator();

while (iterator.hasNext()) {

System.out.println(iterator.next());

}

}

}

Anissa CHALOUAH

BBBBB

AAAAA

DDDDD

CCCCC

39

La classe TreeSet

La classe TreeSet, ajoutée à Java 1.2, stocke ses

éléments de manière ordonnée en les comparant entre-

eux.

Cette classe permet d'insérer des éléments dans

n'importe quel ordre et de restituer ces éléments dans

un ordre précis lors de son parcours.

Une collection de type TreeSet ne peut pas contenir de

doublons.

TreeSet garantit que les éléments sont rangés dans

leur ordre naturel (interface Comparable) ou l'ordre

d'un Comparator.

Anissa CHALOUAH

40

La classe TreeSet : Exemple

import java.util.Iterator;

import java.util.TreeSet;

public class TreeSetExemple {

public static void main(final String[] args) {

TreeSet<String> set = new TreeSet<String>();

set.add("CCCCC");

set.add("BBBBB");

set.add("DDDDD");

set.add("BBBBB");

set.add("AAAAA");

Iterator<String> iterator = set.iterator();

while (iterator.hasNext()) {

System.out.print(iterator.next() + " ");

}

}

}

Anissa CHALOUAH

AAAAA BBBBB CCCCC DDDDD

41

Les collections de type Map : les

associations de type clé/valeur

Anissa CHALOUAH

42

Les collections de type Map

Les collections de type Map sont définies et implémentées comme des dictionnaires sous

la forme d'associations de paires de type clés/valeurs.

La clé doit être unique. En revanche, la même valeur peut être associée à plusieurs clés

différentes.

Avant l'apparition du framework Collections, la classe dédiée à cette gestion était la

classe Hashtable.

Un objet de type Map permet de lier un objet avec une clé qui peut être un type

primitif ou un autre objet.

Il est ainsi possible d'obtenir un objet à partir de sa clé.

Anissa CHALOUAH

43

L'interface Map<K,V>

L'interface java.util.Map<K,V> , ajoutée à Java 1.2, définit les

fonctionnalités pour une collection qui associe des clés à des

valeurs.

Chaque clé ne peut être associée qu'à une seule valeur. Chaque

clé d'une Map doit être unique.

Le langage vous propose trois implémentations de bases :

HashMap<K,V> : implémentation utilisant une table de hachage pour

stocker ses éléments;

TreeMap<K,V> : implémentation qui stocke les éléments triés, de façon

naturelle par défaut, mais utilisable avec un comparateur ;

LinkedHashMap<K,V> : implémentation qui combine table de hachage

et liens chaînés pour stocker ses éléments, ce qui facilite leur insertion

et leur suppression.

Anissa CHALOUAH

44

L'interface Map<K,V> : Méthodes

Méthode

void clear()

boolean containsKey(Object)

boolean containsValue(Object)

Set entrySet()

Object get(Object)

boolean isEmpty()

Set keySet()

Object put(Object, Object)

Object remove(Object)

int size()

Anissa CHALOUAH

Rôle

Supprimer tous les éléments de la collection

Indiquer si la clé est contenue dans la collection

Indiquer si la valeur est contenue dans la collection

Renvoyer un ensemble contenant les paires clé/valeur de la collection

Renvoyer la valeur associée à la clé fournie en paramètre

Indiquer si la collection est vide

Renvoyer un ensemble contenant les clés de la collection

Insèrer la clé et sa valeur associée fournies en paramètres

Supprimer l'élément dont la clé est fournie en paramètre

Renvoyer le nombre d'éléments de la collection

45

Parcours d’un Map<K,V>

Une collection de type Map ne propose pas directement d'Iterator sur ses

éléments.

la collection peut être parcourue de trois manières :

parcours de l'ensemble des clés : méthode keySet()

parcours des valeurs : méthode values()

parcours d'un ensemble de paires clé/valeur : interface interne Map.Entry<K,V>

Anissa CHALOUAH

46

Parcours des clés : méthode keySet()

La méthode keySet() permet d'obtenir un ensemble contenant toutes les clés.

Map<Integer, String> hm = new HashMap<>();

hm.put(10, "1");

hm.put(20, "2");

hm.put(30, "3");

hm.put(40, "4");

hm.put(50, "5");

//Ceci va écraser la valeur 5

hm.put(50, "6");

Set s= hm.keySet();

Iterator i1=s.iterator();

while(i1.hasNext())

System.out.println (i1.next());

50

20

40

10

30

Anissa CHALOUAH

47

Parcours des valeurs : méthode values()

La méthode values() permet d'obtenir une collection contenant toutes les valeurs.

La valeur de retour est une Collection et non un ensemble car il peut y avoir des

doublons (plusieurs clés peuvent être associées à la même valeur).

Map<Integer, String> hm = new HashMap<>();

hm.put(10, "1");

hm.put(20, "2");

hm.put(30, "3");

hm.put(40, "4");

hm.put(50, "5");

//Ceci va écraser la valeur 5

hm.put(50, "6");

Collection c=hm.values();

Iterator i1=c.iterator();

while(i1.hasNext())

System.out.print (" "+i1.next());

6 2 4 1 3

Anissa CHALOUAH

48

parcours d'un ensemble de paires clé/valeur

La méthode entrySEt () retourne une collection de type Set qui sera définit ainsi

Set<Entry<k,v>>.

Ce sera donc une collection d’objets qui contiendra tous les couples clé-valeur de notre

Map.

Cet objet est une classe interne à l’interface Map et contient quelques méthodes utiles

pour récupérer les informations.

Anissa CHALOUAH

49

parcours d'un ensemble de paires clé/valeur

Interface interne Entry<K,V> de Map

L’interface Map<K,V> contient l’interface interne public Map.Entry<K,V> qui correspond

à un couple clé-valeur

Cette interface contient 3 méthodes

K getKey()

V getValue()

V setValue(V valeur)

La méthode entrySet() de Map renvoie un objet de type « ensemble (Set) de Entry »

Anissa CHALOUAH

50

Interface interne Entry<K,V> de Map : Exemple

Map<Integer, String> hm = new HashMap<>();

System.out.println("Parcours de l'objet HashMap : ");

Set<Entry<Integer, String>> setHm = hm.entrySet();

Iterator<Entry<Integer, String>> it = setHm.iterator();

while(it.hasNext()){

Entry<Integer, String> e = it.next();

System.out.println(e.getKey() + " : " + e.getValue());

}

System.out.println("Valeur pour la clé 8 : " + hm.get(8));

50 : 6

20 : 2

40 : 4

10 : 1

30 : 3

Valeur pour la clé 8 : null

Anissa CHALOUAH

51

La classe HashMap & LinkedHashMap<K,V>

ces deux objets sont deux des plus utilisés. Ils travaillent sous forme de table de hachage

et leur principale différence réside dans le fait que LinkedHashMap gère en plus des liens

chaînés (vous avez deviné duquel je parle...), ce qui fait que ce dernier permet de

parcourir les éléments de la collection dans l'ordre d'insertion alors que HashMap ne le

permet pas

Anissa CHALOUAH

52

HashMap & LinkedHashMap<K,V> : Exemple

Map<Integer, String> lhm = new LinkedHashMap<>();

lhm.put(10, "1");

lhm.put(20, "2");

lhm.put(30, "3");

lhm.put(40, "4");

lhm.put(50, "5");

System.out.println("Parcours de l'objet LinkedHashMap : ");

Set<Entry<Integer, String>> setLhm = lhm.entrySet();

Iterator<Entry<Integer, String>> it2 = setLhm.iterator();

while(it2.hasNext()){

Entry<Integer, String> e = it2.next();

System.out.println(e.getKey() + " : " + e.getValue());

Parcours de l'objet LinkedHashMap :

10 : 1

20 : 2

30 : 3

40 : 4

50 : 5

Anissa CHALOUAH

53

Trie et Recherche dans une collection

Anissa CHALOUAH

54

Les classes utilitaires

Collections (avec un s final) fournit des méthodes static pour, en particulier,

trier une collection

faire des recherches rapides dans une collection triée

Arrays fournit des méthodes static pour, en particulier,

Trier,

faire des recherches rapides dans un tableau trié

transformer un tableau en liste

Anissa CHALOUAH

55

Travail à faire

Exposé sur la classe Collections+des exemples de tri de recherche…

Classe Arrays : Exemple de transformation de tableau en liste et de liste en tableau

Anissa CHALOUAH

56

Bibliographie

https://www.jmdoudoux.fr/java/dej/chap-collections.htm

https://openclassrooms.com/courses/java-et-les-collections

Les collections en Java, L. Nerima

Collections, Sophia Antipolis, Université de Nice

Collections dans Java, Olivier Curé

Anissa CHALOUAH

57