LinkedList

Une LinkedList permet d'ajouter des éléments les uns après les autres dans un ensemble ordonné. Les éléments peuvent être accédés par leur indice.

Il s'agit d'une collection du package java.util

Le principe de cette classe est d'utiliser un tableau qui lorsqu'il est trop petit est dupliqué dans un nouveau tableau de taille plus grande.

Il s'agit en fait d'une liste doublement chaînée. Chacun des éléments référence l'élément précédent et suivant.

Avantage: Très rapide pour insérer un élément dans la liste car contrairement à une ArrayList, il n'est pas nécessaire de déplacer tous les autres éléments de la collection.

Inconvénient: L'accès aux éléments de la liste se fait séquentiellement grâce aux liens entre les chaînons. La recherche peut donc être longue.

La valeur de l'indexe commence à 0 et s'incrémente au fur et à mesure que l'on ajoute des éléments, ou se décrémente si on en retire.

Image non trouvée ! Voir aussi la collection ArrayList très similaire.

Quelques méthodes

Méthode	Désignation
public void add (java.lang.Object object)	Ajoute la référence d'un objet à la fin de la collection.
public boolean add (int index, java.lang.Object object)	Inserela référence d'un objet à l'index donné, déplace donc les autres références à partir de cet index automatiquement. (Note: Voir aussi addAll pour ajouter une collection)
public java.lang.Object get (int index)	Récupérer la référence d'un objet par l'index de l'élément.
public java.lang.Object set (int index)	Modifier la référence d'un objet par l'index de l'élément.
boolean contains (java.lang.Object object)	Recherche la présence d'un élément dans la collection correspondant à l'objet dont la référence est passée en paramètre. Retourne vrai si trouvé, false sinon (Note: - utilise la méthode equals pour comparer les objets - Il est possible de faire de même avec une collection: boolean java.util.Collection.containsAll)
public int indexOf (java.lang.Object object)	Recherche la valeur d'un index pour le premier élément dans la collection correspondant à l'objet dont la référence passée en paramètre. (Note: utilise la méthode equals pour comparer les objets)
public int lastIndexOf (java.lang.Object object)	Recherche la valeur d'un index pour le dernier élément dans la collection correspondant à l'objet dont la référence passée en paramètre. (Note: utilise la méthode equals pour comparer les objets)
public int size	Indique le nombre total d'éléments dans la collection
public void clear()	Effacer le contenu de la collection
public java.lang.Object remove (int index)	Effacer un élément de la collection par son index
public java.lang.Object remove (int index)	Effacer un élément de la collection par sa référence
public java.util.Iterator iterator()	Itérateur pour énumérer les éléments de la collection. Vous pouvez donc utiliser l'écriture du for java 5 avec iterateur: for (element:collection) !
public java.lang.Object [] to Array (java.lang.Object [] a)	Récupérer les éléments de la collection dans un tableau
public void push (java.lang.Object a)	Envoyer dans la pile LIFO
public java.lang.Object pop ()	Récupérer de la pile LIFO

Image non trouvée ! Une exception java.lang.IndexOutOfBoundsException pourra être déclenchée si vous essayez d'accèder à un élément via un index hors des valeurs du tableau. D'autres méthodes pourront aussi déclencher des exceptions...

Exemples de code

import java.io.IOException; import java.util.LinkedList; public class TstMain { public static void main(String[] args) { // TODO Auto-generated method stub LinkedList monEnsemble = new LinkedList(); String s = new String ("Element 1"); // Memorise la reference de l'objet string qui contient "Element 1" comme chaine de caracteres monEnsemble.add (s); // Index 0 monEnsemble.add ("Element 2"); // index 1 monEnsemble.add (null); // index 2 monEnsemble.add ("Element 3"); // index 3 monEnsemble.add (2, "Element 4"); // insertion en index 2, donc les objets numerote a partir de 2 seront deplaces monEnsemble.set (3, "modification"); // Modification de l'objet en index 3 qui est en fait l'objet null qui se trouvait avant insertion en index 2 monEnsemble.add (0, "Element 5"); // insertion en index 0, donc les objets numerote a partir de 0 seront deplaces // Recherche l'index d'un objet par sa reference. Il etait en 0 lors de la creation, mais l'ajout de Element 5 doit le mener en index 1. System.out.println ("L'index de s est:" + monEnsemble.indexOf(s)); // Cette ecriture sur la recherche de l'index de l'objet s pourra donc se simplifier ! Voici un autre exemple: System.out.println ("L'index de 'modification' est:" + monEnsemble.indexOf("modification")); // Cela peut paraitre etrange // Car on devrait s'attendre a avoir un nouveau String "modification" ayant donc sa propre reference qui ne sera pas la meme // que l'objet ayant la meme chaine de caracteres precedemment cree. // Mais cela marche, car pour un string, le test se fait non pas sur la reference de l'objet string, mais bien sur la chaine de caracteres // liee a cette reference (cf. methode String.equals). // L'index devra etre 4 (3 initialement, mais deplace ensuite avec l'insertion de Element 5). System.out.println ("Nombre d'elements:" + monEnsemble.size()); for (Object Chaine:monEnsemble) // A partir de java 5, en effet, iterator est implemente dans toutes les collections. Sinon utilisez une boucle for standard System.out.println (Chaine); } }

Exemple d'utilisation en pile LIFO (Last Input First Output)

[...] LinkedList maPile = new LinkedList(); maPile.push(1); // Envoi de valeurs dans la pile maPile.push(2); maPile.push(3); maPile.push(4); int element; System.out.println ("Nombre d'élément dans la pile:" + maPile.size()); int iTaille = maPile.size(); for (int i=0; i < iTaille; i++) { element = (int) maPile.pop(); // Récupération des éléments mode LIFO ! System.out.println ("=" + element); } [...]