Al cerrar el módulo anterior dejamos una promesa en el aire: existe "otra apuesta" distinta a la del array, una estructura que renuncia a la contigüidad en memoria precisamente para hacer baratas las inserciones y borrados donde el array flaquea. Esa apuesta es la lista enlazada, y este módulo entero está dedicado a ella y a sus variantes. Pero antes de escribir una sola clase necesitamos dar un paso atrás y hacer lo mismo que hicimos con la pila en la lección 01-01: separar el qué (el TDA lista, un contrato de operaciones) del cómo (array contiguo o nodos dispersos). En esta lección definimos ese contrato, entendemos la pieza fundamental de la nueva apuesta —el nodo con su referencia siguiente— y ponemos frente a frente los costes de ambas implementaciones, para decidir con criterio cuál conviene en cada rincón de TaskFlow.

1. El TDA lista: un contrato, dos implementaciones
2. La apuesta del array: contigüidad (repaso estratégico)
3. La otra apuesta: nodos dispersos y referencias
4. Anatomía de un nodo en Python
5. Tabla comparativa de costes: array dinámico vs lista enlazada
6. ¿Cuál conviene en TaskFlow?

En la lección 01-01 vimos que un Tipo de Dato Abstracto (TDA) define qué operaciones ofrece una estructura sin comprometerse con cómo se implementan por dentro: nuestras clases PilaConLista y PilaConDiccionario cumplían el mismo contrato con interiores completamente distintos. Con las listas ocurre exactamente lo mismo.

El TDA lista es una secuencia ordenada de elementos donde cada elemento ocupa una posición, y que ofrece como mínimo estas operaciones:

• Insertar un elemento (al principio, al final o en una posición intermedia).
• Borrar un elemento (por posición o por valor).
• Buscar un elemento (¿está? ¿en qué posición?).
• Recorrer la secuencia de principio a fin, visitando cada elemento en orden.
• Consultar el elemento de una posición dada y conocer la longitud de la secuencia.

Fíjate en que el contrato no dice ni una palabra sobre memoria, casillas o referencias. Y eso es deliberado, porque hay (al menos) dos formas radicalmente distintas de cumplirlo:

Una advertencia terminológica importante: en Python, la palabra list nombra a la implementación A. Es un nombre algo desafortunado, porque en la literatura de estructuras de datos "lista" suele referirse al TDA, y "lista enlazada" (linked list) a la implementación B. En este curso diremos list de Python o array dinámico para la A, y lista enlazada para la B.

No vamos a repetir la lección 01-05, pero sí a condensarla en lo que nos importa para la comparación. El array apuesta todo a la contigüidad:

• Gana: acceso por índice O(1) gracias a la fórmula base + i × tamaño; recorridos muy rápidos (la memoria contigua es amiga de la caché del procesador); append O(1) amortizado.
• Pierde: insertar o borrar en el principio o en el medio obliga a desplazar todos los elementos posteriores, un coste O(n) que medimos con timeit y que se volvía cuadrático al repetirlo en bucle (la trampa de insert(0) que vimos al cerrar el módulo 1).

La pregunta que queda flotando es: ¿y si pudiéramos insertar un elemento en medio de la secuencia sin tocar a los demás? Para lograrlo hay que abandonar la idea de que la posición en memoria codifica la posición en la secuencia.

La lista enlazada invierte la apuesta. En lugar de exigir que los elementos vivan en casillas consecutivas, permite que cada uno viva donde quiera en la memoria. Pero entonces surge un problema: si los elementos están dispersos, ¿cómo sabemos cuál va después de cuál? La fórmula del array ya no sirve, porque no hay contigüidad que explotar.

La solución es que cada elemento lleve consigo la dirección del siguiente. A ese paquete —el dato más la referencia al siguiente— lo llamamos nodo:

Tres observaciones clave sobre este diagrama:

• La lista solo necesita "agarrar" el primer nodo (lo llamaremos la cabeza, en inglés head). A partir de él, las flechas permiten llegar a todos los demás.
• El último nodo apunta a None: es la señal de "aquí se acaba la secuencia".
• Las flechas son la secuencia. Si en memoria el nodo de la tarea 3 estuviera físicamente antes que el de la tarea 1, daría exactamente igual: el orden lógico lo definen las referencias, no las direcciones.

Y aquí está la jugada maestra. Para insertar una tarea nueva entre la 1 y la 2, no hay que desplazar nada: basta con recablear dos flechas.

Da igual que la lista tenga 3 elementos o 3 millones: el recableado en sí son dos asignaciones, coste O(1). Esa es la esencia de la promesa "inserciones y borrados baratos". (Ojo: llegar hasta el punto de inserción puede tener su propio coste; lo analizaremos con rigor en la próxima lección. No queremos venderte la moto sin la letra pequeña.)

En Python no manejamos direcciones de memoria a mano: manejamos referencias, que es exactamente lo que ocurre cada vez que asignas un objeto a una variable. Un nodo es simplemente un objeto con dos atributos:

Explicación detallada para quien ve esto por primera vez:

• self.dato guarda el elemento en sí. Como Python trabaja con referencias, aquí puede vivir cualquier cosa: un número, una cadena o —en nuestro caso— la tarea-como-dict que fijamos en el módulo 1.
• self.siguiente guarda otra referencia, esta vez a otro objeto Nodo (o None si es el último). No hay magia: es la misma mecánica de asignación que usas a diario, puesta al servicio de encadenar objetos.

Podemos encadenar tres tareas de TaskFlow a mano, sin ninguna clase contenedora todavía:

Salida:

El bucle while de arriba es el gesto más importante de todo el módulo: avanzar por una lista enlazada es reasignar actual = actual.siguiente hasta toparse con None. Todo lo que construyamos en las próximas lecciones —insertar, borrar, buscar— son variaciones de este gesto.

Encadenar nodos a mano es instructivo pero impracticable. En 02-02 encapsularemos toda esta mecánica en una clase ListaEnlazada con las operaciones del TDA; hoy nos basta con entender la pieza.

Esta tabla es el mapa del módulo. La columna del array la demostramos en 01-05; la columna de la lista enlazada es, por ahora, un adelanto que la lección 02-02 demostrará operación por operación (y verificará con timeit, como mandan nuestras costumbres):

* El "truco" consiste en que la lista guarde también una referencia al último nodo (la cola); lo veremos en 02-02.

Lecturas importantes de la tabla:

• No hay ganador absoluto. Cada estructura gana justo donde la otra pierde: es un intercambio (trade-off), el pan de cada día en estructuras de datos.
• La lista enlazada pierde el superpoder del array: ya no existe fórmula que lleve al elemento i de un salto. Pedir "el elemento 500.000" significa dar 500.000 saltos.
• Buscar por valor es O(n) en ambas: ninguna de las dos resuelve el problema de "encontrar la tarea con id 42" que planteamos en 01-02. Para eso seguirá haciendo falta el índice por id que llegará en el módulo 5.
• La lista enlazada paga un sobrecoste de memoria: cada dato carga con una flecha extra. La dispersión no sale gratis.

Bajemos la tabla a tierra con los escenarios reales de nuestra aplicación:

La conclusión para TaskFlow es matizada, como casi todo en ingeniería: mientras el tablero solo crecía por el final y se leía en orden, la list de Python era imbatible. Pero el tablero real de un equipo no funciona así: las urgencias entran por delante, las tareas se despachan por delante y se reordenan por el medio constantemente. Ese patrón de uso —muchas inserciones y borrados en posiciones incómodas— es exactamente el terreno donde la lista enlazada brilla, y por eso la elegimos como base del tablero definitivo.

• Confundir la list de Python con una lista enlazada. Es el error terminológico número uno. La list de Python es un array dinámico (lección 01-05); si en una entrevista te piden "implementa una lista enlazada", responder lista = [] es responder a otra pregunta.
• Creer que la lista enlazada es "mejor" que el array. No lo es; es mejor para ciertas operaciones y peor para otras. Quien memoriza "lista enlazada = rápida" sin la tabla de costes acaba eligiendo mal. Guarda la tabla de esta lección junto a la de costes de list/dict/set de 01-04.
• Olvidar que siguiente puede ser None. Escribir actual.siguiente.dato sin comprobar antes que actual.siguiente no es None provoca el clásico AttributeError: 'NoneType' object has no attribute 'dato'. Acostúmbrate desde ya a preguntarte en cada línea: "¿y si aquí ya no hay nodo?".
• Perder la cabeza de la lista. Si reasignas la variable que apunta al primer nodo (cabeza = cabeza.siguiente sin querer), el nodo anterior se vuelve inalcanzable y el recolector de basura de Python lo elimina. La cabeza es el único hilo del que pende toda la estructura: trátala con respeto.
• Consejo: cuando dudes de un recableado de referencias, dibuja los nodos y las flechas en papel antes de escribir código. Es la técnica que usan hasta los ingenieros veteranos, y en las lecciones siguientes la practicaremos con diagramas mermaid a cada paso.

Ejercicio 1 — El contrato y sus implementaciones. Sin mirar la tabla, clasifica estas cuatro frases como propias del TDA lista, del array dinámico o de la lista enlazada: (a) "insertar un elemento en la posición i"; (b) "los elementos ocupan casillas contiguas de memoria"; (c) "cada elemento guarda una referencia al siguiente"; (d) "recorrer los elementos en orden". Justifica cada respuesta en una línea.

Ejercicio 2 — Encadenar y recorrer a mano. Usando solo la clase Nodo de esta lección (sin ninguna clase contenedora), construye una cadena con estas cuatro tareas de TaskFlow: "Revisar diseño" (id 10), "Corregir bug login" (id 11), "Desplegar versión" (id 12) y "Cerrar sprint" (id 13), todas con prioridad 2 y estado "pendiente". Después escribe: (a) un bucle que imprima id - titulo de cada tarea; (b) un bucle que cuente cuántos nodos hay, sin usar len de ninguna estructura auxiliar.

Ejercicio 3 — Recablear sin desplazar. Partiendo de la cadena del ejercicio 2, inserta la tarea "Hotfix producción" (id 14, prioridad 1) entre "Corregir bug login" y "Desplegar versión", sin crear ninguna cadena nueva: solo creando un nodo y reasignando las referencias necesarias. ¿Cuántas asignaciones de siguiente has necesitado? ¿Dependería ese número de que la cadena tuviera un millón de nodos?

Solución 1:

• (a) TDA lista: describe una operación del contrato, sin decir cómo se logra por dentro.
• (b) Array dinámico: la contigüidad es la decisión de implementación que da el acceso O(1) por fórmula.
• (c) Lista enlazada: la referencia al siguiente es la decisión de implementación que permite la dispersión.
• (d) TDA lista: recorrer es parte del contrato; ambas implementaciones lo ofrecen (con interiores distintos).

Solución 2:

Observa que ambos apartados usan el mismo patrón de recorrido; solo cambia lo que hacemos al visitar cada nodo. Ese patrón es el corazón de la clase que construiremos en 02-02. Y sí: las cadenas cabeza.siguiente.siguiente.siguiente = ... son horribles — exactamente por eso necesitamos encapsular esto en una clase.

Solución 3:

Han bastado 2 asignaciones de siguiente, y ese número sería idéntico con un millón de nodos: el recableado en sí es O(1). Fíjate en el orden de las dos líneas: si hiciéramos primero nodo_bug.siguiente = nuevo, perderíamos la referencia a "Desplegar versión" y el resto de la cadena quedaría descolgado. Este detalle —el orden del recableado— será protagonista en la próxima lección.

Hemos separado el contrato de sus cumplidores: el TDA lista es una secuencia ordenada con operaciones de insertar, borrar, buscar y recorrer, y tanto el array dinámico como la lista enlazada lo implementan con apuestas opuestas — contigüidad con acceso O(1) por fórmula frente a nodos dispersos unidos por referencias siguiente, donde insertar es recablear dos flechas en vez de desplazar media memoria. La tabla de costes nos dejó claro que no hay ganador absoluto, y el patrón de uso del tablero de TaskFlow (urgencias por delante, reordenaciones por el medio) inclinó la balanza hacia la lista enlazada. Pero hasta ahora solo hemos encadenado nodos a mano, con ese incómodo cabeza.siguiente.siguiente. En la próxima lección haremos las cosas bien: construiremos la clase ListaEnlazada completa —insertar, borrar, buscar, recorrer, __len__, __str__—, analizaremos el Big O de cada operación, y pondremos a la criatura frente a timeit para comprobar que la promesa de las inserciones baratas se cumple donde el array caía: insertando por delante.