Collections Java : ArrayList, LinkedList, HashSet – Structures dynamiques et algorithmes

public class Personne {

private int cin, age;

private String Nom, Prenom;

Personne(int c, String n, String

p, int a){

cin=c;

Nom=n;

Prenom=p;

age=a;

}

public void afficher(){

CIN:

System.out.println(”Le

”+cin+” Le nom: ”+Nom+”

Le

”+Prenom+

prenom:

”L’age: ”+age); }

}

Chapitre 5 - Les collections, M. Chebbah

Introduction

Les collections

Les HashMaps

public static void main(String[]

args) {

ArrayList ăPersonneą A1=new

ArrayList ăPersonneą();

Per-

p1=new

Personne

sonne(12345678,”Salah”,”Mohamed”,23);

A1.add(p1);

ArrayList ăPersonneą A2=new

ArrayList ăPersonneą (A1);

A1.remove(0);

A2.get(0).afficher();

}

Semestre 1, 2020

8/29

LinkedList: construction

Introduction

Les collections

Les HashMaps

§ Listes doublement chaˆın´ees

§ D´eclaration / construction

§ LinkedListăEą l1 = new LinkedListăEą (); // liste vide

§ LinkedListăEą l2 = new LinkedListăEą (l1); /* liste

contenant tous les ´el´ements de la collection c */

§ Exemple:

LinkedList ăPersonneą L1=new LinkedList ăPersonneą();

LinkedList ăPersonneą L2=new LinkedList

ăPersonneą(L1);//L2 contient les mˆemes ´el´ements que L1

Chapitre 5 - Les collections, M. Chebbah

Semestre 1, 2020

9/29

LinkedList: Ajout, acc`es et suppr´ession

Introduction

Les collections

Les HashMaps

§ Ajout d’un ´el´ement elem de type E au d´ebut / fin de la liste

§ l1.addFirst(elem);

§ l1.addLast(elem);

§ Acc`es au premier / dernier ´el´ement de la liste

§ E elem = l1.getFirst();

§ elem = l1.getLast();

§ Suppression du premier / i`eme / dernier ´el´ement

§ l1.remove();

§ elem = l1.removeFirst();

§ elem = l1.remove(i);

§ elem = l1.removeLast();

Chapitre 5 - Les collections, M. Chebbah

Semestre 1, 2020

10/29

Exemple

Introduction

Les collections

Les HashMaps

public static void main(String[] args){

LinkedList ăPersonneą L1=new LinkedList ăPersonneą();

Personne p1=new Personne(12345678,”Salah”,”Mohamed”,23);

Personne p2=new Personne(23416789,”Ali”,”Mohamed”,24);

Personne p3=new Personne(98765436,”Tounsi”,”Mohamed”,32);

L1.add(p1);

L1.addFirst(p2);

L1.add(1,p3);

LinkedList ăPersonneą L2=new LinkedList ăPersonneą(L2);

L2.remove(1);

L2.getFirst().afficher();

L2.getLast().afficher();

}

Chapitre 5 - Les collections, M. Chebbah

Semestre 1, 2020

11/29

Exemple

Introduction

Les collections

Les HashMaps

R´esultat de l’ex´ecution:

Le CIN: 23416789 Le nom: Ali Le prenom: Mohamed L’age: 24

Le CIN: 12345678 Le nom: Salah Le prenom: Mohamed L’age: 23

Chapitre 5 - Les collections, M. Chebbah

Semestre 1, 2020

12/29

LinkedList:Parcours

Introduction

Les collections

Les HashMaps

§ La liste peut ˆetre parcourue par un it´erateur bidirectionnel

ListIterator

IteratorăEą iter = l1.iterator() //iter d´esigne le d´ebut de

la liste

§ Avancer / reculer d’un ´el´ement et retourner l’´el´ement

§ e = iter.next();

§ e = iter.previous();

§ Ajout d’un ´el´ement `a la position courante

iter.add(elem); // si fin de liste: ajout `a la fin

§ Suppression de l’´el´ement `a la position courante

iter.remove(); // supprime le dernier ´el´ement retourn´e par

next ou previous

Chapitre 5 - Les collections, M. Chebbah

Semestre 1, 2020

13/29

Exemple

Introduction

Les collections

Les HashMaps

public static void main(String[] args) {

LinkedList ăPersonneą L1=new LinkedList ăPersonneą();

Personne p1=new Personne(12345678,”Salah”,”Mohamed”,23);

Personne p2=new Personne(23416789,”Ali”,”Mohamed”,24);

Personne p3=new Personne(98765436,”Tounsi”,”Mohamed”,32);

L1.add(p1);

L1.addFirst(p2);

L1.add(1,p3);

Iterator ăPersonneą iter=L1.iterator();

while(iter.hasNext()){

iter.next().afficher();

}

}

Chapitre 5 - Les collections, M. Chebbah

Semestre 1, 2020

14/29

Exemple

Introduction

Les collections

Les HashMaps

R´esultat de l’ex´ecution:

Le CIN: 23416789 Le nom: Ali Le prenom: Mohamed L’age: 24

Le CIN: 98765436 Le nom: Tounsi Le prenom: Mohamed L’age: 32

Le CIN: 12345678 Le nom: Salah Le prenom: Mohamed L’age: 23

Chapitre 5 - Les collections, M. Chebbah

Semestre 1, 2020

15/29

Les ensembles: HashSet (et TreeSet)

Introduction

Les collections

Les HashMaps

§ Un ensemble est une collection non ordonn´ee d’´el´ements de

type E, aucun ´el´ement ne peut apparaˆıtre plus d’une fois dans

un ensemble

§ Probl`eme: comme deux objets distincts ont des r´ef´erences

diff´erentes, on ne pourra jamais avoir deux objets ´egaux mˆeme

si toutes leurs valeurs sont identiques -ą Il faudra d´efinir un

comparateur qui sera capable de tester l’´egalit´e de deux objets

(equals et compareTo)

Chapitre 5 - Les collections, M. Chebbah

Semestre 1, 2020

16/29

Les ensembles: HashSet (et TreeSet)

Introduction

Les collections

Les HashMaps

§ L’utilisateur devra d´efinir, pour l’utilisation d’un:

§ HashSet -ą les m´ethodes hashCode et equals dans la classe

des ´el´ements E

§ TreeSet -ą la m´ethode compareTo dans la classe E

§ Exemple:

public class Personne {

private int cin, age;

private String Nom, Prenom;

String n,

Personne(int

c,

String p, int a){

cin=c;

Nom=n;

Prenom=p;

age=a;

}

Chapitre 5 - Les collections, M. Chebbah

public void afficher(){

System.out.println(”Le

CIN:

”+cin+” Le nom: ”+Nom+”

”+Prenom+

prenom:

Le

”L’age: ”+age); }

public int hashCode(){

return

Nom.hashCode()+Prenom.hashCode();

}

}

Semestre 1, 2020

17/29

HashSet: m´ethodes usuelles

Introduction

Les collections

Les HashMaps

§ contains: test d’appartenance

boolean appartient = e.contains(elem); // elem

appartient-il `a e ?

§ remove: suppression d’un ´el´ement

boolean trouve = e.remove(elem); //false si elem

n’appartient pas `a e

Chapitre 5 - Les collections, M. Chebbah

Semestre 1, 2020

18/29

HashSet: parcours

Introduction

Les collections

Les HashMaps

§ Parcours `a l’aide d’un it´erateur

HashSetăEą e = new HashSetăEą (); // ajouts

d’´el´ements `a l’ensemble

Iterator ăEą iter = e.iterator();

while (iter.hasNext()) {

E elem = iter.next();

System.out.println(elem);

}

§ Remarques

§ Les ´el´ements d’un ensemble n’´etant pas ordonn´ees, aucun

ordre d’it´eration n’est assur´e

§ L’ordre d’it´eration peut varier dans le temps

Chapitre 5 - Les collections, M. Chebbah

Semestre 1, 2020

19/29

Exemple

Introduction

Les collections

Les HashMaps

public static void main(String[] args) {

HashSet ăPersonneą hset=new HashSet ăPersonneą();

Personne p1=new Personne(12345678,”Salah”,”Mohamed”,23);

Personne p2=new Personne(23416789,”Ali”,”Mohamed”,24);

Personne p3=new Personne(98765436,”Tounsi”,”Mohamed”,32);

hset.add(p1);

hset.add(p2);

hset.add(p3);

Iterator ăPersonneą iter=hset.iterator();

while(iter.hasNext()){

iter.next().afficher();

}

}

Chapitre 5 - Les collections, M. Chebbah

Semestre 1, 2020

20/29

Introduction aux fonctions (Map)

Introduction

Les collections

Les HashMaps

§ Les collections de type fonction (map) ou tableau associatif

en Java, sont d´efinies `a partir de la racine Interface Map ăK,

Vą (et non Collection ăEą )

§ Une Map est un ensemble de paires d’objets, chaque paire

associant un objet de l’ensemble de d´epart K `a un objet de

l’ensemble d’arriv´ee V ; on parle de paires (cl´e, valeur)

§ Application: chaque fois qu’il faut retrouver une valeur en

fonction d’une cl´e. Exemple: dans un dictionnaire: mot -ą

d´efinition du mot; dans un annuaire: nom de personne -ą

adresse et n˚de t´el; localisation: avion -ą a´eroport, etc.

Chapitre 5 - Les collections, M. Chebbah

Semestre 1, 2020

21/29

Introduction aux fonctions (Map)

Introduction

Les collections

Les HashMaps

§ Les classes Map: AbstractMap, AuthProvider,

ConcurrentHashMap, ConcurrentSkipListMap, EnumMap,

HashMap, Hashtable, IdentityHashMap, LinkedHashMap,

Provider, RenderingHints, SimpleBindings,

TabularDataSupport, TreeMap, UIDefaults, WeakHashMap

§ Nous verrons: HashMap

Chapitre 5 - Les collections, M. Chebbah

Semestre 1, 2020

22/29

Les fonctions (map): HashMap

Introduction

Les collections

Les HashMaps

§ Fonction (Map ) = ensemble de paires (cl´e, valeur)

§ Notion proche de la fonction au sens math´ematique

§ En informatique, la fonction est aussi appel´ee tableau

associatif ou encore dictionnaire

§ En Java, les collections de type fonction, sont d´efinies `a partir

de la racine Interface Map ăK, Vą

§ Techniquement r´ealis´e par une table de hachage sur le

domaine des cl´es

§ Tout comme pour un HashSet, l’utilisateur doit d´efinir les

m´ethodes hashCode et equals dans la classe des cl´es K

§ Remarque: si K est String, hashCode et equals sont d´ej`a

d´efinies dans la classe String -ą l’utilisateur n’a pas besoin de

les d´efinir

Chapitre 5 - Les collections, M. Chebbah

Semestre 1, 2020

23/29

HashMap: construction

et m´ethodes usuelles

Introduction

Les collections

Les HashMaps

§ D´eclaration / construction:

HashMap ăK, Vą m = new HashMap ăK, Vą (); //

map vide

Exemple: HashMap ăString,Integerą m = new HashMap

ăString,Integerą();

§ put: ajout d’une paire (ou mise `a jour de la valeur si la cl´e

existe)

// map vide

Exemple: m.put(cle, val); // o`u cl´e objet de type K, val

objet de type V

§ Cas particulier: val peut ˆetre de type primitif int, float, char,

. . .

Exemple: m.put(”occiden”, 1);

Chapitre 5 - Les collections, M. Chebbah

Semestre 1, 2020

24/29

HashMap: construction

et m´ethodes usuelles (2/2)

Introduction

Les collections

Les HashMaps

§ get: r´ecupere la valeur associ´ee a une cl´e.

Exemple:

String cle = ”occident”;

Integer val = m.get(cle);

if (val == null) System.out.println(”cette cl´e n’existe pas !

”);

§ remove: suppression d’une paire en fonction de la cl´e.

Exemple:

§ m.remove(cle); // supprime la paire (”occident” , val )

§ Integer val = m.remove(cle); // retourne la valeur, null

”occident”

Chapitre 5 - Les collections, M. Chebbah

Semestre 1, 2020

25/29

HashMap: parcours

Introduction

Les collections

Les HashMaps

§ En th´eorie une map ne dispose pas d’it´erateur

§ En pratique, on utilise la m´ethode entrySet() d´efine dans la

classe HashMap pour cr´eer un ensemble `a partir du map

(l’ensemble des paires du map); puis on cr´ee un it´erateur sur

cet ensemble:

HashMap ăK, Vą m = new HashMap ăK, Vą ();

Set ăMap.EntryăK,Vąą paires = m.entrySet(); //

ensemble de paires

Iterator ăMap.EntryăK,Vąą iter = paires.iterator(); //

it´erateur

while (iter.hasNext()) {

Map.Entry ăK, Vą paire = iter.next(); // paire courante

System.out.println(paire); // affichage de la paire courante

K cle = paire.getKey(); // acces a la cl´e

V val = paire.getValue(); // acces a la valeur

}

Chapitre 5 - Les collections, M. Chebbah

Semestre 1, 2020

26/29

Exemple

Introduction

Les collections

Les HashMaps

import java.util.*; // HashMap, Map, Iterator, Set

public class HashMapDemo{

public static void main(String args[]) {

/ D´eclaration du HashMap persAge /

HashMapăString, Integerą persAge = new HashMapăString,

Integerą();

/ Ajouter des entr´ees dans le HashMap persAge/

persAge.put(”Myriam”, 28);

persAge.put(”Malek”, 33);

persAge.put(”Mohamed”, 45);

Chapitre 5 - Les collections, M. Chebbah

Semestre 1, 2020

27/29

Exemple

Introduction

Les collections

Les HashMaps

/ Afficher le contenu de persAge en utilisant un it´erateur /

Set paires = persAge.entrySet(); // cr´ee en ensemble de paires `a

partir du HashMap

Iterator ăMap.EntryăString,Integerąą iter = paires.iterator();

while (iter.hasNext()) {

Map.Entry paire = iter.next();

System.out.println( paire.getKey() + ” ˆage ” + paire.getValue());

}

/ Retrouver une valeur en donnant la cl´e / System.out.println(

”Myriam a ” + persAge.get( ”Myriam”) + ” ans”);

/ Mettre a jour la valeur associ´ee a une cl´e /

persAge.put(”Mohamed”, 40);

Chapitre 5 - Les collections, M. Chebbah

Semestre 1, 2020

28/29

Exemple

Introduction

Les collections

Les HashMaps

System.out.println( ”Mohamed a rajeuni ! Nouvel ˆage: ” +

persAge.get(”Mohamed”));

/ Supprimer une entr´ee /

persAge.remove(”Mohamed”); // Mohamed est mort . . .

}

}

Chapitre 5 - Les collections, M. Chebbah

Semestre 1, 2020

29/29