Una vez dominamos los nodos y referencias, el siguiente paso es diferenciar las variantes de listas. Existen tres familias clásicas: simplemente enlazadas, doblemente enlazadas y circulares. Cada una balancea memoria, complejidad y velocidad según el patrón de acceso que queremos resolver.
La lista simplemente enlazada conecta cada nodo con su sucesor mediante una sola referencia sig. Es ideal para pilas, colas sencillas o estructuras donde el recorrido siempre va hacia adelante.
class NodoSimple:
def __init__(self, valor):
self.valor = valor
self.sig = None
class ListaSimple:
def __init__(self):
self.cabeza = None
def insertar_inicio(self, valor):
nuevo = NodoSimple(valor)
nuevo.sig = self.cabeza
self.cabeza = nuevo
def imprimir(self):
reco = self.cabeza
while reco:
print(reco.valor, end=" -> ")
reco = reco.sig
print("None")
El método inserta al inicio en O(1). El costo de recorrer es lineal y no hay forma de retroceder sin usar estructuras auxiliares. Es la variante más económica en memoria porque solo guarda una referencia por nodo.
La lista doblemente enlazada agrega una referencia ant para navegar hacia atrás. Esto permite eliminaciones y recorridos bidireccionales más eficientes, a costa de mayor uso de memoria.
class NodoDoble:
def __init__(self, valor):
self.valor = valor
self.ant = None
self.sig = None
class ListaDoble:
def __init__(self):
self.cabeza = None
self.cola = None
def insertar_final(self, valor):
nuevo = NodoDoble(valor)
if self.cola is None:
self.cabeza = self.cola = nuevo
return
nuevo.ant = self.cola
self.cola.sig = nuevo
self.cola = nuevo
Al mantener referencias a cabeza y cola, las inserciones en ambos extremos se vuelven O(1). El riesgo principal es olvidar actualizar ant y sig simultáneamente, lo que corrompe la lista.
En la lista circular, el último nodo enlaza de vuelta al primero. Esta propiedad se aplica tanto a variantes simples como dobles y resulta útil para algoritmos que requieren recorrer indefinidamente, como planificadores round-robin.
class NodoCircular:
def __init__(self, valor):
self.valor = valor
self.sig = None
class ListaCircular:
def __init__(self):
self.cola = None # cola.sig apunta al primer nodo
def insertar(self, valor):
nuevo = NodoCircular(valor)
if self.cola is None:
nuevo.sig = nuevo
self.cola = nuevo
return
nuevo.sig = self.cola.sig
self.cola.sig = nuevo
self.cola = nuevo
def recorrer(self):
if self.cola is None:
return
inicio = self.cola.sig
reco = inicio
while True:
print(reco.valor, end=" ")
reco = reco.sig
if reco is inicio:
break
print()
El recorrido usa un ciclo controlado manualmente para garantizar que se visite cada nodo una sola vez sin caer en bucles infinitos. Las listas circulares simplifican la implementación de buffers que necesitan reutilizar posiciones sin detener el flujo.
| Característica | Simple | Doble | Circular |
|---|---|---|---|
| Referencias por nodo | 1 (sig) | 2 (ant, sig) | 1 o 2 según variante |
| Inserción en cola | O(n) sin referencia adicional | O(1) con acceso a cola | O(1) manteniendo referencia a cola |
| Recorrido hacia atrás | No | Sí | Solo si es doble |
| Uso típico | Pilas, colas sencillas | Listas de reproducción, editores | Planificadores, buffers circulares |