Numa qual estrutura de dados a inserção de um elemento no meio é mais rápida: em ArrayList ou LinkedList?

A inserção de um elemento no meio é mais rápida em LinkedList do que em ArrayList, se considerarmos apenas a operação de inserção.

A razão é que:

• Em ArrayList, os elementos são armazenados numa matriz, por isso ao inserir no meio, é necessário deslocar todos os elementos seguintes para a direita, o que leva O(n) tempo.

• Em LinkedList, os elementos estão ligados por referências, portanto basta alterar as referências dos nós vizinhos para inserir um novo elemento, o que leva O(1) para a inserção em si, mas a procura da posição de inserção é O(n).

Assim, se já tiver uma referência para o nó necessário, a inserção na LinkedList é mais rápida. Mas se precisar primeiro encontrar a posição, o tempo é aproximadamente o mesmo.

Exemplo:

List<String> list = new LinkedList<>();
// adiciona elementos
list.add("a");
list.add("b");
list.add("c");

// insere no meio
list.add(1, "x");