Qual é a complexidade temporal de inserir um elemento no meio de uma lista ligada, se você já tiver um array preenchido?

Se tiver um array preenchido e desejar inserir um elemento no meio de uma lista ligada, primeiro deve encontrar a posição de inserção na lista. A complexidade temporal para procurar um elemento numa lista ligada é O(n), pois é necessário percorrer os elementos até à posição desejada.

Depois de encontrar a posição, a inserção do elemento na lista ligada ocorre em O(1), pois basta reatribuir os links.

Assim, a complexidade temporal total para inserir um elemento no meio de uma lista ligada, na presença de um array (que pode ajudar a encontrar rapidamente o índice, mas não o nó da lista), será O(n), pois a procura do nó leva tempo linear.

Se tiver um array que armazena referências para os nós da lista ligada (por exemplo, um array de ponteiros para os elementos da lista), então a inserção pode ser feita em O(1), pois obtém diretamente o nó necessário.

Exemplo:

// Suponhamos que temos uma lista ligada e um array de nós
Node[] arrayNodos = ...; // array de nós da lista ligada
int indiceInsercao = arrayNodos.length / 2;
Node nodoAntes = arrayNodos[indiceInsercao - 1];
Node novoNodo = new Node(valor);
novoNodo.next = nodoAntes.next;
nodoAntes.next = novoNodo;
// Inserção realizada em O(1)

Se não tiver um array com nós, então é necessário percorrer a lista até à posição desejada — O(n).