¿Cuál es la complejidad temporal de insertar un elemento en el medio de una lista enlazada si ya tienes un array lleno?

Si tienes un array lleno y quieres insertar un elemento en el medio de una lista enlazada, primero debes encontrar la posición de inserción en la lista. La complejidad temporal para buscar un elemento en una lista enlazada es O(n), ya que necesitas recorrer los elementos hasta la posición deseada.

Una vez que se encuentra la posición, la inserción del elemento en la lista enlazada se realiza en O(1), ya que basta con redirigir los enlaces.

Por lo tanto, la complejidad temporal total para insertar un elemento en el medio de una lista enlazada, cuando se tiene un array (que puede ayudar a encontrar rápidamente el índice, pero no el nodo de la lista), será O(n), ya que la búsqueda del nodo ocupa tiempo lineal.

Si tienes un array que almacena referencias a los nodos de la lista enlazada (por ejemplo, un array de punteros a los elementos de la lista), entonces la inserción puede realizarse en O(1), ya que obtienes directamente el nodo necesario.

Ejemplo:

// Supongamos que tenemos una lista enlazada y un array de nodos
Node[] arrayNodos = ...; // array de nodos de la lista enlazada
int indiceInsercion = arrayNodos.length / 2;
Node nodoAntes = arrayNodos[indiceInsercion - 1];
Node nuevoNodo = new Node(valor);
nuevoNodo.next = nodoAntes.next;
nodoAntes.next = nuevoNodo;
// La inserción se realiza en O(1)

Si no tienes un array con nodos, entonces necesitas recorrer la lista hasta la posición deseada — O(n).