Operaciones de insercion y eliminacion en una lista simplemente enlazada

La idea en simple

Una lista enlazada es una cadena de nodos donde cada uno “apunta” al siguiente. Insertar o borrar es solo reconectar flechas, no mover datos.

Siguiendo las 4 operaciones sobre head -> [7] -> [3] -> [10]:

1. Insertar 5 al inicio $\rightarrow$ [5,7,3,10]. Facil y barato ($O(1)$): apuntas el nuevo a lo que habia y mueves head.
2. Insertar 15 al final $\rightarrow$ [5,7,3,10,15]. Barato en flechas (2), pero primero hay que caminar hasta el ultimo nodo $\rightarrow O(n)$.
3. Eliminar 3 $\rightarrow$ [5,7,10,15]. Basta una flecha: haces que el nodo anterior (7) apunte al que seguia (10). Pero hay que buscarlo $\rightarrow O(n)$.
4. Insertar 8 en la posicion 3 $\rightarrow$ [5,7,10,8,15]. Caminas hasta la posicion, reconectas dos flechas.

Lista final: head -> [5] -> [7] -> [10] -> [8] -> [15] -> NULL.

Lo importante — lista vs arreglo: para llegar al elemento numero $k$, la lista tiene que caminar $k$ pasos ($O(n)$), mientras que un arreglo salta directo con una cuenta ($O(1)$), porque sus elementos estan pegados en memoria. La lista es comoda para insertar/borrar sin correr elementos; el arreglo es imbatible para acceso directo por indice.

Solucion formal

Estado inicial: head -> [7] -> [3] -> [10] -> NULL, $n = 3$. Se cuentan solo asignaciones sobre ->enlace o head.

#	Operacion	Estado resultante	Asig.	Costo
1	Insertar 5 al inicio	[5,7,3,10]	2	$O(1)$
2	Insertar 15 al final	[5,7,3,10,15]	2	$O(n)$
3	Eliminar 3	[5,7,10,15]	1	$O(n)$
4	Insertar 8 en pos. 3	[5,7,10,8,15]	2	$O(n)$

Justificacion de costos.

• Op 1. nuevo->enlace = head; head = nuevo. Independiente de $n$ $\Rightarrow O(1)$.
• Op 2. Sin puntero tail hay que recorrer $n-1$ enlaces hasta el ultimo nodo antes de las 2 asignaciones de enlace $\Rightarrow O(n)$.
• Op 3. Buscar el predecesor del nodo objetivo es $O(n)$; la reconexion pred->enlace = victima->enlace es una unica asignacion.
• Op 4. Avanzar hasta la posicion $k=3$ es $O(k)$; la insercion local usa 2 asignaciones. Peor caso $O(n)$.

Lista final: head -> [5] -> [7] -> [10] -> [8] -> [15] -> NULL.

Acceso a la posicion $k$.

$T_{\text{lista}}(k) = \Theta(k) = O(n) \quad\text{(peor caso)}, \qquad T_{\text{arreglo}}(k) = \Theta(1).$

El arreglo usa memoria contigua: $\text{dir}(A[k]) = \text{base} + k\cdot s$ (con $s$ el tamano del elemento), un acceso directo. La lista guarda nodos no contiguos enlazados por siguiente, por lo que el acceso indexado exige recorrido secuencial. $\blacksquare$

Solucion

Estado inicial ($n = 3$):

head -> [7] -> [3] -> [10] -> NULL

Para contar asignaciones de punteros solo contamos las que modifican enlaces (->enlace) o head; las asignaciones de dato (nodo->dato = x) no son de puntero, y el recorrido con un cursor auxiliar se contabiliza aparte como costo de busqueda.

Operacion 1 — Insertar 5 al inicio

Nodo* nuevo = new Nodo;
nuevo->dato = 5;
nuevo->enlace = head;   // (1)
head = nuevo;           // (2)

(a) Resultado:

head -> [5] -> [7] -> [3] -> [10] -> NULL

(b) Asignaciones de punteros: 2 (nuevo->enlace = head, head = nuevo).

(c) Complejidad: $O(1)$ — no depende de $n$, insertar al inicio es siempre constante.

Operacion 2 — Insertar 15 al final

Sin puntero a la cola hay que recorrer hasta el ultimo nodo:

Nodo* nuevo = new Nodo;
nuevo->dato = 15;
nuevo->enlace = NULL;       // (1)
Nodo* p = head;
while (p->enlace != NULL) p = p->enlace;  // recorrido O(n)
p->enlace = nuevo;          // (2)

(a) Resultado:

head -> [5] -> [7] -> [3] -> [10] -> [15] -> NULL

(b) Asignaciones de enlace: 2 (nuevo->enlace = NULL, p->enlace = nuevo). Ademas el cursor p avanza $n-1$ veces durante la busqueda del final.

(c) Complejidad: $O(n)$ — dominada por el recorrido hasta el ultimo nodo. (Con un puntero tail seria $O(1)$.)

Operacion 3 — Eliminar el nodo con valor 3

Nodo* p = head;
while (p->enlace->dato != 3) p = p->enlace;  // p queda en [7]
Nodo* victima = p->enlace;      // [3]
p->enlace = victima->enlace;    // (1)  [7] -> [10]
delete victima;

(a) Resultado:

head -> [5] -> [7] -> [10] -> [15] -> NULL

(b) Asignaciones de enlace: 1 (p->enlace = victima->enlace). Se necesita mantener el puntero al nodo anterior para poder reconectar.

(c) Complejidad: $O(n)$ — hay que buscar el nodo (y su predecesor) recorriendo la lista.

Operacion 4 — Insertar 8 en la posicion 3 (indexada desde 0)

Lista actual con indices: 0:[5] 1:[7] 2:[10] 3:[15]. Insertar en la posicion 3 significa que $8$ pasa a ocupar el indice 3 y empuja a $15$ al indice 4; hay que enlazar despues del nodo en la posicion 2.

Nodo* p = head;
for (int i = 0; i < 2; i++) p = p->enlace;  // p queda en [10] (indice 2)
Nodo* nuevo = new Nodo;
nuevo->dato = 8;
nuevo->enlace = p->enlace;   // (1)  8 -> [15]
p->enlace = nuevo;           // (2)  [10] -> 8

(a) Resultado:

head -> [5] -> [7] -> [10] -> [8] -> [15] -> NULL

(b) Asignaciones de enlace: 2 (nuevo->enlace = p->enlace, p->enlace = nuevo). El cursor avanza $k-1 = 2$ posiciones.

(c) Complejidad: $O(n)$ en el peor caso — hay que avanzar hasta la posicion $k$; insertar en si es $O(1)$, pero llegar al punto es $O(k)$.

Resumen

Operacion	Resultado	Asignaciones de enlace	Complejidad
Insertar 5 al inicio	[5,7,3,10]	2	$O(1)$
Insertar 15 al final	[5,7,3,10,15]	2	$O(n)$
Eliminar 3	[5,7,10,15]	1	$O(n)$
Insertar 8 en pos. 3	[5,7,10,8,15]	2	$O(n)$

Lista final:

head -> [5] -> [7] -> [10] -> [8] -> [15] -> NULL

Acceso a la posicion $k$: lista vs. arreglo

En una lista enlazada, para llegar al elemento en la posicion $k$ hay que partir de head y seguir $k$ enlaces uno por uno:

Nodo* p = head;
for (int i = 0; i < k; i++) p = p->enlace;  // O(k)

Esto es $O(k)$, y en el peor caso ($k = n-1$) $O(n)$.

En un arreglo, el acceso es $O(1)$: los elementos ocupan memoria contigua, asi que la direccion del elemento $k$ se calcula directamente con aritmetica de punteros,

$\text{direccion}(A[k]) = \text{base} + k \cdot \text{tam(elemento)},$

sin recorrer nada. La lista enlazada, en cambio, guarda sus nodos dispersos en memoria y solo conoce el enlace siguiente, por lo que no puede saltar directamente al indice $k$: esta obligada a un recorrido secuencial.

Conclusion. La lista enlazada gana en inserciones/eliminaciones en extremos conocidos ($O(1)$ al inicio, o al final con tail) y no requiere desplazar elementos; el arreglo gana en acceso aleatorio por indice ($O(1)$ frente a $O(n)$). Es el clasico compromiso entre acceso directo y flexibilidad estructural.