¿Qué tipo de colección es más adecuado para agregar elementos de manera eficiente en el medio de la estructura?

Para agregar elementos de manera eficiente en medio de una estructura en Java, la colección LinkedList es la más adecuada.

LinkedList implementa una lista doblemente enlazada, lo que permite insertar elementos en cualquier lugar de la lista en tiempo O(1), si se tiene una referencia al nodo necesario. A diferencia de ArrayList, donde insertar en medio requiere desplazar elementos y toma O(n).

Ejemplo de uso de LinkedList:

import java.util.LinkedList;

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

// Insertar "C" en la posición 2 (entre B y D)
list.add(2, "C");

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

Si necesitas acceder frecuentemente a los elementos por índice, debes tener en cuenta que LinkedList tiene acceso O(n), a diferencia de ArrayList que tiene acceso O(1).