Las listas enlazadas son una familia de estructuras lineales descritas en la literatura desde los orígenes de la programación. Cada elemento se aloja en un nodo que conoce a su sucesor y, dependiendo de la variante, a su predecesor. A diferencia de los arreglos, no hay un bloque contiguo que reserve toda la memoria, sino que los nodos se crean bajo demanda.
Gracias a esta flexibilidad se vuelven una opción natural cuando el volumen de datos es incierto, cuando la aplicación requiere insertar o borrar elementos en posiciones arbitrarias o cuando se busca reutilizar nodos para ahorrar copias. En Python siguen vigentes para representar colas, historiales o estructuras internas donde las listas nativas (arrays dinámicos) no son ideales.
El concepto formal está documentado en la entrada de listas enlazadas de Wikipedia, que resume las variantes históricas y sus principales aplicaciones. En este tutorial enfocamos el análisis en la implementación en Python, de modo que comprendamos cómo modelar nodos con clases, qué hace el recolector de basura y cómo escribir código idiomático.
Una lista enlazada es una colección de nodos enlazados por referencias. Cada nodo guarda el dato de interés (entero, cadena, objeto propio) y al menos una referencia que indica dónde continuar. El primer nodo se conoce como head y delimita la entrada oficial a la estructura; cuando la lista está vacía, el head es None. El último nodo se denomina tail y su referencia también es None salvo en diseños circulares donde se vuelve a enlazar con el head.
Al recorrer una lista pensamos en una cadena de nodos: iniciar en head, inspeccionar su valor y seguir el enlace al siguiente nodo. Si alguno de los enlaces queda mal actualizado, se pierde parte de la estructura. Por ello las inserciones y eliminaciones siempre deben preservar la secuencia head → ... → tail.
En Python podemos representar un nodo de la siguiente forma:
class Nodo:
def __init__(self, valor):
self.valor = valor
self.sig = None # referencia al siguiente nodo
Este esquema admite cualquier tipo de dato en valor; basta con pasar cualquier objeto al constructor. El objetivo es separar la lógica de enlace de los datos reales. El recolector de basura de Python libera los nodos cuando dejan de estar referenciados, por lo que no necesitamos llamar a free, pero sí evitar referencias cruzadas que impidan la recolección.
Comparar listas enlazadas con las listas nativas de Python (arrays dinámicos) ayuda a decidir cuándo utilizar cada estructura. En la tabla siguiente se contrastan los aspectos más relevantes:
| Criterio | Lista nativa de Python | Lista enlazada |
|---|---|---|
| Ubicación en memoria | Bloque contiguo gestionado por CPython; favorece la cercanía a nivel de caché | Nodos dispersos; puede aprovechar huecos libres en el heap |
| Coste de inserción intermedia | O(n) por desplazamiento de elementos internos | O(1) si se tiene la referencia al nodo anterior |
| Acceso por posición | O(1), basta con calcular la dirección base + desplazamiento | O(n); es necesario recorrer desde head |
| Consumo extra | Sin punteros adicionales por elemento, aunque cada objeto tiene sobrecarga de Python | Cada nodo incluye al menos una referencia adicional |
| Redimensión | Realiza copias amortizadas cuando crece el array interno | Cada inserción crea un nodo independiente |
El resultado principal es que un array es insuperable para lectura secuencial y acceso directo, pero se vuelve costoso cuando el tamaño cambia muchas veces por segundo. Las listas enlazadas sacrifican velocidad de acceso para ganar flexibilidad estructural y reducir copias.
Entre los beneficios más importantes destacan:
Estas ventajas cobran sentido en colas de tareas, historiales de comandos o estructuras internas que requieren eliminar nodos frecuentemente sin copiar listas completas.
No hay estructura perfecta; las listas enlazadas introducen retos que deben evaluarse antes de adoptarlas:
sig puede dejar la lista corrupta. Aunque el recolector de basura limpia los nodos sin referencias, los ciclos pueden retrasar la liberación.Por estas razones se suelen combinar con otras estructuras: por ejemplo, una lista enlazada que almacena arreglos pequeños para equilibrar flexibilidad y rendimiento.
Las listas enlazadas tienen presencia en componentes críticos de software:
Estos casos demuestran que, aunque existan estructuras más sofisticadas, la lista enlazada sigue siendo una herramienta indispensable cuando la mutabilidad y el control de memoria son prioritarios.