Quel type de collection est le mieux adapté pour ajouter efficacement des éléments au milieu de la structure?

Pour ajouter efficacement des éléments au milieu d'une structure en Java, la collection LinkedList est la plus adaptée.

LinkedList implémente une liste doublement chaînée, ce qui permet d'insérer des éléments à n'importe quel endroit de la liste en temps O(1), si l'on dispose d'une référence au nœud concerné. Contrairement à ArrayList, où l'insertion au milieu nécessite de décaler les éléments et prend O(n).

Exemple d'utilisation de LinkedList :

import java.util.LinkedList;

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

// Insérer "C" à la position 2 (entre B et D)
list.add(2, "C");

System.out.println(list); // [A, B, C, D]

Si vous devez accéder fréquemment aux éléments par indice, il faut prendre en compte que LinkedList a un accès O(n), contrairement à ArrayList qui a un accès O(1).