Guide de la LinkedList Java

1. Introduction

LinkedList est une implémentation de liste à double lien des interfaces List et Deque . Il implémente toutes les opérations de liste facultatives et autorise tous les éléments (y compris null ).

2. Caractéristiques

Vous trouverez ci-dessous les propriétés les plus importantes de LinkedList :

  • Les opérations qui indexent dans la liste parcourent la liste à partir du début ou de la fin, selon ce qui est le plus proche de l'index spécifié
  • Il n'est pas synchronisé
  • Ses itérateurs Iterator et ListIterator sont rapides (ce qui signifie qu'après la création de l'itérateur, si la liste est modifiée, une ConcurrentModificationException sera lancée)
  • Chaque élément est un nœud, qui garde une référence aux suivants et précédents
  • Il maintient l'ordre d'insertion

Bien que LinkedList ne soit pas synchronisé, nous pouvons en récupérer une version synchronisée en appelant la méthode Collections.synchronizedList , comme:

List list = Collections.synchronizedList(new LinkedList(...));

3. Comparaison avec ArrayList

Bien que les deux implémentent l' interface List , ils ont une sémantique différente - ce qui affectera certainement la décision d'utiliser.

3.1. Structure

Une ArrayList est une structure de données basée sur un index soutenue par un Array . Il fournit un accès aléatoire à ses éléments avec une performance égale à O (1).

D'autre part, une LinkedList stocke ses données sous forme de liste d'éléments et chaque élément est lié à son élément précédent et suivant. Dans ce cas, l'opération de recherche d'un élément a un temps d'exécution égal à O (n).

3.2. Opérations

Les opérations d'insertion, d'ajout et de suppression d'un élément sont plus rapides dans une LinkedList car il n'est pas nécessaire de redimensionner un tableau ou de mettre à jour l'index lorsqu'un élément est ajouté à une position arbitraire dans la collection, seules les références dans les éléments environnants changeront.

3.3. Utilisation de la mémoire

Un LinkedList consomme plus de mémoire qu'un ArrayList car chaque nœud d'un LinkedList stocke deux références, une pour son élément précédent et une pour son élément suivant, alors qu'ArrayList ne contient que les données et son index.

4. Utilisation

Voici quelques exemples de code qui montrent comment utiliser LinkedList :

4.1. Création

LinkedList linkedList = new LinkedList();

4.2. Ajout d'un élément

LinkedList implémente les interfaces List et Deque , en plus des méthodes standard add () et addAll () , vous pouvez trouver addFirst () et addLast () , qui ajoute un élément au début ou à la fin, respectivement.

4.3. Suppression d'un élément

De la même manière que l'ajout d'éléments, cette implémentation de liste propose removeFirst () et removeLast ().

En outre, il existe des méthodes pratiques removeFirstOccurence () et removeLastOccurence () qui retournent boolean (true si la collection contient l'élément spécifié).

4.4. Opérations de file d'attente

L' interface Deque fournit des comportements de type file d'attente (en fait, Deque étend l' interface de file d'attente ):

linkedList.poll(); linkedList.pop();

Ces méthodes récupèrent le premier élément et le suppriment de la liste.

La différence entre poll () et pop () est que pop lancera NoSuchElementException () sur une liste vide, tandis que poll renvoie null. Les API pollFirst () et pollLast () sont également disponibles.

Voici par exemple comment fonctionne l' API push :

linkedList.push(Object o);

Qui insère l'élément en tant que tête de la collection.

LinkedList a de nombreuses autres méthodes, dont la plupart devraient être familières à un utilisateur qui a déjà utilisé Lists . D'autres, fournis par Deque, pourraient être une alternative pratique aux méthodes «standard».

La documentation complète peut être trouvée ici.

5. Conclusion

ArrayList est généralement l' implémentation par défaut de List .

Cependant, il existe certains cas d'utilisation où l'utilisation de LinkedList conviendra mieux, comme les préférences pour un temps d'insertion / suppression constant (par exemple, des insertions / suppressions / mises à jour fréquentes), sur un temps d'accès constant et une utilisation efficace de la mémoire.

Des exemples de code peuvent être trouvés sur GitHub.