Les collections

Les collections
Les collections permettent de stocker un nombre variable d'éléments de
types identiques ou disparates. Le langage Java dispose de plusieurs
classes destinées à créer ce genre d'artifice. Les collections se démarquent des tableaux dans la mesure ou elles ont la
capacité de s'étendre et de diminuer au gré, respectivement, des ajouts et
des suppressions d'éléments. Cela permet d'éviter de consommer des
ressources mémoires inutilement en initialisant un tableau à une taille
prédéfinie en sachant que celui-ci risque de ne pas être totalement rempli
lors des différentes étapes d'exécution d'un programme. Dans ce cas, une
collection possèdera la faculté d'adapter sa taille à tous changements. Les classes de gestion de collections se situent dans le paquetage
java.util. Il en existe trois sortes : . Les listes sont des structures capables de contenir des objets de
différents types accessibles séquentiellement.
. Les maps sont des tableaux associatifs qui permettent de lier un objet
clé à un autre objet valeur.
. Les ensembles sont des structures contenant des éléments non dupliqués
dont l'accès reste très performant.
|Type |Classe |Description |
|Les |Vector |représente un tableau dynamique dont la taille peut varier.|
|listes | | |
| |Stack |représente un mécanisme de pile de type LIFO. |
| |ArrayList |représente un tableau dynamique dont la taille peut varier.|
| |LinkedList|représente une liste liée utilisable comme une pile LIFO ou|
| | |une file FIFO. |
|Les |Hashtable |représente un tableau associatif dont les clés ne peuvent |
|Maps | |être nulles. |
| |HashMap |représente un tableau associatif dont une clé et des |
| | |valeurs peuvent être nulles. |
| |WeakHashMa|représente un tableau associatif où si une clé n'est plus |
| |p |référencée, la paire clé-valeur est ignorée. |
| |TreeMap |représente un tableau associatif dont les clés sont |
| | |classées en ordre croissant. |
|Ensembl|HashSet |représente un ensemble renforcée par un map. |
|es | | |
| |TreeSet |représente un ensemble renforcée par un TreeMap et classant|
| | |les objets en ordre croissant. | L'API propose deux implémentations concrètes pour les listes
(java.util.List). Une liste est une suite ordonnée d'éléments (les éléments
peuvent être ajoutés à plusieurs endroits de la liste). java.util.ArrayList :
Un java.util.ArrayList utilise un tableau en interne pour ranger les
données. Un ArrayList fournit un accès aux éléments par leur indice très
performant et est optimisé pour des opérations d'ajout/suppression
d'éléments en fin de liste.
Complexité : Les opérations size, isEmpty, get, set, iterator sont
exécutées en temps constant.
Les opérations d'ajout/suppression sont exécutées en temps constant amorti
(les ajouts/suppressions en fin de liste sont plus rapides). java.util.LinkedList :
Un java.util.LinkedList utilise une liste chainée pour ranger les données.
L'ajout et la suppression d'éléments est aussi rapide quelle que soit la
position, mais l'accès aux valeurs par leur indice est très lente.
Complexité : Les opérations size, isEmpty, add, remove, set, get sont
exécutées en temps constant. Toutes les méthodes qui font référence à un
indice sont exécutées en temps O(n). java.util.Vector :
La classe java.util.Vector est une classe héritée de Java 1. Elle n'est
conservée dans l'API actuelle que pour des raisons de compatiblité
ascendante et elle ne devrait pas être utilisée dans les nouveaux
programmes. Dans tous les cas, il est préférable d'utiliser un ArrayList.
Note : Cette classe est "thread-safe", c'est-à-dire que plusieurs processus
peuvent l'utiliser en même temps sans risque.
Complexité : idem que pour ArrayList, plus le temps de synchronisation des
méthodes. Liste linéaire chaînée(LinkedList) Jusqu'ici, nous avons toujours utilisé des tableaux pour conserver nos
données (Vector utilise un tableau qu'il redimensionne au besoin),
certaines opérations sont très efficaces avec un tableau, tel : accéder à
un élément à une position donnée, supprimer le dernier élément du tableau,
ajouter un élément à la fin du tableau (sauf si le tableau doit être
redimensionné). Par contre, l'ajout ou la suppression d'un élément
ailleurs qu'à la fin du tableau impliquent de décaler d'une position tous
les éléments qui suivent. Une autre structure de données qui est plus efficace dans ces cas est une
liste chaînée, celle-ci consiste en un objet connaissant la position en
mémoire du premier et du dernier élément de la liste ainsi que le nombre
d'éléments. Chaque élément de la liste connaît la position de l'élément
qui le précède ainsi que celle de l'élément qui le suit. liste
|
V
+-----+----+-----+
|--------------- | | ---------------
| | | 3 | | |
| +-----+----+-----+ |
| |
V V
+-----+-----+----+ +-----+----+-----+ +----+-----+----+
| | | | | |monde| X |
+-----+-----+----+ +-----+----+-----+ +----+-----+----+ Ainsi, liste fait référence à l'objet qui connaît le premier élément de la
liste, le dernier et le nombre d'éléments. Pour accéder à l'élément
contenant la chaîne de caractères « le », il faut passer, soit par le
premier élément, soit par le dernier, mais pas directement.
Les éléments peuvent se retrouver n'importe où en mémoire, et non un après
l'autre comme un tableau.
Ainsi, pour ajouter un élément en plein milieu, par exemple après « Allo »,
il suffit de créer un élément (n'importe où en mémoire), de modifier la
référence de « Allo » vers sont suivant et de « le » vers son précédent. liste
|
V
+-----+----+-----+
|--------------- | | --------------------
| | | 4 | | |
| +-----+----+-----+ |
| |
V V
+-----+-----+----+ +-----+----+-----+ +----+-----+----+
| | | | |----- | | | | |monde| X |
+-----+-----+----+ | | +-----+----+-----+ +----+-----+----+
^ v v ^
| +-----+----+-----+ |
|--------------- | | --------|
| |tout| |
+-----+----+-----+ Donc il n'est pas nécessaire de déplacer les éléments suivants. Donc, une liste chaînée est indiquée lorsqu'il y aura beaucoup d'insertion
ou de suppression n'importe où dans la liste, par contre, l'accès à un
élément par sa position (index) implique que l'on doit parcourir plusieurs
éléments avant d'y arriver.
La classe LinkedList fournit des méthodes nommées uniformément pour
l'obtention, la suppression et l'insertion d'élément au début et à la fin
de la liste chaînée. Ces opérations permettent aux listes chaînées d'être
utilisées en tant que pile, file d'attente, ou file d'attente double. |Les constructeurs |
|LinkedList() |
|crée une liste chaînée vide. |
|LinkedList(Collection c) |
|crée une liste chaînée contenant les éléments de la |
|collection passée en argument. | |Les méthodes |
|void add(int index, Object element) |
|insère l'élément spécifié à la position donnée au sein de l"objet LinkedList.|
|boolean add(Object o) |
|ajoute l'élément spécifié à la fin de l'objet LinkedList. |
|boolean addAll(Collection c) |
|ajoute tous les éléments de la collection spécifiée à la fin de la liste |
|chaînée. |
|boolean addAll(int index, Collection c) |
|insère à partir de la position donnée, tous les les éléments de la collection|
|spécifiée au sein de l'objet LinkedList. |
|void addFirst(Object o) |
|insère l'élément donné au début de la liste chaînée. |
|void addLast(Object o) |
|ajoute l'élément donné à la fin de la liste chaînée. |
|void clear() |
|supprime tous les éléments de l'objet LinkedList. |
|Object clone() |
|retourne