Clase 16. Variantes de la lista enlazada¶
Viernes 2 de octubre de 2026, de 14:00 a 17:00.
La lista enlazada con la que se construyó el TAD guarda en cada nodo el dato y la dirección del siguiente. Con eso insertar al frente cuesta dos escrituras, pero borrar un nodo que ya se tiene localizado obliga a recorrer la lista entera buscando quién lo apunta, y llegar a la posición \(p\) cuesta \(p\) pasos sin excepción. Esta sesión agrega un campo, cierra la cadena sobre sí misma y guarda un contador, y mide qué compra cada una de las tres decisiones y qué cobra a cambio. Después usa la estructura para lo que mejor hace: ordenar partiendo, ordenando cada mitad y mezclando.
Al terminar, el objetivo es poder construir la lista doblemente enlazada y la circular diciendo qué operación baja de costo en cada una; explicar por qué caminar por el lado más corto parte el trabajo a la mitad sin mover la cota \(\Theta(n)\); ordenar una lista enlazada con merge sort y escribir la recurrencia \(T(n) = 2T(n/2) + \Theta(n)\) que da \(\Theta(n \log n)\); y decir por qué la mezcla sobre nodos ocupa \(\Theta(1)\) de espacio aparte mientras sobre un arreglo ocupa \(\Theta(n)\).
Diapositivas¶
Lo que compró el puntero al último¶
La cadena arranca en cabeza y termina en el nodo cuyo campo siguiente vale
NULL. Insertar al frente son dos escrituras de puntero, nuevo->siguiente =
cabeza y cabeza = nuevo, y ningún nodo que ya estaba se mueve. Llegar a la
posición \(p\) son \(p\) pasos, porque la dirección del nodo \(p\) no se calcula: se
sigue la cadena.
Los números de insertar al frente diez veces quedaron medidos: el arreglo hace 45 corrimientos, \(0 + 1 + \cdots + 9\), y la enlazada hace 20 escrituras de puntero, dos por inserción. Con mil elementos son 499 500 contra 2000. Esa es la operación que la enlazada regala.
Guardar aparte la dirección del último nodo bajó agregar de \(\Theta(n)\) a
\(\Theta(1)\) y cobró su precio en eliminar, que ganó dos casos: borrar el
único elemento, que devuelve ultimo a NULL, y borrar el último, que mueve
ultimo al anterior y obliga a buscarlo.
Queda una operación sin arreglar, y es la que abre la sesión. Supongamos que el programa ya tiene en la mano un puntero al nodo que quiere borrar, porque venía recorriendo la lista o porque lo guardó antes. ¿Cuánto cuesta sacarlo?
Cuesta toda la lista. Para desenlazar un nodo hay que reescribir el campo
siguiente del anterior, y un nodo sabe cuál es el que sigue y no cuál es
el que lo apunta. Hay que buscar al anterior desde la cabeza: \(\Theta(n)\),
aunque el empalme en sí sean dos asignaciones. Tener el nodo no sirve de nada
si el nodo no sabe de dónde viene.
Esa es la operación que paga la primera variante.
El nodo que mira atrás¶
Un campo más¶
struct Nodo {
Elemento dato;
Nodo *anterior;
Nodo *siguiente;
};
Sobre \(\langle 5, 2, 7 \rangle\) el dibujo tiene dos juegos de flechas. Las de
arriba van hacia adelante, del 5 al 2 y del 2 al 7; las de abajo van hacia
atrás, del 7 al 2 y del 2 al 5. En los extremos los dos campos que no tienen a
quién apuntar valen NULL: el anterior del primer nodo y el siguiente del
último. La cadena sigue teniendo puntas, y las puntas se reconocen por ese
NULL.
La clase guarda cabeza, ultimo y n. Mantener ultimo ya no cuesta nada
extra: los enlaces van en los dos sentidos, así que el último se alcanza desde
el anterior sin recorrer.
Invariante de representación
Sea \(\mathrm{Alc}\) el conjunto de nodos que se alcanzan desde cabeza
siguiendo el campo siguiente un número finito de veces, sea
\(m = |\mathrm{Alc}|\), y sea \(v_0, v_1, \ldots\) la sucesión definida por
\(v_0 = \texttt{cabeza}\) y \(v_{i+1} = v_i\texttt{->siguiente}\) mientras
\(v_i \neq \texttt{NULL}\).
La sucesión de elementos que el contrato nombra es \(L = \langle v_0\texttt{->dato}, \ldots, v_{n-1}\texttt{->dato} \rangle\).
Los tres primeros son los de la lista simple. Los que llegan con el campo
nuevo son \(I_4\) y \(I_5\), y \(I_5\) es el que hay que vigilar en cada
modificación: dice que las dos direcciones cuentan la misma historia. Si
insertar escribe el enlace hacia adelante y olvida el de vuelta, el recorrido
de ida sale bien y el de regreso se salta un nodo o se cae. Es el error que no
aparece hasta que alguien recorre al revés.
Desenlazar sin recorrer¶
// Saca el nodo de la cadena. No recorre nada: por eso se guarda anterior.
void desenlazar(Nodo *x) {
if (x->anterior == NULL) {
cabeza = x->siguiente;
} else {
x->anterior->siguiente = x->siguiente;
}
if (x->siguiente == NULL) {
ultimo = x->anterior;
} else {
x->siguiente->anterior = x->anterior;
}
}
Con a, x y b consecutivos, lo que pasa es que el siguiente de a pasa
a ser b y el anterior de b pasa a ser a. El nodo x queda desacoplado
de la cadena sin que nadie haya caminado hasta él: ya estaba en la mano.
Cuatro escrituras de puntero en el peor caso, \(\Theta(1)\).
Los dos if son los extremos. Cuando x es el primero no hay un a a quien
reescribirle el siguiente, y lo que cambia es cabeza; cuando es el último
no hay un b, y lo que cambia es ultimo. Vale la pena mirar la línea
x->siguiente->anterior = x->anterior con esa guarda puesta: x->siguiente
tiene que ser un nodo para que escribir en su campo anterior signifique algo.
Sin el if, cuando x es el último se escribe sobre NULL.
void eliminar(int p) {
assert(0 <= p && p < n);
Nodo *muerto = nodoEn(p);
desenlazar(muerto);
delete muerto;
n = n - 1;
}
eliminar(p) sigue costando \(\Theta(p)\), y el costo está entero en nodoEn,
que camina. Lo que bajó a \(\Theta(1)\) es borrar un nodo que ya se tiene, y eso
es justo lo que pasa al recorrer la lista borrando, o al guardar punteros a
elementos para quitarlos después. El campo anterior compra esa operación y
no la otra.
Lo que cobra el campo nuevo¶
insertar mantiene ahora dos enlaces por nodo, y los extremos le abren cuatro
casos: lista vacía, al frente, al final y en medio.
if (n == 0) {
nuevo->anterior = NULL;
nuevo->siguiente = NULL;
cabeza = nuevo;
ultimo = nuevo;
} else if (p == 0) {
nuevo->anterior = NULL;
nuevo->siguiente = cabeza;
cabeza->anterior = nuevo;
cabeza = nuevo;
} else if (p == n) {
nuevo->anterior = ultimo;
nuevo->siguiente = NULL;
ultimo->siguiente = nuevo;
ultimo = nuevo;
} else {
Nodo *x = nodoEn(p);
nuevo->anterior = x->anterior;
nuevo->siguiente = x;
x->anterior->siguiente = nuevo;
x->anterior = nuevo;
}
| Caso | Tiempo | Por qué |
|---|---|---|
| lista vacía | \(\Theta(1)\) | el nodo nuevo es cabeza y último a la vez |
| \(p = 0\) | \(\Theta(1)\) | cabeza está guardada |
| \(p = n\) | \(\Theta(1)\) | ultimo está guardado |
| \(0 < p < n\) | \(\Theta(p)\) | nodoEn(p) camina hasta el nodo que va a quedar detrás |
Los cuatro casos tienen la misma causa: en algún extremo falta un vecino. El
caso de la lista vacía existe porque no hay ni cabeza ni ultimo a los que
engancharse; el de \(p = 0\) existe porque el nodo nuevo no tiene anterior; el de
\(p = n\) existe porque no tiene siguiente. Solo el caso de en medio tiene
vecinos a los dos lados, y es el único donde las cuatro líneas del empalme
salen sin condicionales.
El orden de esas cuatro líneas no es libre. Primero se escriben los dos enlaces
del nodo nuevo, anterior y siguiente, y solo después se reescriben los de
los vecinos. Al revés, x->anterior ya vale nuevo cuando se lee, y la
dirección del nodo que estaba antes de x se pierde para siempre: la mitad de
la lista queda inalcanzable, con \(I_1\) e \(I_5\) rotos de un golpe.
Lo que se compró con el campo: desenlazar en \(\Theta(1)\), llegar al último en
un paso y recorrer hacia atrás. Lo que se paga: un puntero más por nodo, dos
enlaces que mantener en cada modificación y los cuatro casos de insertar.
Esos casos son el problema que resuelve la variante siguiente.
La cadena que se cierra¶
Sin NULL no hay extremos¶
Si el último apunta al primero y el primero al último, la cadena deja de tener
puntas. Desaparece NULL de todos los enlaces y con él desaparecen los casos
que existían solo porque a un nodo le faltaba un vecino.
La clase guarda cabeza y n, y nada más. El último ya no hay que guardarlo:
cabeza->anterior es el último nodo y se llega en un paso.
Invariante de representación
Para \(n > 0\), sea \(v_0 = \texttt{cabeza}\) y
\(v_{i+1} = v_i\texttt{->siguiente}\), y sea \(\mathrm{Alc}\) el conjunto de
nodos alcanzables desde cabeza por el campo siguiente.
\(J_3\) es todo el cambio, y está en el \(\bmod n\). En la lista doble el enlace
hacia adelante se acababa en el último nodo; aquí da la vuelta. Evaluado en
\(i = n-1\) dice \(v_{n-1}\texttt{->siguiente} = v_0\) y
\(v_0\texttt{->anterior} = v_{n-1}\), que es exactamente la afirmación de que
cabeza->anterior es el último.
\(J_1\) pasa a ser indispensable. En las variantes anteriores el recorrido se
detenía al encontrar NULL, así que el contador podía mentir sin colgar el
programa. Aquí no hay NULL en ningún enlace: lo único que detiene un
recorrido es haber dado \(n\) pasos. El destructor lo deja a la vista, porque
cuenta en vez de comparar contra NULL:
~Lista() {
int i = 0;
while (i < n) {
Nodo *muerto = cabeza;
cabeza = cabeza->siguiente;
delete muerto;
i = i + 1;
}
cabeza = NULL;
}
La autorreferencia
Un ciclo que recorra la circular con la condición de siempre,
actual != NULL, no termina nunca: ningún nodo vale NULL y el recorrido
da vueltas hasta que alguien lo mate. La condición de parada de esta
estructura es el contador, y por eso \(J_1\) dejó de ser un detalle de
contabilidad y pasó a ser lo que impide el ciclo infinito.
Insertar, con dos casos en vez de cuatro¶
void insertar(int p, Elemento e) {
assert(0 <= p && p <= n);
Nodo *nuevo = new Nodo;
nuevo->dato = e;
if (n == 0) {
nuevo->siguiente = nuevo;
nuevo->anterior = nuevo;
cabeza = nuevo;
} else {
// se empalma antes de x; con p == n, x es la cabeza y queda al final
Nodo *x = cabeza;
if (p < n) {
x = nodoEn(p);
}
nuevo->siguiente = x;
nuevo->anterior = x->anterior;
x->anterior->siguiente = nuevo;
x->anterior = nuevo;
if (p == 0) {
cabeza = nuevo;
}
}
n = n + 1;
}
Las cuatro líneas del empalme sirven para cualquier posición, porque
x->anterior siempre existe. Insertar al final es insertar antes de la cabeza:
en un círculo son el mismo lugar, y el código lo dice con
Nodo *x = cabeza; cuando \(p = n\). Sobre \(\langle 5, 2, 7 \rangle\), insertar
el 9 en la posición 3 lo deja entre el 7 y el 5, que es el final de la
sucesión y el vecino de la cabeza al mismo tiempo.
Con la lista vacía el nodo nuevo cierra el círculo consigo mismo: es su propio
siguiente y su propio anterior. Ese es el único caso aparte que queda, y
reaparece al borrar. Cuando \(n = 1\) no hay a quién reenlazar, así que cabeza
vuelve a NULL y la lista queda vacía.
Las dos circulares, la de este código y la que llega enseguida, responden
igual al contrato: circular_uso.cpp se compila una vez con cada cabecera y
las dos imprimen las mismas cuatro líneas.
La mitad del camino¶
Una pregunta de pasos¶
La lista circular doble tiene \(n = 10\) elementos y se pide la posición 8.
Caminando desde la cabeza hacia adelante son 8 pasos. Con los enlaces hacia
atrás y sabiendo que hay 10 elementos, hacen falta dos: cabeza->anterior es
la posición 9 y cabeza->anterior->anterior es la 8.
Las dos cosas que vuelven posible esa cuenta son el enlace anterior y el
contador n. Sin el enlace no hay camino de regreso; sin el contador no se
sabe cuál de los dos caminos es el corto, porque para saber que la 8 está a dos
pasos del final hay que saber que el final es la 9.
Caminar por el lado más corto¶
Nodo *nodoEn(int p) {
Nodo *actual = cabeza;
if (p <= n / 2) {
int i = 0;
while (i < p) {
actual = actual->siguiente;
i = i + 1;
}
} else {
int i = n;
while (i > p) {
actual = actual->anterior;
i = i - 1;
}
}
return actual;
}
La rama de abajo arranca en \(i = n\) con actual en la cabeza, y eso no es un
descuido de índices: en el círculo la cabeza ocupa a la vez la posición 0 y la
posición \(n\), así que empezar a contar desde \(n\) y retroceder hasta \(p\) da
\(n - p\) pasos y aterriza en el nodo correcto.
Con \(n = 10\), los pasos que cuesta cada posición por los dos caminos, medidos
por pasos.cpp:
| \(p\) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| de frente | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| por el lado corto | 0 | 1 | 2 | 3 | 4 | 5 | 4 | 3 | 2 | 1 |
La segunda fila sube hasta la mitad y baja. El empate está en la posición 5, que queda a cinco pasos por los dos lados, y de ahí en adelante conviene ir al revés. Recorriendo todas las posiciones una vez:
| \(n\) | de frente | por el lado corto |
|---|---|---|
| 10 | 45 | 25 |
| 100 | 4950 | 2500 |
| 1000 | 499 500 | 250 000 |
La cota no se movió¶
Teorema
Sea \(\mathit{pasos}(p)\) el número de pasos que da nodoEn(p) en la lista
circular doble, con \(0 \leq p < n\). Entonces
\(\mathit{pasos}(p) \leq \lceil n/2 \rceil\) para todo \(p\).
Demostración. Se procede de forma directa, separando los dos caminos que toma el código.
Desarrollo. Si \(p \leq \lfloor n/2 \rfloor\), el ciclo de la primera rama avanza desde \(i = 0\) hasta \(i = p\) y da exactamente \(p\) pasos, de modo que \(\mathit{pasos}(p) = p \leq \lfloor n/2 \rfloor \leq \lceil n/2 \rceil\).
Si \(p > \lfloor n/2 \rfloor\), el ciclo de la segunda rama retrocede desde \(i = n\) hasta \(i = p\) y da \(n - p\) pasos. Como \(p\) es entero y \(p > \lfloor n/2 \rfloor\), se sigue \(p \geq \lfloor n/2 \rfloor + 1\), y por lo tanto
donde la igualdad del medio usa \(n - \lfloor n/2 \rfloor = \lceil n/2 \rceil\), que vale para todo entero \(n\).
Conclusión. En los dos casos \(\mathit{pasos}(p) \leq \lceil n/2 \rceil\), de donde \(\mathit{pasos}(p) \in O(n)\) con testigos \(c = 1\) y \(k = 1\).
El peor caso pasó de \(n - 1\) pasos a \(\lceil n/2 \rceil\). Es la mitad del trabajo, y la cota siguió siendo \(\Theta(n)\).
Por qué \(\Theta(n/2) = \Theta(n)\)¶
Las dos afirmaciones del párrafo anterior conviven, y conviene ver por qué sin quedarse en que «la notación ignora las constantes».
\(\Theta(g)\) no es un número: es el conjunto de funciones que crecen como \(g\). Una función \(f\) está en \(\Theta(g)\) cuando existen \(c_1, c_2 > 0\) y \(k\) tales que \(c_1 \, g(n) \leq f(n) \leq c_2 \, g(n)\) para todo \(n \geq k\). Con \(f(n) = n/2\) y \(g(n) = n\) los testigos salen de inmediato: \(c_1 = c_2 = 1/2\) y \(k = 1\), porque \(\tfrac{1}{2}n \leq n/2 \leq \tfrac{1}{2}n\) para todo \(n\). Entonces \(n/2 \in \Theta(n)\), y por el mismo argumento \(n \in \Theta(n/2)\). Los dos conjuntos tienen exactamente los mismos elementos, y escribir \(\Theta(n/2)\) o escribir \(\Theta(n)\) es escribir el mismo conjunto.
Visto desde los números medidos, dos funciones están en el mismo \(\Theta\) cuando el cociente entre ellas se queda entre dos constantes positivas por grandes que se hagan. La tabla de arriba lo muestra: el cociente entre las dos columnas es \(45/25 = 1{,}8\) con \(n = 10\), \(4950/2500 = 1{,}98\) con \(n = 100\) y \(499\,500/250\,000 = 1{,}998\) con \(n = 1000\). Se acerca a 2 y se queda ahí.
El contraste está en la comparación entre las dos implementaciones del TAD
Lista, insertar al frente en el arreglo y en la enlazada. Ahí los cocientes
eran \(45/20 = 2{,}25\), \(4950/200 = 24{,}75\) y \(499\,500/2000 = 249{,}75\): no se
acercan a nada, crecen con \(n\). Eso es \(\Theta(n^2)\) contra \(\Theta(n)\), y es
una diferencia de otra clase. Duplicar \(n\) duplica el trabajo de las dos
versiones de nodoEn; lo que cambió fue cuánto trabajo hay para cada \(n\), no
cómo crece.
La consecuencia práctica aparece cuando dos algoritmos comparten la cota. La cota ya no distingue, así que hay que mirar dos cosas más: el factor constante, que es la mitad en este caso, y el espacio que pide cada uno. El factor es lo que acaba de medirse. El espacio aparece en la sección siguiente, con dos formas de ordenar que corren en \(\Theta(n \log n)\) y no ocupan lo mismo.
Ordenar partiendo y mezclando¶
Lo que frenaba a insertion sort¶
Insertion sort acomoda un elemento a la vez contra el trozo que ya quedó ordenado. Sobre la lista enlazada el corrimiento desaparece, porque meter un nodo en su lugar es un empalme y ningún dato se mueve, pero encontrar ese lugar exige caminar desde la cabeza. La vuelta \(j\) puede recorrer \(j\) nodos, así que el peor caso sigue siendo \(\Theta(n^2)\). Se cambió mover datos por seguir punteros, y son la misma cantidad de pasos.
La otra idea es no acomodar un elemento contra todos los anteriores. Se parte la lista en dos, se ordena cada mitad y se combinan las dos mitades ya ordenadas. Combinar dos listas ordenadas es barato: se comparan las dos cabezas y se toma la menor, porque en una lista ordenada la cabeza es el mínimo.
Son tres pasos: dividir la lista en dos mitades, conquistar ordenando cada una con el mismo procedimiento, y combinar mezclando las dos (CLRS, 4.ª edición, sección 2.3).
Dividir con dos punteros a distinta velocidad¶
La lista no tiene índices, así que la mitad no se calcula: se encuentra. Un puntero avanza de a un nodo y otro de a dos; cuando el rápido llega al final, el lento va por la mitad. Es la carrera de dos motos, una a 30 y otra a 60: cuando la rápida llega, la lenta va por la mitad del camino.
Nodo *partir(Nodo *cabeza) {
Nodo *lento = cabeza;
Nodo *rapido = cabeza->siguiente;
while (rapido != NULL && rapido->siguiente != NULL) {
lento = lento->siguiente;
rapido = rapido->siguiente->siguiente;
}
Nodo *segunda = lento->siguiente;
lento->siguiente = NULL;
return segunda;
}
Sobre \(\langle 6, 2, 9, 4, 1, 7 \rangle\):
| vuelta | lento señala | rápido señala |
|---|---|---|
| inicio | 6 | 2 |
| 1 | 2 | 4 |
| 2 | 9 | 7 |
| fin | 9 | NULL tras 7 |
Se corta después del 9 y quedan \(\langle 6, 2, 9 \rangle\) y
\(\langle 4, 1, 7 \rangle\). La línea lento->siguiente = NULL es la que
convierte una cadena en dos: sin ella las dos mitades siguen siendo la misma
lista y la recursión no termina.
Un solo recorrido y ningún nodo nuevo: \(\Theta(n)\) en tiempo y \(\Theta(1)\) en espacio. Con un número impar de nodos la primera mitad queda con uno más.
Combinar: empalmar, no copiar¶
Nodo *mezclar(Nodo *a, Nodo *b) {
Nodo guia;
guia.dato = 0;
guia.siguiente = NULL;
Nodo *cola = &guia;
while (a != NULL && b != NULL) {
if (a->dato <= b->dato) {
cola->siguiente = a;
a = a->siguiente;
} else {
cola->siguiente = b;
b = b->siguiente;
}
cola = cola->siguiente;
}
if (a != NULL) {
cola->siguiente = a;
} else {
cola->siguiente = b;
}
return guia.siguiente;
}
El nodo guia vive en la pila y su campo dato no se usa. Está para que la
primera vuelta escriba cola->siguiente igual que todas las demás, sin un caso
aparte para la mezcla todavía vacía. Al final se devuelve lo que quedó colgando
de él, no él.
Cuando una de las dos cadenas se acaba, lo que queda de la otra ya está ordenado y es mayor o igual que todo lo que salió, así que se cuelga entero de una sola asignación. Esa es la razón de que mezclar no tenga que volver atrás: al comparar el 3 con el 7 y tomar el 3, lo que viene después del 7 en su cadena es mayor que 7, y por lo tanto mayor que 3.
No se reserva ni un nodo y no se copia ni un dato: solo se reescribe el campo
siguiente. Los nodos de la salida son los mismos de la entrada, en otro
orden. Por eso la mezcla ocupa \(\Theta(1)\) de espacio aparte.
Lo que sostiene el ciclo
Sean \(A\) y \(B\) los multiconjuntos de los datos que traen las cadenas \(a\) y
\(b\) al entrar. Al empezar una vuelta cualquiera, sea
\(M = \langle M[0], \ldots, M[|M|-1] \rangle\) la cadena que cuelga de
guia, y sean \(R_a\) y \(R_b\) los multiconjuntos de los datos que quedan en
\(a\) y en \(b\).
\(I_1\) dice que lo mezclado está en orden. \(I_2\) dice que lo que falta no es menor que lo último que se puso, y es el que permite agregar al final sin revisar hacia atrás. \(I_3\) dice que no se perdió ni se inventó ningún dato, contados con repetición. Cuando el ciclo termina, una de las dos cadenas se vació, y \(I_2\) es lo que autoriza a colgar el resto de la otra sin comparar nada más.
El algoritmo completo¶
// Una lista de cero o un nodo ya esta ordenada.
Nodo *ordenar(Nodo *cabeza) {
if (cabeza != NULL && cabeza->siguiente != NULL) {
Nodo *segunda = partir(cabeza);
cabeza = mezclar(ordenar(cabeza), ordenar(segunda));
}
return cabeza;
}
El caso base es la lista de cero o un nodo, que ya está ordenada por tener un
solo elemento, y es donde la recursión se detiene. El caso recursivo parte,
manda cada mitad al mismo procedimiento y mezcla lo que vuelve. Las dos
llamadas a ordenar están adentro de la llamada a mezclar, así que las dos
mitades llegan ordenadas y mezclar puede suponer lo que \(I_1\) exige.
Las ocho, paso a paso¶
Sobre \(\langle 6, 2, 9, 4, 1, 7, 3, 8 \rangle\), bajando hasta listas de un nodo y subiendo mezclando:
| Nivel | Al bajar, partir deja |
Al subir, mezclar devuelve |
|---|---|---|
| 0 | \(\langle 6\,2\,9\,4\,1\,7\,3\,8 \rangle\) | \(\langle 1\,2\,3\,4\,6\,7\,8\,9 \rangle\) |
| 1 | \(\langle 6\,2\,9\,4 \rangle\) \(\langle 1\,7\,3\,8 \rangle\) | \(\langle 2\,4\,6\,9 \rangle\) \(\langle 1\,3\,7\,8 \rangle\) |
| 2 | \(\langle 6\,2 \rangle\) \(\langle 9\,4 \rangle\) \(\langle 1\,7 \rangle\) \(\langle 3\,8 \rangle\) | \(\langle 2\,6 \rangle\) \(\langle 4\,9 \rangle\) \(\langle 1\,7 \rangle\) \(\langle 3\,8 \rangle\) |
| 3 | \(\langle 6 \rangle \langle 2 \rangle \langle 9 \rangle \langle 4 \rangle \langle 1 \rangle \langle 7 \rangle \langle 3 \rangle \langle 8 \rangle\) | ya están ordenadas |
Las comparaciones que cuesta subir, por nivel:
| Nivel | Comparaciones | De dónde salen |
|---|---|---|
| 2 | 4 | cuatro mezclas de uno contra uno |
| 1 | 6 | dos mezclas de dos contra dos |
| 0 | 7 | una mezcla de cuatro contra cuatro |
| 17 |
El programa cuenta 17 sobre esa entrada. Cada nivel toca los 8 nodos y hay \(\log_2 8 = 3\) niveles de mezcla, y ahí está el \(n \log n\): no en una vuelta larga, sino en pocas vueltas sobre todo.
Otra vez, con ocho valores distintos¶
Vale la pena seguir el árbol completo una segunda vez, ahora sobre \(\langle 2, 3, 1, 5, 7, 0, 9, 8 \rangle\), para ver que la forma del árbol no depende de los datos.
Bajando, partir corta siempre por la mitad:
| Nivel | Las cadenas |
|---|---|
| 0 | \(\langle 2\,3\,1\,5\,7\,0\,9\,8 \rangle\) |
| 1 | \(\langle 2\,3\,1\,5 \rangle\) \(\langle 7\,0\,9\,8 \rangle\) |
| 2 | \(\langle 2\,3 \rangle\) \(\langle 1\,5 \rangle\) \(\langle 7\,0 \rangle\) \(\langle 9\,8 \rangle\) |
| 3 | \(\langle 2 \rangle \langle 3 \rangle \langle 1 \rangle \langle 5 \rangle \langle 7 \rangle \langle 0 \rangle \langle 9 \rangle \langle 8 \rangle\) |
Subiendo, cada mezcla compara cabeza con cabeza:
| Nivel | Lo que devuelve mezclar |
Comparaciones |
|---|---|---|
| 2 | \(\langle 2\,3 \rangle\) \(\langle 1\,5 \rangle\) \(\langle 0\,7 \rangle\) \(\langle 8\,9 \rangle\) | 4 |
| 1 | \(\langle 1\,2\,3\,5 \rangle\) \(\langle 0\,7\,8\,9 \rangle\) | 5 |
| 0 | \(\langle 0\,1\,2\,3\,5\,7\,8\,9 \rangle\) | 5 |
| 14 |
La mezcla de \(\langle 2\,3 \rangle\) con \(\langle 1\,5 \rangle\) compara 2 con 1 y saca el 1; compara 2 con 5 y saca el 2; compara 3 con 5 y saca el 3; ahí se vació la primera cadena y el 5 se cuelga sin comparar. Tres comparaciones para cuatro nodos. La final, entre \(\langle 1\,2\,3\,5 \rangle\) y \(\langle 0\,7\,8\,9 \rangle\), saca el 0, después el 1, el 2, el 3 y el 5, y cuando la primera cadena se vacía cuelga \(\langle 7\,8\,9 \rangle\) entero: cinco comparaciones para ocho nodos.
Son 14 comparaciones contra las 17 de la entrada anterior, y el programa lo confirma. El árbol es el mismo y el total cambia, porque una cadena que se vacía temprano deja a la otra colgarse sin comparar. Mezclar dos cadenas con \(n\) nodos entre las dos cuesta a lo sumo \(n - 1\) comparaciones y puede costar bastante menos; lo que no cambia con los datos es que son \(\Theta(n)\) y que los niveles son \(\log_2 n\).
Lo que cuesta¶
Partir recorre la lista una vez y mezclar también, así que el trabajo fuera de las llamadas recursivas es \(\Theta(n)\). Cada llamada se parte en dos de tamaño \(n/2\):
El árbol de llamadas tiene \(\log_2 n\) niveles, cada nivel reparte los \(n\) nodos entre sus llamadas y hace \(\Theta(n)\) de trabajo en total, de donde \(T(n) = \Theta(n \log n)\) (CLRS, 4.ª edición, sección 2.3). No hay mejor ni peor caso: la lista se parte por la mitad sin mirar los datos, así que el árbol tiene la misma altura para cualquier entrada. Lo único que varía con los datos es el número exacto de comparaciones dentro de cada mezcla, como se acaba de ver con 17 y con 14.
| Función | Tiempo | Espacio aparte de la lista | Por qué |
|---|---|---|---|
partir |
\(\Theta(n)\) | \(\Theta(1)\) | un recorrido con dos punteros; no reserva nodos |
mezclar |
\(\Theta(n_a + n_b)\) | \(\Theta(1)\) | cada nodo se cuelga una vez; solo se reescribe siguiente |
ordenar |
\(\Theta(n \log n)\) | \(\Theta(\log n)\) | \(\log_2 n\) niveles de \(\Theta(n)\); la pila guarda un marco por nivel |
El \(\Theta(\log n)\) de ordenar es la pila de llamadas, no datos: cada llamada
anidada deja su marco mientras espera a las dos de adentro, y la profundidad de
ese anidamiento es la altura del árbol.
Sobre el arreglo cuesta más espacio¶
La mezcla sobre un arreglo no puede empalmar. Para intercalar dos mitades en el sitio habría que correr elementos, que es justo lo que se quería evitar, así que se escribe el resultado en un arreglo auxiliar y después se copia de vuelta. Eso es \(\Theta(n)\) de espacio extra y dos escrituras por elemento en cada nivel.
| Sobre la enlazada | Sobre el arreglo | |
|---|---|---|
| tiempo | \(\Theta(n \log n)\) | \(\Theta(n \log n)\) |
| espacio de la mezcla | \(\Theta(1)\) | \(\Theta(n)\) |
| qué se mueve | un puntero por nodo | cada elemento, dos veces por nivel |
Aquí cierra la cuenta que quedó abierta en la sección de los pasos. Las dos versiones tienen la misma cota de tiempo, y la cota no las distingue; lo que las distingue es el espacio. Es el único punto del curso donde la enlazada le gana al arreglo en un algoritmo completo, y gana justo por lo que la hacía cara: que los elementos no están pegados, y moverlos es reescribir una dirección.
Los dos algoritmos sobre la misma entrada¶
Comparaciones contadas por comparar.cpp sobre la misma permutación:
| \(n\) | insertion sort | merge sort | veces más |
|---|---|---|---|
| 16 | 82 | 46 | 1 |
| 128 | 4066 | 748 | 5 |
| 1024 | 258 018 | 8181 | 31 |
| 4096 | 4 088 802 | 37 214 | 109 |
Con 16 elementos merge sort hace 46 comparaciones contra 82, ni la mitad de trabajo ahorrada; con 4096 hace 109 veces menos. La ventaja aparece al crecer \(n\), que es exactamente lo que una cota asintótica afirma y lo único que afirma. Para un tamaño fijo y pequeño el algoritmo simple compite, y encima no paga la pila de llamadas.
Cómo crecen las comparaciones de merge sort sobre permutaciones mezcladas,
contadas por merge.cpp, contra el valor de \(n \log_2 n\):
| \(n\) | comparaciones | \(n \log_2 n\) |
|---|---|---|
| 8 | 16 | 24 |
| 64 | 317 | 384 |
| 512 | 3775 | 4608 |
| 1024 | 8181 | 10 240 |
La cuenta medida se queda por debajo de \(n \log_2 n\) y se le acerca. La cota superior no promete que el algoritmo llegue a ella, promete que no la pasa.
Lo que cobra cada implementación¶
\(n\) es el número de elementos y \(p\) la posición sobre la que se opera.
| Operación | Simple | Doble | Circular | Circular, lado corto | Por qué |
|---|---|---|---|---|---|
obtener(p), asignar(p, e) |
\(\Theta(p)\) | \(\Theta(p)\) | \(\Theta(p)\) | \(\Theta(\min(p, n-p))\) | ninguna calcula direcciones: hay que caminar, y el contador deja escoger el lado |
insertar(0, e) |
\(\Theta(1)\) | \(\Theta(1)\) | \(\Theta(1)\) | \(\Theta(1)\) | cabeza está guardada en todas |
insertar(p, e), eliminar(p) |
\(\Theta(p)\) | \(\Theta(p)\) | \(\Theta(p)\) | \(\Theta(\min(p, n-p))\) | el empalme es \(\Theta(1)\); lo caro es llegar al nodo |
agregar(e) |
\(\Theta(n)\), o \(\Theta(1)\) con ultimo |
\(\Theta(1)\) | \(\Theta(1)\) | \(\Theta(1)\) | el final está guardado, o se alcanza por cabeza->anterior |
| desenlazar un nodo que ya se tiene | \(\Theta(n)\) | \(\Theta(1)\) | \(\Theta(1)\) | \(\Theta(1)\) | sin el campo anterior hay que buscar quién apunta al nodo |
| llegar al último | \(\Theta(n)\), o \(\Theta(1)\) con ultimo |
\(\Theta(1)\) | \(\Theta(1)\) | \(\Theta(1)\) | en el círculo el último es el vecino de atrás de la cabeza |
| recorrer hacia atrás | no se puede | \(\Theta(n)\) | \(\Theta(n)\) | \(\Theta(n)\) | el camino de vuelta existe solo con el campo anterior |
tamano(), vacia() |
\(\Theta(1)\) | \(\Theta(1)\) | \(\Theta(1)\) | \(\Theta(1)\) | el contador está guardado |
| liberar la estructura | \(\Theta(n)\) | \(\Theta(n)\) | \(\Theta(n)\) | \(\Theta(n)\) | un delete por nodo |
casos de insertar |
2 | 4 | 2 | 2 | cada caso aparte existe porque en un extremo falta un vecino |
| espacio por nodo | dato y 1 puntero | dato y 2 | dato y 2 | dato y 2 | el camino de vuelta se paga en memoria |
| espacio de la estructura | \(\Theta(n)\) | \(\Theta(n)\) | \(\Theta(n)\) | \(\Theta(n)\) | un nodo por elemento en las cuatro |
| espacio aparte por operación | \(\Theta(1)\) | \(\Theta(1)\) | \(\Theta(1)\) | \(\Theta(1)\) | punteros y contadores sueltos |
Cuatro frases resumen la tabla. Todas caminan para llegar a una posición,
porque ninguna calcula direcciones, y ese es el precio de no estar en casillas
consecutivas. El campo anterior convierte el desenlace en cuatro escrituras
fijas, y a cambio cada modificación mantiene dos enlaces en vez de uno. Cerrar
el círculo borra los extremos y con ellos los casos que existían solo porque
faltaba un vecino. El contador deja escoger el lado: la cota sigue siendo
\(\Theta(n)\) y el peor caso baja de \(n-1\) pasos a \(\lceil n/2 \rceil\).
Ninguna de las cuatro gana en todo, y la columna que más se repite es la del espacio por nodo, que es donde se paga lo que las otras compran. La estructura se escoge por las operaciones que el programa repite, no por cuál se ve más completa, y esa cuenta se hace con la tabla a la vista antes de escribir el código. Para el proyecto del curso, el enunciado publicado es el documento que manda.
Lo que se vio¶
- En la lista doble cada nodo guarda también
anterior, y desenlazar un nodo que ya se tiene cuesta \(\Theta(1)\) en vez de \(\Theta(n)\). El precio es un puntero más por nodo y cuatro casos eninsertar. - Su invariante añade \(I_5\): \(v_i\texttt{->siguiente} = v_{i+1} \wedge v_{i+1}\texttt{->anterior} = v_i\). En el empalme se escriben primero los dos enlaces del nodo nuevo y después los de los vecinos; al revés, media lista queda inalcanzable.
- La circular doble cierra la cadena:
cabeza->anteriores el último einsertarse queda con dos casos. SinNULL, un recorrido conactual != NULLno termina, y lo único que lo detiene es contar \(n\) pasos. - Con el contador,
nodoEn(p)camina por el lado corto y da a lo sumo \(\lceil n/2 \rceil\) pasos. El peor caso se reduce a la mitad y la cota sigue en \(\Theta(n)\), porque \(\Theta(n/2) = \Theta(n)\). partirencuentra la mitad con un puntero lento y uno rápido: \(\Theta(n)\) en tiempo, \(\Theta(1)\) en espacio.mezclarsolo reescribesiguientey ocupa \(\Theta(1)\) aparte.- Merge sort cumple \(T(n) = 2\,T(n/2) + \Theta(n)\), así que \(T(n) = \Theta(n \log n)\) para cualquier entrada, con \(\Theta(\log n)\) de pila de llamadas.
- Sobre el arreglo la mezcla pide un auxiliar de \(\Theta(n)\); sobre la enlazada no. Con \(n = 4096\), merge sort hizo 37 214 comparaciones e insertion sort 4 088 802.
Ejercicios¶
Rotar la circular¶
Escriba rotar(int k) sobre la lista circular doble: la posición \(k\) pasa a
ser la cabeza y el orden circular no cambia. Con \(\langle 5, 2, 7, 4 \rangle\)
y \(k = 2\) queda \(\langle 7, 4, 5, 2 \rangle\).
- ¿Cuántos nodos hay que mover de sitio?
- ¿Cuánto cuesta con \(k = 1\)? ¿Y con \(k = n - 1\)?
- Escríbalo de modo que nunca dé más de \(\lceil n/2 \rceil\) pasos.
- ¿Se puede hacer lo mismo sobre la lista estática? ¿Qué costaría?
No se mueve ningún nodo. Lo único que cambia es a cuál apunta cabeza, porque
en un círculo todos los elementos ya están en su lugar relativo y rotar es
mirar el mismo círculo desde otro punto. Con \(k = 1\) es un paso hacia adelante
y con \(k = n - 1\) es un paso hacia atrás, así que escogiendo el sentido queda
\(\Theta(\min(k, n-k))\), y \(\lceil n/2 \rceil\) en el peor caso. Sobre el arreglo
hay que correr los \(n\) elementos, \(\Theta(n)\), y no hay manera de evitarlo:
allí la posición 0 es una casilla fija y no un nodo al que se pueda apuntar.
Quitar repetidos de una lista ordenada¶
La lista enlazada simple viene ordenada y trae repetidos: \(\langle 1, 1, 3, 5, 5, 5, 8 \rangle\). Deje una sola copia de cada valor, liberando los nodos que sobran.
- ¿Cuántos recorridos hacen falta?
- ¿Qué puntero hay que guardar antes de cada
delete, y por qué? - ¿Cuántos nodos se liberan en el ejemplo?
- ¿Cuánto cuesta en tiempo y en espacio aparte de la lista?
Un solo recorrido. Estando ordenada, los repetidos quedan consecutivos, así que
basta comparar cada nodo con el siguiente y, cuando son iguales, empalmar sobre
el siguiente del siguiente y liberar el de en medio. Antes del delete hay que
guardar el siguiente del nodo que se borra, que es a donde hay que enlazar;
leerlo después es leer memoria ya devuelta. Se liberan tres nodos y queda
\(\langle 1, 3, 5, 8 \rangle\). Es \(\Theta(n)\) en tiempo y \(\Theta(1)\) en
espacio, porque los nodos no se copian: se sueltan.
Si la lista no estuviera ordenada, los repetidos no serían consecutivos y habría que comparar cada nodo con todos los anteriores, \(\Theta(n^2)\). Ordenar primero con merge sort y después quitar repetidos cuesta \(\Theta(n \log n) + \Theta(n) = \Theta(n \log n)\), que es menos.
Para el juez¶
UVa 11462 — Age Sort, https://vjudge.net/problem/UVA-11462. Envío en https://vjudge.net/problem/UVA-11462.
Varios casos. Cada uno trae \(n\) edades de los habitantes de un país y hay que imprimirlas en orden ascendente, separadas por espacio, una línea por caso. El archivo termina con \(n = 0\). Los límites son \(0 < n \leq 2\,000\,000\), y el enunciado dice que todos tienen al menos un año y que nadie llega a los 100, de modo que las edades van de 1 a 99.
Merge sort ordena en \(\Theta(n \log n)\): con dos millones de edades son unos
\(2 \cdot 10^6 \times 21 \approx 4{,}2 \cdot 10^7\) comparaciones, que entran en
el tiempo. Hay tres trampas. El cuello de botella no es ordenar sino leer: el
enunciado avisa que la entrada pesa unos 25 MB y pide usar entrada y salida
rápidas, así que los dos millones de enteros se leen con scanf y se escriben
con printf. Una lista enlazada de dos millones de nodos pide dos millones de new, y el tiempo de reservar y el puntero por nodo
pesan: aquí gana el arreglo. Y el rango 1 a 99 es una cota sobre los valores,
no sobre la cantidad, y eso permite ordenar sin comparar y en \(\Theta(n)\).
Averiguar cómo es el ejercicio que deja planteado la sesión de tablas hash.
UVa 10810 — Ultra-QuickSort, https://vjudge.net/problem/UVA-10810. Envío en https://vjudge.net/problem/UVA-10810.
Varios casos, cada uno con \(n < 500\,000\) enteros entre 0 y 999 999 999, uno
por línea, y el archivo termina con \(n = 0\). Para cada caso hay que imprimir
cuántos intercambios de elementos vecinos hacen falta para dejar la sucesión en
orden ascendente. Con la entrada 9 1 0 5 4 la respuesta es 6.
El número que pide es la cantidad de pares en desorden, y es exactamente el
número de corrimientos que haría insertion sort, así que contarlos con
insertion sort es \(\Theta(n^2)\) y con medio millón de elementos no entra. La
cuenta se puede llevar dentro de mezclar sin tocar su costo: cuando se toma
un elemento de la segunda cadena, ese elemento se adelanta a todos los que
quedan en la primera, y hay que sumarlos. La trampa es el tipo. Con medio
millón de elementos la respuesta puede llegar a \(n(n-1)/2\), del orden de
\(1{,}2 \cdot 10^{11}\), y eso no cabe en 32 bits.
Para practicar en casa¶
Propuesto 1¶
Escriba buscar(Elemento x) sobre la circular doble recorriendo desde los dos
extremos a la vez, uno hacia adelante y otro hacia atrás. ¿Cuántas
comparaciones hace en el peor caso, y cuándo conviene frente a recorrer de
frente?
Propuesto 2¶
¿Qué pasa si se le pasa una lista circular a partir? Siga el ciclo del
puntero rápido con la condición rapido != NULL && rapido->siguiente != NULL y
diga en qué queda.
Propuesto 3¶
Con tres listas ordenadas de \(n\) nodos cada una, compare mezclarlas de a dos contra escribir una mezcla que compare las tres cabezas. ¿Cuántas comparaciones hace cada una?
Propuesto 4¶
Merge sort sobre la lista doblemente enlazada. ¿Qué hay que arreglar al
terminar la mezcla para que los enlaces anterior queden bien, y cambia el
costo?
Propuesto 5¶
Un nodo centinela es un nodo fijo que no guarda elementos y que siempre está al
frente de la cadena. ¿Cuáles de los casos de insertar y de eliminar
desaparecen con él, y qué invariante hay que reescribir?
Propuesto 6¶
Sobre la circular doble con \(n = 7\), escriba la fila de pasos por el lado corto para \(p = 0, \ldots, 6\) y compruebe que ninguno pasa de \(\lceil 7/2 \rceil = 4\).
Ejercicios interactivos¶
Cinco actividades que se trabajan en el navegador, una por tema de la sesión,
en la página de ejercicios interactivos: qué punteros se
reescriben al sacar un nodo de la cadena doble; insertar al frente y al final
sobre la circular prediciendo cada resultado; los pasos por los dos caminos con
doce elementos; dónde corta partir y cuántas comparaciones hace cada mezcla;
y qué variante conviene a cuatro perfiles de uso distintos. Los programas no
son los de la sesión: mismo tema, valores nuevos.
Lo que sigue¶
Pila y cola por dentro. Qué implementación le conviene a cada una cuando todas las operaciones ocurren por los extremos, cuál de las cuatro variantes sobra para ese perfil, y por qué una cola montada sobre arreglo necesita dar la vuelta al llegar al final en vez de correr los elementos.
Código de la sesión¶
Compilación y ejecución:
g++ -Wall -Wextra archivo.cpp -o archivo && ./archivo
El nodo que mira atrás
- doble.h — la lista doblemente enlazada, con el
desenlazarque saca un nodo en \(\Theta(1)\) porque no necesita buscar al anterior, y los cuatro casos deinsertar. - doble_uso.cpp — el mismo contrato corriendo sobre
ella: imprime
2 5 7 8 4, después5 8 4y cierra con3 0.
La cadena que se cierra
- circular.h — la circular doble: sin
NULLen ningún enlace,cabeza->anteriores el último einsertarpasa de cuatro casos a dos. - circular_rapida.h — la misma, con el
nodoEnque usa el contador para llegar a la posición por el lado más corto. - circular_uso.cpp — se compila una vez con cada cabecera y las dos responden igual.
Los dos de la lista circular se compilan escogiendo la cabecera:
g++ -Wall -Wextra -DCABECERA='"circular.h"' circular_uso.cpp -o circular
g++ -Wall -Wextra -DCABECERA='"circular_rapida.h"' circular_uso.cpp -o rapida
La mitad del camino
- pasos.cpp — cuántos pasos cuesta llegar a cada posición por los dos caminos, con los totales para 10, 100 y 1000 elementos.
Ordenar partiendo y mezclando
- merge.cpp — merge sort sobre la lista:
partircon el puntero lento y el rápido,mezclarempalmando nodos yordenar, con el contador de comparaciones. - comparar.cpp — insertion sort y merge sort sobre la misma entrada, contando comparaciones para \(n\) entre 16 y 4096.
Referencias¶
- R. Thareja. Data Structures Using C. Oxford University Press, 2018. Capítulo 6, listas enlazadas: circulares, doblemente enlazadas y circulares doblemente enlazadas.
- N. Kalicharan. Data Structures in C, 2008. Capítulo de listas enlazadas:
variantes y manejo de los nodos con
mallocyfree. - T. H. Cormen, C. E. Leiserson, R. L. Rivest y C. Stein. Introduction to Algorithms, 4.ª ed. MIT Press, 2022. Sección 2.3, merge sort y el análisis de la recurrencia; sección 10.2, listas enlazadas.