Plan
Structures de données
Collections & Java
Interfaces
o Collection
o Set
o List
o Map
2
Structures de données
C'est l'organisation efficace d'un ensemble de
données, sous la forme de tableaux, de listes, piles,
files, arbres (binaire, n-are) ou graphes.
Efficacité réside :
o Quantité mémoire pour stocker les données
o le temps nécessaire pour réaliser des opérations
sur ces données.
3
Structure de données
Regroupe un ensemble d’objets : conteneur ou de
collection.
Possède un ensemble de fonctions qui permettent
de la parcourir et de gérer ses objets (Ajouter,
Supprimer, Modifier, Consulter) et de connaître
l'état de la structure.
4
Structures de données
Exemples :
5
Structures de données
Pour implémenter les structures de données :
(Accès direct , aléatoire)
o Les tableaux :
(Accès séquentiel
o Les structures chaînées
o Simuler une structure chaînée dans un tableau
6
Collections de Java : Histrorique
JDK 1.1 disposait de classes (Array, Stack, Vector)
JDK 1.2 propose un framework de collection
JDK 1.5 propose les collections génériques
7
Collections Framwork en java
Réparties en deux groupes:
o Interfaces
o Implémentations
8
Interfaces
Organisées dans deux arborescences :
9
Hiérarchie des Collection
10
Hiérarchie des Map
11
Interfaces
Collection : Ensemble d'objets où la duplication est autorisée
List : Ensemble d’objets indexés qui autorise la duplication.
Set : Ensemble d’objet qui n’autorise pas la duplication
(sans doublons). SortedSet est un Set trié.
Map : collection sous la forme clé/valeur. SortedMap est un
Map trié.
12
Implémentations
Le framework fournit les implémentations suivantes :
Set et Map Table de Hachage (HashSet/HashMap) ou
Arbre (TreeSet/TreeMap)
Liste Tableau (ArrayList) ou liste chaînée(LinkedList)
13
Interface Collection
Sur un seul
objet
Sur une
collection
Revenir aux
tableaux
14
Interface Iterator
L'interface collection est dotée d'une instance
d'une
classe qui implante l'interface Iterator. Outil utilisé
Vérifie s'il y a un élément qui suit.
pour la parcourir du début à la fin.
Pointe l'élément suivant
retirer l'élément courant
15
Interface List<T>
Liste est une collection ordonnée. Elle permet la
duplication des éléments.
L'interface est renforcée par des méthodes
permettant d'ajouter ou de retirer des éléments se
trouvant à une position donnée.
Elle permet aussi de travailler sur des sous listes.
On utilise le plus souvent des ArrayList sauf s'il y a
insertion d'élément(s) au milieu de la liste. Dans ce
cas il est préférable d'utiliser une LinkedList pour
éviter ainsi les décalages.
16
Interface List<T>
listes de fromIndex (inclus) à toIndex (non inclus)
17
Interface ListIterator
Vérifie s'il y a un élément qui suit.
pointer l'élément courant
retourne l'index de l'élément courant
18
Classe concrète : ArrayList<T>
class ArrayListDemo {
public static void main(String args[]) {
//création d'un array list
ArrayList<String> al = new ArrayList<String>();
[Link]("Taille initial de al: " + [Link]());
Output :
//ajout d'un élément dans array list
[Link]("C");
[Link]("A");
[Link]("E");
[Link]("B");
[Link]("D");
[Link]("F");
[Link](1, "A2");
[Link]("Taille de al après ajout : " + [Link]());
// Affichage de al
[Link]("Affichage de al: " + al);
// suppression d'éléments dans array list
[Link]("F");
[Link](2);
[Link]("Taille al après suppression: " + [Link]());
[Link]("Affichage de al: " + al);
}
}
19
Classe concrète : LinkedList<T>
class LinkedListDemo {
public static void main(String args[]) {
// create a linked list
LinkedList<String> ll = new LinkedList<String>();
// add elements to the linked list
[Link]("F"); Output :
[Link]("B");
[Link]("D");
[Link]("E");
[Link]("C");
[Link]("Z");
[Link]("A");
[Link](1, "A2");
[Link]("Original contents of ll: " + ll);
// remove elements from the linked list
[Link]("F");
[Link](2);
[Link]("Contents of ll after deletion: " + ll);
// remove first and last elements
[Link]();
[Link]();
[Link]("ll after deleting first and last: " + ll);
// get and set a value
Object val = [Link](2);
[Link](2, (String) val + " Changed");
[Link]("ll after change: " + ll);
}
20
}
Interface Set<T>
C'est une interface identique à celle de Collection.
Deux implémentations possibles:
o HashSet: les éléments sont rangés suivant une méthode
de hachage.
o TreeSet : les éléments sont rangés de manière
ascendante.
21
Classe concrète : HashSet<T>
class HashSetDemo {
public static void main(String args[]) {
// create a hash set
HashSet<String> hs = new HashSet<String>();
// add elements to the hash set
[Link]("B");
[Link]("A");
[Link]("D");
[Link]("E");
[Link]("C");
[Link]("F");
[Link](hs);
// delete elements from the hash set
[Link]("D");
[Link]("C");
[Link](hs);
}
}
Output :
22
Classe concrète : TreeSet<T>
class TreeSetDemo {
public static void main(String args[]) {
// Create a tree set
TreeSet<String> ts = new TreeSet<String>();
// Add elements to the tree set
[Link]("C");
[Link]("A");
[Link]("B");
[Link]("E");
[Link]("F");
[Link]("D");
[Link](ts);
}
}
Output :
23
Classe concrète : TreeSet<T>
24
Interface Map<K,V>
Une Map est une collection de couples (clé, valeur) :
o Les clés sont uniques : chaque clé est associée à une seule valeur.
o Les clés comme les valeurs peuvent être null.
Les deux implémentations les plus populaires :
o HashMap: les éléments sont rangés suivant une table
hachée
o TreeMap : les éléments sont rangés dans une structure
d’arbre binaire
25
Interface Map<K,V>
26
Classe concrète : HashMap<K,V>
class HashMapDemo {
public static void main(String args[]) {
// Create a hash map
HashMap<String,Double> hm = new HashMap<String,Double>();
// Put elements to the map
Output :
[Link]("Zara", new Double(3434.34));
[Link]("Mahnaz", new Double(123.22));
[Link]("Ayan", new Double(1378.00));
[Link]("Daisy", new Double(99.22));
[Link]("Qadir", new Double(-19.08));
// Get a set of the entries
Set<[Link]<String,Double>> set = [Link]();
// Get an iterator
Iterator<[Link]<String,Double>> i = [Link]();
// Display elements
while([Link]()) {
[Link]<String,Double> me = [Link]();
[Link]([Link]() + ": ");
[Link]([Link]());
}
[Link]();
// Deposit 1000 into Zara's account
double balance = ((Double)[Link]("Zara")).doubleValue();
[Link]("Zara", new Double(balance + 1000));
[Link]("Zara's new balance: " + [Link]("Zara"));
} } 27
Classe concrète : TreeMap<K,V>
class TreeMapDemo {
public static void main(String args[]) {
// Create a hash map
Output :
TreeMap<String, Double> tm = new TreeMap<String, Double>();
// Put elements to the map
[Link]("Zara", new Double(3434.34));
[Link]("Mahnaz", new Double(123.22));
[Link]("Ayan", new Double(1378.00));
[Link]("Daisy", new Double(99.22));
[Link]("Qadir", new Double(-19.08));
// Get a set of the entries
Set<[Link]<String, Double>> set = [Link]();
// Get an iterator
Iterator<[Link]<String, Double>> i = [Link]();
// Display elements
while([Link]()) {
[Link]<String, Double> me = [Link]();
[Link]([Link]() + ": ");
[Link]([Link]());
}
[Link]();
// Deposit 1000 into Zara's account
double balance = ((Double)[Link]("Zara")).doubleValue();
[Link]("Zara", new Double(balance + 1000));
[Link]("Zara's new balance: " +
[Link]("Zara"));
} 28
}
Classes utilitaires
La classe Collections contient des méthodes statiques
qui opèrent sur des collections ou retournent une colle
ction. Parmi ces méthodes, on retrouve le min, le max,
la recherche, le tri (sort) par fusion (merge sort)
La classe Arrays opére sur des tableaux. Parmi
les algorithmes le tri utisés est le tri rapide (quicksort)
pour les nombres et le tri par fusion pour les objets.
29
Classe concrète : TreeMap<K,V>
class UtilitaireDemo {
public static void main(String args[]) {
//création d'un array list
ArrayList<String> al = new ArrayList<String>();
//ajout d'un élément dans array list
[Link]("C"); Output :
[Link]("A");
[Link]("E");
[Link]("B");
[Link]("D");
[Link]("F");
[Link](1, "A2");
// Affichage de al
[Link]("Affichage de al: " + al);
[Link](al);
[Link]("Affichage de al: " + al);
[Link]("B en : " + [Link](al, "B"));
}
}
30
Fin
31