TL;DR : ArrayList et LinkedList sont deux implémentations de List en Java. La différence fondamentale : ArrayList utilise un tableau redimensionnable, LinkedList une liste chaînée doublement liée.

En préparant un entretien technique récemment, j’ai demandé à un LLM quelles questions techniques pourraient m’être posées. Parmi les réponses, une question est revenue avec insistance : « Quelle est la différence entre ArrayList et LinkedList en Java ? » Cette question, apparemment simple, cache en réalité des concepts fondamentaux de l’informatique que tout développeur Java devrait maîtriser. J’ai donc pensé qu’écrire un article détaillé sur ce sujet pourrait être utile, non seulement pour les entretiens, mais surtout pour mieux comprendre ces structures de données essentielles. Vous lisez actuellement le résultat de cette réflexion.

Ces optimisations de structures de données font partie des évolutions continues du langage Java.

Avant de plonger : pourquoi cette question est-elle si importante ?

Cette question n’est pas posée par hasard lors des entretiens techniques. Elle permet d’évaluer plusieurs compétences à la fois : votre compréhension des structures de données, votre capacité à analyser la complexité algorithmique, et surtout votre aptitude à choisir la bonne solution selon le contexte. En effet, utiliser ArrayList ou LinkedList dans la mauvaise situation peut avoir un impact considérable sur les performances de votre application.

Les fondations : comprendre les structures de données sous-jacentes

Pour vraiment saisir les différences entre ArrayList et LinkedList, nous devons d’abord comprendre les structures de données qui les sous-tendent. C’est comme comprendre la différence entre une voiture et un train : les deux vous emmènent d’un point A à un point B, mais leur fonctionnement interne détermine dans quelles situations chacun excelle.

ArrayList : la puissance des tableaux dynamiques

ArrayList s’appuie sur un tableau (array) redimensionnable. Imaginez une rangée de casiers numérotés dans un vestiaire. Chaque casier a un numéro (l’index), et vous pouvez directement aller au casier numéro 42 sans passer par tous les autres. C’est exactement ainsi qu’ArrayList fonctionne en mémoire : les éléments sont stockés de manière contiguë, et chaque élément peut être accédé directement grâce à son index.

// Création d'une ArrayList - en interne, un tableau est alloué
ArrayList<String> prenoms = new ArrayList<>();

// Ajout d'éléments - ils sont placés de manière contiguë en mémoire
prenoms.add("Alice");   // Index 0
prenoms.add("Bob");     // Index 1  
prenoms.add("Charlie"); // Index 2

// Accès direct par index - très rapide car calcul mathématique simple
String deuxiemePrenom = prenoms.get(1); // Récupère "Bob" directement

LinkedList : la flexibilité des listes chaînées

LinkedList, de son côté, implémente une liste doublement chaînée. Imaginez maintenant une chasse au trésor où chaque indice vous dit où se trouve le suivant. Chaque élément (appelé nœud) contient non seulement la donnée, mais aussi des références vers l’élément précédent et le suivant. Pour atteindre un élément spécifique, il faut suivre la chaîne depuis le début ou la fin.

// Création d'une LinkedList - structure de nœuds liés
LinkedList<String> prenoms = new LinkedList<>();

// Ajout d'éléments - chaque nœud pointe vers le précédent et le suivant
prenoms.add("Alice");   // Nœud 1: [null ← Alice → nœud2]
prenoms.add("Bob");     // Nœud 2: [nœud1 ← Bob → nœud3]
prenoms.add("Charlie"); // Nœud 3: [nœud2 ← Charlie → null]

// Accès par index - nécessite de parcourir la chaîne
String deuxiemePrenom = prenoms.get(1); // Doit partir du début et suivre un lien

L’analyse des performances : la complexité algorithmique en action

Comprendre les performances de ces structures nécessite de maîtriser la notation Big O, qui décrit comment le temps d’exécution évolue avec la taille des données. Analysons chaque opération fondamentale.

Accès aux éléments (get/set)

ArrayList : L’accès est en O(1) – temps constant. Peu importe si votre liste contient 10 ou 10 millions d’éléments, accéder à l’élément à l’index 5 prendra toujours le même temps. C’est un calcul mathématique simple : adresse_base + (index × taille_élément).

LinkedList : L’accès est en O(n) – temps linéaire. Pour atteindre l’élément à l’index 5, il faut parcourir les éléments 0, 1, 2, 3, puis 4. Plus l’index est élevé, plus l’opération prend du temps.

// Démonstration de la différence de performance
ArrayList<Integer> arrayList = new ArrayList<>();
LinkedList<Integer> linkedList = new LinkedList<>();

// Remplissage avec 100 000 éléments
for (int i = 0; i < 100000; i++) {
    arrayList.add(i);
    linkedList.add(i);
}

// Accès à l'élément au milieu
long start = System.nanoTime();
int valeur = arrayList.get(50000); // Très rapide - O(1)
long tempsArrayList = System.nanoTime() - start;

start = System.nanoTime();
valeur = linkedList.get(50000); // Plus lent - doit parcourir 50 000 éléments
long tempsLinkedList = System.nanoTime() - start;

// LinkedList sera significativement plus lente

Insertion et suppression

C’est ici que les choses deviennent plus nuancées et intéressantes.

Insertion/suppression au début ou à la fin :

• ArrayList : O(1) pour la fin, O(n) pour le début (doit décaler tous les éléments)
• LinkedList : O(1) pour les deux positions (modification des liens seulement)

Insertion/suppression au milieu :

• ArrayList : O(n) (doit décaler tous les éléments suivants)
• LinkedList : O(n) pour localiser la position + O(1) pour l’opération

// Insertion au début - LinkedList excelle ici
ArrayList<String> arrayList = new ArrayList<>();
LinkedList<String> linkedList = new LinkedList<>();

// ArrayList doit décaler tous les éléments existants
arrayList.add(0, "Nouveau premier"); // O(n) - coûteux

// LinkedList modifie juste les liens
linkedList.addFirst("Nouveau premier"); // O(1) - très rapide

Utilisation de la mémoire : un aspect souvent négligé

La consommation mémoire diffère significativement entre ces deux structures.

ArrayList stocke uniquement les références aux objets dans un tableau continu. C’est efficace en termes d’espace et excellent pour la localité spatiale (les éléments adjacents sont physiquement proches en mémoire, ce qui améliore les performances du cache du processeur).

LinkedList stocke chaque élément dans un nœud qui contient, en plus de la référence à l’objet, deux pointeurs supplémentaires (vers le précédent et le suivant). Cela représente un surcoût mémoire non négligeable, surtout pour de petits objets.

Quand utiliser quoi ? Guide pratique de décision

La question cruciale pour tout développeur est : comment choisir entre ArrayList et LinkedList dans une situation donnée ?

Privilégiez ArrayList quand :

Vous effectuez beaucoup d’accès aléatoires : Si votre code fait fréquemment liste.get(index), ArrayList est incontournable. Par exemple, dans un algorithme de tri, dans la manipulation de matrices, ou lors de l’affichage paginé de données.

Vous itérez souvent sur la collection : Grâce à la localité spatiale, parcourir une ArrayList est plus rapide et plus efficace pour le cache du processeur.

La mémoire est une contrainte : ArrayList consomme moins de mémoire par élément.

// Cas d'usage typique d'ArrayList : affichage paginé
public List<Produit> getProduitsPagines(int page, int taille) {
    ArrayList<Produit> tousProduits = recupererTousProduits();
    int debut = page * taille;
    int fin = Math.min(debut + taille, tousProduits.size());
    
    List<Produit> resultat = new ArrayList<>();
    // Accès direct par index - très efficace avec ArrayList
    for (int i = debut; i < fin; i++) {
        resultat.add(tousProduits.get(i));
    }
    return resultat;
}

Privilégiez LinkedList quand :

Vous insérez/supprimez fréquemment au début : Les opérations comme addFirst(), removeFirst() sont très efficaces.

Vous implémentez une pile ou une file : LinkedList implémente les interfaces Deque et Queue, offrant des méthodes optimisées pour ces structures.

La taille de votre collection fluctue beaucoup : LinkedList n’a pas besoin de réallouer et copier un tableau entier lors de l’agrandissement.

// Cas d'usage typique de LinkedList : implémentation d'une file d'attente
public class GestionnaireCommandes {
    private LinkedList<Commande> fileCommandes = new LinkedList<>();
    
    public void ajouterCommande(Commande commande) {
        fileCommandes.addLast(commande); // O(1) - très efficace
    }
    
    public Commande traiterProchaineCommande() {
        return fileCommandes.removeFirst(); // O(1) - très efficace
    }
}

Exemples concrets et benchmarks

Pour illustrer concrètement ces différences, considérons quelques scénarios réels.

Scénario 1 : Système de cache LRU (Least Recently Used)

// LinkedList excelle ici grâce aux opérations efficaces en début/fin
public class CacheLRU<T> {
    private LinkedList<T> cache = new LinkedList<>();
    private int capaciteMax;
    
    public void acceder(T element) {
        // Retirer l'élément de sa position actuelle (si présent)
        cache.remove(element); // O(n) pour trouver, O(1) pour supprimer
        
        // L'ajouter au début (plus récemment utilisé)
        cache.addFirst(element); // O(1)
        
        // Supprimer le plus ancien si nécessaire
        if (cache.size() > capaciteMax) {
            cache.removeLast(); // O(1)
        }
    }
}

Scénario 2 : Traitement de données par lots

// ArrayList est plus appropriée pour ce cas
public class ProcesseurDonnees {
    public void traiterParLots(ArrayList<Donnee> donnees, int tailleLot) {
        // Accès direct par index - très efficace avec ArrayList
        for (int i = 0; i < donnees.size(); i += tailleLot) {
            int fin = Math.min(i + tailleLot, donnees.size());
            
            // Traitement d'un lot spécifique
            for (int j = i; j < fin; j++) {
                traiter(donnees.get(j)); // O(1) pour chaque accès
            }
        }
    }
}

Les pièges courants à éviter

Piège 1 : Utiliser LinkedList pour l’accès aléatoire

// ❌ Mauvaise pratique - très inefficace
LinkedList<String> liste = new LinkedList<>();
// ... remplissage de la liste
for (int i = 0; i < liste.size(); i++) {
    System.out.println(liste.get(i)); // O(n) à chaque itération !
}

// ✅ Bonne pratique - utiliser un itérateur
for (String element : liste) {
    System.out.println(element); // O(1) par élément
}

Piège 2 : Choisir ArrayList pour de nombreuses insertions au début

// ❌ Inefficace avec ArrayList
ArrayList<String> messages = new ArrayList<>();
for (String nouveauMessage : nouveauxMessages) {
    messages.add(0, nouveauMessage); // O(n) à chaque insertion !
}

// ✅ Plus efficace avec LinkedList
LinkedList<String> messages = new LinkedList<>();
for (String nouveauMessage : nouveauxMessages) {
    messages.addFirst(nouveauMessage); // O(1) à chaque insertion
}

Conclusion et réflexions avancées

Comprendre la différence entre ArrayList et LinkedList va bien au-delà de la simple mémorisation de leurs caractéristiques. C’est une porte d’entrée vers une réflexion plus profonde sur le choix des structures de données appropriées selon le contexte.

Dans la pratique, ArrayList est plus souvent le bon choix, car la plupart des applications effectuent plus d’accès en lecture que d’insertions/suppressions au milieu des collections. Cependant, connaître les forces de LinkedList vous permettra de l’utiliser efficacement dans les situations où elle excelle vraiment.

Cette question d’entretien révèle finalement votre capacité à analyser un problème, comprendre les trade-offs, et faire des choix techniques éclairés. Ces compétences sont exactement ce que recherchent les recruteurs : un développeur qui ne se contente pas d’utiliser les outils, mais qui comprend pourquoi et quand les utiliser.

La prochaine fois qu’on vous posera cette question, vous pourrez non seulement expliquer les différences techniques, mais aussi démontrer votre compréhension des implications pratiques et votre capacité à faire des choix architecturaux réfléchis.

Questions fréquentes