En la lección anterior encadenamos nodos a mano y terminamos con expresiones tan incómodas como cabeza.siguiente.siguiente.siguiente. Hoy encapsulamos toda esa mecánica en una clase ListaEnlazada que cumple el contrato del TDA lista: insertar (al inicio, al final y en posición), borrar, buscar, recorrer, y los métodos mágicos __len__ y __str__ para que se comporte como una estructura de Python de pleno derecho. Además de construirla, la someteremos al mismo escrutinio que a todo lo demás en este curso: análisis Big O operación por operación y verificación empírica con timeit, enfrentándola a la list de Python justo donde esta flaqueaba —insertar por delante—. Al final, el tablero de TaskFlow pasará a vivir sobre nuestra nueva estructura.

1. Las piezas: Nodo y el esqueleto de ListaEnlazada
2. Insertar al inicio y al final (y el truco de la cola)
3. Recorrer, __len__ y __str__
4. Buscar y insertar en una posición
5. Borrar: el patrón del nodo anterior
6. Análisis Big O de todas las operaciones
7. La revancha: timeit contra list insertando por delante
8. TaskFlow v0.2: el tablero como lista enlazada

Partimos de la clase Nodo de la lección anterior, sin cambios, y añadimos la clase contenedora que guardará las referencias estratégicas:

Tres decisiones de diseño que conviene entender antes de seguir:

• cabeza: el único punto de entrada imprescindible. Si es None, la lista está vacía.
• cola: referencia directa al último nodo. No es obligatoria en una lista enlazada, pero sin ella insertar al final exigiría caminar toda la lista (O(n)); con ella será O(1). Es el truco que dejamos anunciado en la tabla de 02-01. El precio: cada operación debe mantenerla actualizada, como veremos.
• tamano: llevar la cuenta al insertar y borrar cuesta una suma o una resta (O(1)) y a cambio len(lista) será instantáneo, en lugar de recontar los nodos cada vez. Es el mismo espíritu del coste repartido que vimos con el amortizado: pagar un poquito en cada operación para no pagar mucho de golpe.

Nota sobre la palabra tamano: la escribimos sin eñe a propósito. Aunque Python admite identificadores con ñ, evitar caracteres no ASCII en nombres de código es una convención profesional extendida (y coherente con la higiene de nombres URL-safe que practica este campus).

Paso a paso, con el diagrama del recableado:

• Línea 1 (nuevo.siguiente = self.cabeza): el nodo recién creado agarra al que era el primero. Si la lista estaba vacía, self.cabeza es None y el nuevo queda correctamente como último (su siguiente es None).
• Línea 2 (self.cabeza = nuevo): la lista pasa a empezar por el nuevo. El orden de estas dos líneas es sagrado: si reasignáramos la cabeza primero, perderíamos la única referencia al resto de la lista.
• Línea 3: caso especial de la lista vacía — el nuevo nodo es a la vez primero y último.

Cuenta las operaciones: dos asignaciones, una comparación, una suma. Ninguna depende de cuántos elementos haya. O(1) de verdad, no amortizado: aquí no hay redimensionados ocasionales como en el append del array.

Sin la referencia cola, este método tendría que caminar desde la cabeza hasta el último nodo (O(n)) solo para engancharle el nuevo. Con ella, dos asignaciones y listo. Es un ejemplo perfecto de cómo una referencia extra bien mantenida cambia la clase de coste de una operación.

El recorrido es el gesto que ya conoces: actual = actual.siguiente hasta None. Lo ofreceremos de la forma más pythónica posible, como generador, para poder escribir for tarea in lista:

• yield convierte __iter__ en un generador: entrega un dato, se queda "congelado" y continúa cuando el for pide el siguiente. Para el usuario de la clase, la lista enlazada se recorre igual que una list.
• __str__ reutiliza el propio __iter__ (nada de duplicar el bucle) y tiene un detalle amable con TaskFlow: si el dato es una tarea-dict, muestra id:titulo en lugar del diccionario completo.
• La flecha -> None final no es decorativa: recuerda visualmente que el último nodo apunta a None.

Buscar por valor no tiene atajos: hay que mirar nodo a nodo. Implementamos una búsqueda por predicado, pensada para tareas ("dame la primera que cumpla esta condición"):

Uso: lista.buscar(lambda t: t["id"] == 42). Es el mismo O(n) que buscar en una list; la lección 01-02 ya nos enseñó que "mirar todo" no escala, y el módulo 5 traerá el índice por id que lo arregla. La lista enlazada no compite en este terreno.

Aquí aparece la letra pequeña que anunciamos en 02-01, y conviene mirarla de frente:

• Llegar al punto de inserción cuesta O(n): hay que caminar indice - 1 saltos.
• Recablear cuesta O(1): las dos asignaciones de siempre, en el orden de siempre.

¿Entonces dónde está la ventaja sobre el array, si ambos son O(n) al insertar en medio? En dos sitios. Primero, en los extremos: al principio la lista enlazada es O(1) donde el array es O(n) — esa diferencia la mediremos enseguida. Segundo, en el matiz "si ya estamos situados": cuando un algoritmo recorre la lista y decide insertar o borrar donde ya está (como harás al fusionar listas ordenadas en 02-05), el recableado O(1) se aprovecha de verdad, mientras que el array pagaría el desplazamiento igualmente. El array, en cambio, paga los desplazamientos de memoria siempre, esté donde esté.

Para borrar un nodo hay que recablear al que está antes que él... y en una lista enlazada simple los nodos no saben quién les precede (esa carencia la resolverá la lista doble en 02-03). La técnica estándar es avanzar con dos referencias en paralelo: anterior y actual.

Puntos delicados, uno a uno:

• Puentear: anterior.siguiente = actual.siguiente hace que la cadena "salte por encima" del nodo condenado. Nadie apunta ya a él, así que el recolector de basura de Python lo libera. No hay del ni liberación manual: soltar todas las referencias basta.
• Borrar el primero: si anterior sigue siendo None, el nodo a borrar es la cabeza; el puente consiste en mover self.cabeza.
• Borrar el último: si el condenado era la cola, hay que retrasar self.cola al anterior. Olvidar este caso deja una cola fantasma apuntando a un nodo fuera de la lista — un clásico.
• Usamos is (identidad) y no == para comparar con self.cola: queremos saber si es el mismo nodo, no uno parecido.

La tabla prometida en 02-01, ya demostrada método a método:

La última fila es el precio de la dispersión y no hay que esconderlo: si tu código vive de hacer tablero[i], la lista enlazada es una mala elección. Por eso no hemos implementado __getitem__: dar sintaxis de corchetes a una operación O(n) invita a usarla en bucles y fabricar O(n²) sin darse cuenta.

En 01-05 vimos que llenar una list con insert(0, x) era cuadrático. Repitamos aquel experimento con nuestra estructura en la contienda:

Resultado típico (los números exactos varían según la máquina; la forma no):

La lectura importa más que las cifras:

• Al duplicar n, la list se cuadruplica (cada insert(0) es O(n), el total O(n²)); la enlazada se duplica (cada inserción O(1), el total O(n)). Son las curvas de 01-04 en carne viva.
• Con n pequeño la diferencia es anecdótica; con n grande es abismal. La escalabilidad, como en el experimento de 01-02, es lo que separa una elección correcta de una que "funcionaba en mi portátil".
• Honestidad experimental: en operaciones donde la list es fuerte (recorrer, append, acceso por índice), ganaría ella, y a menudo con ventaja, porque el array contiguo aprovecha la caché y su código interno está escrito en C. Elegir estructura es elegir según la operación dominante, no según la ganadora del último benchmark.

Cerramos poniendo la pieza en su sitio. El tablero de TaskFlow, donde las urgencias entran por delante y las tareas se despachan por delante, encuentra por fin su estructura:

Fíjate en que el código cliente no menciona nodos ni referencias: habla de tareas, tal como manda la separación TDA-implementación de 01-01. Y un anticipo: este patrón de "entrar por un extremo y salir por un extremo" tiene nombres propios —pila y cola— y estructuras dedicadas que construiremos en los módulos 3 y 4, muchas veces montadas exactamente sobre lo que acabas de escribir.

• Recablear en el orden equivocado. Asignar self.cabeza = nuevo antes de nuevo.siguiente = self.cabeza deja al nuevo nodo apuntándose a sí mismo y pierde el resto de la lista. Regla mnemotécnica: primero el nuevo agarra, después lo agarran a él.
• Olvidar actualizar cola (o tamano). Cada método que toca la estructura debe dejar las tres referencias coherentes. Un borrar que no retrasa la cola cuando elimina el último nodo hará que el siguiente insertar_al_final enganche el nodo a un fantasma. Escribe un método _comprobar_invariantes() en depuración si te pasa a menudo.
• Los casos frontera: lista vacía y un solo elemento. Son la fuente del 80% de los fallos: borrar el único nodo debe dejar cabeza y cola a None; insertar en vacía debe fijar ambas. Prueba siempre tus métodos con listas de 0, 1 y 2 elementos antes que con 100.
• Iterar con índices por costumbre. for i in range(len(lista)): hacer_algo(lista_en(i)) sería O(n²) en una lista enlazada. Recorre siempre con for dato in lista (nuestro __iter__), que visita cada nodo una sola vez.
• Consejo: ante cualquier duda con un recableado, dibuja el antes y el después con cajas y flechas, numera las asignaciones y solo entonces escribe el código. Cinco minutos de papel ahorran una hora de depurador.

Ejercicio 1 — contar_si. Añade a ListaEnlazada un método contar_si(condicion) que devuelva cuántos datos cumplen la condición, y úsalo para contar cuántas tareas del tablero tienen prioridad == 1. ¿Cuál es su coste Big O y por qué no puede ser mejor?

Ejercicio 2 — insertar_ordenado por prioridad. Añade un método insertar_ordenado(tarea) que inserte la tarea manteniendo el tablero ordenado por prioridad ascendente (prioridad 1 delante). Pista: es una variante de insertar_en, pero en lugar de contar saltos, caminas hasta encontrar el primer nodo con prioridad mayor. Cuida los tres casos: insertar delante, en medio y al final. Indica el Big O.

Ejercicio 3 — El precio del índice. Implementa una función externa elemento_en(lista, i) que devuelva el dato en la posición i de una ListaEnlazada (o None si no existe). Después escribe imprimir_mal(lista) que imprima todos los elementos usando elemento_en en un bucle sobre range(len(lista)), e imprimir_bien(lista) usando for dato in lista. Mide ambas con timeit para n = 2.000 y 4.000 elementos y explica el resultado con Big O.

Solución 1:

Es O(n) y no puede ser mejor: para contar cuántos cumplen algo hay que examinarlos todos; ningún recableado ni referencia extra evita mirar cada dato al menos una vez.

Solución 2:

Comentarios: la condición del while mira anterior.siguiente (no anterior) porque necesitamos detenernos en el nodo previo al punto de inserción — el patrón del nodo anterior otra vez. El caso "va al final" se resuelve solo: el while termina con anterior.siguiente a None y el recableado engancha al final (sin olvidar la cola). Coste O(n): en el peor caso se camina toda la lista. Este método reaparecerá en el módulo 4 cuando hablemos de colas de prioridad.

Solución 3:

Resultado típico: al duplicar n, imprimir_bien se duplica (O(n): un recorrido) pero imprimir_mal se cuadruplica (O(n²): la llamada i-ésima camina i saltos, total 0+1+...+(n−1) ≈ n²/2). Es exactamente la misma suma que condenaba a insert(0) en el array, ahora del lado de la lista enlazada: cada estructura tiene su propia forma de fabricar O(n²) si se usa contra su naturaleza.

Ya tienes tu primera estructura construida desde cero y completa: ListaEnlazada, con inserciones O(1) en ambos extremos (cabeza recableada, cola mantenida), borrado con el patrón del nodo anterior, búsqueda por predicado, recorrido como generador y len/print de ciudadano de primera. El análisis Big O quedó demostrado y timeit confirmó la revancha: donde insert(0) condenaba a la list a lo cuadrático, nuestra estructura escala linealmente — a cambio de haber renunciado al acceso por índice O(1), como delató el último ejercicio. El tablero de TaskFlow ya vive sobre ella. Pero le queda una carencia estructural: cada nodo conoce al siguiente e ignora por completo al anterior, lo que nos obligó al baile de dos referencias para borrar y nos impide recorrer hacia atrás. En la próxima lección añadiremos la flecha que falta —anterior— y obtendremos la lista doblemente enlazada: borrados O(1) teniendo el nodo, recorridos en ambos sentidos, y para TaskFlow un historial de tareas navegable hacia delante y hacia atrás.