LinkedList ou ArrayList en Java : que choisir et pourquoi c'est important

LinkedList ou ArrayList : le choc des titans des collections Java

Si vous avez déjà écrit du code Java qui manipule des listes de données, vous avez sûrement été confronté au dilemme : LinkedList ou ArrayList ? Cette question est un véritable hit sur Stack Overflow, discutée par des milliers de développeurs. Et ce n'est pas pour rien. Choisir la mauvaise structure de données peut transformer votre code rapide en tortue qui rampe dans un marécage. Alors qu'un bon choix peut rendre votre application réactive et efficace.

Aujourd'hui, nous ne nous contenterons pas d'énumérer des faits secs. Nous allons regarder sous le capot de Java, comprendre comment ces collections fonctionnent au niveau de la mémoire et du processeur, et donner une réponse claire : quand faut-il utiliser LinkedList, et quand faut-il utiliser ArrayList ? C'est parti !

L'essentiel en bref : ce que disent les gentlemen de la documentation

Commençons par les bases. Les deux classes implémentent l'interface List, mais le font de manière différente.

\n
• ArrayList est un tableau dynamique. Il stocke les éléments dans un bloc de mémoire contigu. Lorsque le tableau est plein, il en crée un nouveau, plus grand, et y copie tous les éléments.
\n
• LinkedList est une liste doublement chaînée. Chaque élément (nœud) stocke des références vers l'élément précédent et le suivant. La mémoire est allouée séparément pour chaque nœud.
\n

Cela semble simple. Mais le diable, comme toujours, se cache dans les détails. Regardons le code.

Sous le capot : comment cela fonctionne en pratique

ArrayList : accès rapide, mais insertion lente au milieu

import java.util.ArrayList;\nimport java.util.List;\n\npublic class ArrayListDemo {\n    public static void main(String[] args) {\n        List<String> arrayList = new ArrayList<>();\n        \n        // Ajout à la fin — rapide (O(1) amorti)\n        long start = System.nanoTime();\n        for (int i = 0; i < 100000; i++) {\n            arrayList.add("Element " + i);\n        }\n        long end = System.nanoTime();\n        System.out.println("ArrayList add (à la fin) : " + (end - start) / 1e6 + " ms");\n        \n        // Accès par index — instantané (O(1))\n        start = System.nanoTime();\n        String element = arrayList.get(50000);\n        end = System.nanoTime();\n        System.out.println("ArrayList get : " + (end - start) + " ns");\n        \n        // Insertion au milieu — lente (O(n))\n        start = System.nanoTime();\n        arrayList.add(25000, "INSERTED");\n        end = System.nanoTime();\n        System.out.println("ArrayList insert (milieu) : " + (end - start) / 1e6 + " ms");\n    }\n}

Que se passe-t-il ici ? Lorsque vous insérez un élément au milieu d'un ArrayList, tous les éléments à droite du point d'insertion sont décalés d'une position. C'est une opération en O(n). Si vous avez un million d'éléments, cela représente un million d'opérations de copie. Douloureux.

LinkedList : l'insertion est reine, mais l'accès est un paria

import java.util.LinkedList;\nimport java.util.List;\n\npublic class LinkedListDemo {\n    public static void main(String[] args) {\n        List<String> linkedList = new LinkedList<>();\n        \n        // Ajout à la fin — rapide (O(1))\n        long start = System.nanoTime();\n        for (int i = 0; i < 100000; i++) {\n            linkedList.add("Element " + i);\n        }\n        long end = System.nanoTime();\n        System.out.println("LinkedList add (à la fin) : " + (end - start) / 1e6 + " ms");\n        \n        // Accès par index — lent (O(n))\n        start = System.nanoTime();\n        String element = linkedList.get(50000);\n        end = System.nanoTime();\n        System.out.println("LinkedList get : " + (end - start) / 1e6 + " ms");\n        \n        // Insertion au milieu — rapide (O(1) après la recherche de la position)\n        start = System.nanoTime();\n        // ATTENTION : la méthode add(index, element) elle-même effectue une recherche (O(n))\n        linkedList