Que vaut-il mieux utiliser : ArrayList ou LinkedList, si je veux supprimer un élément du milieu de la liste ?

ArrayList.

Lors de la suppression d’un élément du milieu de la liste :

• ArrayList : Nécessite de décaler tous les éléments suivants, ce qui dans le pire cas (suppression du premier élément) prend du temps $O(n)$, où $n$ est le nombre d’éléments. Cependant, en moyenne, l’opération reste $O(n)$, car il faut déplacer seulement la moitié des éléments. La performance réelle est souvent meilleure grâce à une meilleure localité des données.
• LinkedList : Nécessite d’itérer jusqu’à trouver le nœud souhaité ($O(n)$ dans le pire cas, si l’itération commence du début ou de la fin). Après avoir trouvé le nœud, la suppression prend $O(1)$.

Bien que la suppression du nœud en soi dans LinkedList soit plus rapide, la recherche du nœud avant la suppression rend l’opération en moyenne plus lente qu’avec ArrayList.

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

public class ListRemovalComparison {

    public static void main(String[] args) {
        int size = 100000; // Taille de la liste
        int removeIndex = size / 2; // Index pour la suppression (milieu)

        // ArrayList
        List<Integer> arrayList = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            arrayList.add(i);
        }

        long startTimeArrayList = System.nanoTime();
        arrayList.remove(removeIndex); // Suppression du milieu
        long endTimeArrayList = System.nanoTime();
        long durationArrayList = (endTimeArrayList - startTimeArrayList);

        System.out.println("Temps de suppression d’un ArrayList : " + durationArrayList + " ns");

        // LinkedList
        List<Integer> linkedList = new LinkedList<>();
        for (int i = 0; i < size; i++) {
            linkedList.add(i);
        }

        long startTimeLinkedList = System.nanoTime();
        linkedList.remove(removeIndex); // Suppression du milieu
        long endTimeLinkedList = System.nanoTime();
        long durationLinkedList = (endTimeLinkedList - startTimeLinkedList);

        System.out.println("Temps de suppression d’un LinkedList : " + durationLinkedList + " ns");
    }
}

Les résultats du benchmark montrent que, pour supprimer un élément du milieu, ArrayList est généralement plus rapide, malgré la complexité théorique du décalage. Cela est dû au fait que la recherche par index dans LinkedList ($O(n)$) est plus lente que le décalage dans ArrayList.

// ArrayList - accès par index O(1), suppression O(n) (décalage)
ArrayList<String> arrayList = new ArrayList<>();
arrayList.add("A");
arrayList.add("B");
arrayList.add("C");
arrayList.remove(1); // Suppression de "B" - nécessite le décalage de "C"

// LinkedList - accès par index O(n), suppression O(1) (après avoir trouvé le nœud)
LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("A");
linkedList.add("B");
linkedList.add("C");
linkedList.remove(1); // Suppression de "B" - il faut d’abord trouver le nœud "B" (O(n)), puis supprimer (O(1))

En résumé, pour l’opération de suppression du milieu, si vous connaissez l’indice, ArrayList est souvent un choix plus préféré en raison de sa opération d’accès plus rapide par indice, ce qui compense le coût du décalage.