0Pricing
Java Academy · Leçon

LinkedList et ArrayList : compromis

Comparez les performances de l’insertion, de la suppression et de l’accès aléatoire pour choisir le type de liste approprié.

LinkedList et ArrayList : compromis est une leçon Java Academy gratuite sur CoddyKit. Ceci est la leçon 3 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Java Academy, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Java Academy comprend 4 leçons au total.

La question essentielle

ArrayList et LinkedList implémentent toutes deux List, et partagent donc la même API. La différence réside dans leurs structures de données internes et dans les opérations que chacune réalise efficacement.

Structure interne d'ArrayList

ArrayList stocke les éléments dans un tableau contigu. Lorsque le tableau est plein, il est remplacé par un nouveau tableau 1,5 fois plus grand et tous les éléments sont copiés.

import java.util.ArrayList;

ArrayList<String> list = new ArrayList<>(4); // initial capacity 4
list.add("A"); list.add("B"); list.add("C"); list.add("D");
list.add("E"); // triggers resize: new array of capacity 6

System.out.println(list.get(3)); // O(1) — direct index access

Nouvelle étude de la structure interne de LinkedList

Chaque élément se trouve dans son propre objet Node, avec des pointeurs prev/next. Il n'y a pas de mémoire contiguë : les nœuds peuvent se trouver n'importe où dans le tas.

import java.util.LinkedList;

LinkedList<String> list = new LinkedList<>();
list.add("A"); list.add("B"); list.add("C");

// get(index) must traverse from head or tail
System.out.println(list.get(1)); // O(n) — traverses 1 step from head

Accès aléatoire : ArrayList l'emporte

ArrayList.get(i) est en O(1) : l'indice du tableau est accès direct. LinkedList.get(i) est en O(n) : il parcourt jusqu'à n/2 nœuds.

ArrayList<Integer> al = new ArrayList<>();
LinkedList<Integer> ll = new LinkedList<>();
for (int i = 0; i < 100_000; i++) { al.add(i); ll.add(i); }

// Fast:
System.out.println(al.get(99_999)); // O(1)

// Slow — avoid this pattern with LinkedList:
System.out.println(ll.get(99_999)); // O(n)

Insertions en tête : LinkedList l'emporte

Ajouter à l'indice 0 dans ArrayList nécessite de décaler tous les éléments, soit O(n). LinkedList met simplement à jour deux pointeurs, soit O(1).

// ArrayList: O(n) — shifts all elements right
ArrayList<String> al = new ArrayList<>(List.of("B","C","D"));
al.add(0, "A"); // shifts B, C, D

// LinkedList: O(1)
LinkedList<String> ll = new LinkedList<>(List.of("B","C","D"));
ll.addFirst("A"); // updates head pointer only

Insertions en queue : à peu près équivalentes

ArrayList et LinkedList offrent toutes deux des ajouts en queue en O(1) amorti. ArrayList déclenche parfois une copie lors de l'agrandissement, mais son coût amorti reste O(1). LinkedList alloue un nouveau nœud, sans agrandissement nécessaire.

ArrayList<Integer> al = new ArrayList<>();
LinkedList<Integer> ll = new LinkedList<>();

for (int i = 0; i < 1_000_000; i++) {
    al.add(i); // amortized O(1)
    ll.add(i); // O(1)
}

Utilisation de la mémoire

ArrayList : environ 8 octets par élément, soit une référence dans le tableau. LinkedList : environ 48 octets par élément, soit un objet Node contenant les données, prev et next, en plus de l'en-tête de l'objet. Pour les grands ensembles de données, ArrayList utilise nettement moins de mémoire.

Performances du parcours

Le parcours séquentiel, avec une boucle for-each ou un itérateur, est en O(n) dans les deux cas. Cependant, ArrayList bénéficie du préchargement du cache du CPU : les éléments sont contigus en mémoire. Les nœuds de LinkedList sont dispersés dans le tas, ce qui provoque des défauts de cache.

// Both O(n), but ArrayList is faster in practice due to cache locality
for (String s : arrayList) { process(s); }
for (String s : linkedList) { process(s); } // more cache misses

Insertion et suppression au milieu

Les deux structures nécessitent O(n) pour trouver la position. Une fois celle-ci trouvée, ArrayList décale les éléments en O(n), tandis que LinkedList les délie en O(1). Ainsi, pour des modifications fréquentes au milieu lorsque vous disposez déjà d'un itérateur, LinkedList l'emporte ; sinon, leurs performances sont similaires.

LinkedList<Integer> ll = new LinkedList<>(List.of(1,2,3,4,5));
ListIterator<Integer> it = ll.listIterator();
while (it.hasNext()) {
    int val = it.next();
    if (val == 3) it.remove(); // O(1) unlink via iterator
}
System.out.println(ll); // [1, 2, 4, 5]

Guide de décision

Choisissez en fonction de l'opération dominante :

  • ArrayList : accès aléatoire, parcours et ajouts en queue — couvre 90 % des cas d'utilisation
  • LinkedList : insertions et suppressions fréquentes en tête ou en queue, implémentation d'une file, d'une deque ou d'une pile
  • ArrayDeque : si vous avez besoin d'une simple file ou pile, plus performante que LinkedList

Résumé des performances

Modèle mental des performances :

  • get(i) : ArrayList O(1) contre LinkedList O(n)
  • add(0,x) : ArrayList O(n) contre LinkedList O(1)
  • add(x) : O(1) amorti dans les deux cas
  • Suppression avec un itérateur : O(1) dans les deux cas une fois la position atteinte
  • Mémoire par élément : ArrayList environ 8 octets contre LinkedList environ 48 octets

Vérification rapide

Vous construisez une file de tâches dans laquelle des tâches sont ajoutées à la fin et retirées au début des millions de fois par seconde. Quelle structure de données est la plus appropriée ?

Récapitulatif : LinkedList contre ArrayList

Points essentiels :

  • ArrayList excelle pour l’accès aléatoire (O(1)) et les parcours favorables au cache
  • LinkedList excelle pour les opérations en tête et en queue en O(1)
  • Mémoire : environ 8 octets par élément pour ArrayList ; environ 48 octets par élément pour LinkedList
  • Pour les files et les piles, préférez ArrayDeque à LinkedList
  • ArrayList est le choix par défaut approprié dans la plupart des situations

Questions Fréquemment Posées

La leçon « LinkedList et ArrayList : compromis » est-elle gratuite ?

Oui — le texte complet de « LinkedList et ArrayList : compromis » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Java Academy, passe à CoddyKit PRO. Le cours Java Academy comprend 4 leçons au total.

Qu'est-ce que j'apprendrai dans « LinkedList et ArrayList : compromis » ?

Comparez les performances de l’insertion, de la suppression et de l’accès aléatoire pour choisir le type de liste approprié. Tu pratiques Java Academy avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.

Dois-je avoir de l'expérience pour commencer Java Academy ?

Aucune expérience préalable n'est requise. Java Academy sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 3 sur 4.

Combien de temps prend la leçon « LinkedList et ArrayList : compromis » ?

La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.

Peux-tu écrire et exécuter du code dans cette leçon Java Academy ?

Oui. Chaque leçon Java Academy inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.

Toutes les leçons de ce cours

  1. Fonctionnement interne de LinkedList
  2. Opérations sur une deque : pile et file
  3. LinkedList et ArrayList : compromis
  4. PriorityQueue pour le traitement ordonné
← Retour à Java Academy