Qual tipo de coleção é mais adequado para adicionar elementos de forma eficiente no meio da estrutura?

Para adicionar elementos de forma eficiente ao meio de uma estrutura em Java, a coleção LinkedList é a mais adequada.

LinkedList implementa uma lista duplamente ligada, o que permite inserir elementos em qualquer lugar da lista em tempo O(1), se houver uma referência para o nó necessário. Ao contrário do ArrayList, onde inserir no meio requer deslocar elementos e leva O(n).

Exemplo de uso do LinkedList:

import java.util.LinkedList;

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

// Inserir "C" na posição 2 (entre B e D)
list.add(2, "C");

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

Se precisar acessar frequentemente elementos por índice, deve-se considerar que o acesso ao LinkedList é O(n), ao contrário do ArrayList, que é O(1).