Différence entre ArrayList et LinkedList en Java

Les deux listes ArrayList et LinkedList implémentent l'interface List, mais quelle est la différence alors ? La différence principale entre ArrayList et LinkedList est dans ArrayList qui est implémentée en utilisant un tableau extensible. Tant que plus d'éléments sont ajoutés à ArrayList, sa taille augmente dynamiquement. Ses éléments peuvent être accessibles directement en utilisant les méthodes get() et set(), puisque ArrayList est essentiellement un tableau.

LinkedList est implémentée sous forme d'une liste chaînée, ces performances d'ajout et de suppression sont plus meilleures que celles de ArrayList, mais ils sont mauvaises pour les méthodes get() et set().

Dans cet article, on va voir quelques différences entre LinkedList et ArrayList et essayer de comprendre quand et ou utiliser LinkedList au lieu d'ArrayList.

ArrayList vs LinkedList

Toutes les différences entre LinkedList et ArrayList ont une source qui est la différence entre un tableau et une LinkedList (liste chaînée).

1) Puisque la recherche dans ArrayList est basée sur l'index de l'élément alors elle est très rapide. La méthode get(index) a une complexité de O(1), mais la suppression est coûteuse parce que vous devez décaler tous les éléments. Dans le cas de LinkedList, elle ne possède pas un accès direct aux éléments, vous devez parcourir toute la liste pour récupérer un élément, sa complexité est égale à O(n).

2) Les insertions sont faciles dans LinkedList par rapport à ArrayList parce qu'il n y a aucun risque lors de la redimensionnement et l'ajout de l'élément à LinkedList et sa complexité est égale à O(1), tandis que ArrayList décale tous les éléments avec une complexité de O(n) dans le pire des cas.

3) La suppression est comme l'insertion, meilleure dans LikedList que dans ArrayList.

4) LinkedList a plus de mémoire que ArrayList parce que dans ArrayList chaque index est relié avec l'objet actuel, mais dans le cas de LinkedList, chaque nœud est relié avec l'élément et l'adresse du nœud suivant et précédent.

Quand utiliser LinkedList et ArraList en Java

Visiblement, LinkedList n'est pas populaire comme ArrayList, mais reste un bon choix dans certains cas:

1) Votre application n'a pas besoin d'un accès aléatoire, parce que cette opération consiste à parcourir toute la liste dans ce cas.

2) Votre application a plus d'insertion et de suppression que de récupération. Ces deux opérations sont plus rapide dans LikedList.

Utilisez ArrayList en Java dans ces situation quant vous avez besoin d'un accès non synchronisé. ArrayList est rapide et facile à utiliser.

Exemple de ArrayList

ArrayList<String> al = new ArrayList<String>();
al.add("a");
al.add("c"); 
al.add("e");
al.add("z");
al.add("t");
al.add("m");

for(String s: e){
 System.out.println(e);
}

Exemple de LinkedList

LinkedList<Integer> llist = new LinkedList<Integer>();
llist.add(8);
llist.add(9);
llist.add(5);
llist.add(2);
llist.add(6);
 
Iterator<Integer> it = llist.iterator();
while(it.hasNext()){
 System.out.println(it.next());
}

Performance de ArrayList et de LinkedList

La complexité en temps des deux listes:

Opération	ArrayList	LinkedList
get()	O(1)	O(n)
add()	O(1)	O(1)
remove()	O(n)	O(1)

- ArrayList a une compexité en temps de O(n) pour les deux opérations add() et remove(), mais O(1) pour l'opération à la fin de la liste ou pour la récupération d'un élément avec la méthode get().

- LinkedList a une complexité de O(n) pour l'opération get() , mais O(n) pour l'opération de suppression remove().

Ce code teste les performances en basant sur le temps nécessaire pour effectuer un certain nombre d'opérations:

import java.util.ArrayList;
import java.util.LinkedList;

public class ArrayListVsLinkedList {

 public static void main(String[] args) {
 ArrayList<Integer> alist = new ArrayList<Integer>();
 LinkedList<Integer> llist = new LinkedList<Integer>();
 
 /******************************/
 /* La méthode add() */
 /******************************/
 
 // ArrayList
 long tpsdebut = System.currentTimeMillis();
 
 for (int i = 0; i <= 999999; i++) {
 alist.add(i);
 }
 long tpsfin = System.currentTimeMillis();
 long duree = tpsfin - tpsdebut;
 System.out.println("ArrayList add: " + duree);
 
 // LinkedList
 tpsdebut = System.currentTimeMillis();
 
 for (int i = 0; i <= 999999; i++) {
 llist.add(i);
 }
 tpsfin = System.currentTimeMillis();
 duree = tpsfin - tpsdebut;
 System.out.println("LinkedList add: " + duree);
 
 /******************************/
 /* La méthode get() */
 /******************************/
 // ArrayList
 tpsdebut = System.currentTimeMillis();
 
 for (int i = 0; i <= 99999; i++) {
 alist.get(i);
 }
 tpsfin = System.currentTimeMillis();
 duree = tpsfin - tpsdebut;
 System.out.println("ArrayList get: " + duree);
 
 // LinkedList
 tpsdebut = System.currentTimeMillis();
 
 for (int i = 0; i <= 99999; i++) {
 llist.get(i);
 }
 tpsfin = System.currentTimeMillis();
 duree = tpsfin - tpsdebut;
 System.out.println("LinkedList get: " + duree);
 
 /******************************/
 /* La méthode remove() */
 /******************************/
 // ArrayList
 tpsdebut = System.currentTimeMillis();
 
 for (int i = 9999; i >=0; i--) {
 alist.remove(i);
 }
 tpsfin = System.currentTimeMillis();
 duree = tpsfin - tpsdebut;
 System.out.println("ArrayList remove: " + duree);
 
 // LinkedList
 tpsdebut = System.currentTimeMillis();
 
 for (int i = 9999; i >=0; i--) {
 llist.remove(i);
 }
 tpsfin = System.currentTimeMillis();
 duree = tpsfin - tpsdebut;
 System.out.println("LinkedList remove: " + duree);
 }
}

Résultat:

ArrayList add: 398
LinkedList add: 987
ArrayList get: 180
LinkedList get: 43276
ArrayList remove: 8721
LinkedList remove: 233

performance et difference ArrayList vs LinkedList

La différence majeure est celle de la méthode get() et remove(). On voit bien que LinkedList est très coûteuse en temps lors de la récupération des données parce qu'elle fait le parcours de toute la liste à chaque fois qu'elle veut accéder à un élément. ArrayList a un accès direct. En revanche, ArrayList consomme beaucoup de temps pour l'opération remove().