8 - Aplicaciones y casos de uso
Puentes hacia proyectos reales
Las listas enlazadas son más que un ejercicio académico: se usan para pilas, colas, buffers, planificadores y algoritmos clásicos. Este tema repasa cinco aplicaciones comunes con ejemplos en Python.
8.1 Pilas implementadas con listas
Una pila (stack) agrega y retira elementos por el mismo extremo. Con una lista enlazada obtenemos crecimiento dinámico sin capacidad fija.
class Nodo:
def __init__(self, valor):
self.valor = valor
self.sig = None
class Pila:
def __init__(self):
self.tope = None
def push(self, valor):
nuevo = Nodo(valor)
nuevo.sig = self.tope
self.tope = nuevo
def pop(self):
if self.tope is None:
return None
victima = self.tope
self.tope = victima.sig
victima.sig = None
return victima.valor
push inserta al inicio en O(1) y pop reutiliza la eliminación del primer nodo.
8.2 Colas implementadas con listas
Las colas encolan por el final y desencolan por el inicio. Mantener referencias a cabeza y cola da inserciones O(1).
class Cola:
def __init__(self):
self.cabeza = None
self.cola = None
def enqueue(self, valor):
nuevo = Nodo(valor)
if self.cabeza is None:
self.cabeza = self.cola = nuevo
return
self.cola.sig = nuevo
self.cola = nuevo
def dequeue(self):
if self.cabeza is None:
return None
victima = self.cabeza
self.cabeza = victima.sig
if self.cabeza is None:
self.cola = None
victima.sig = None
return victima.valor
8.3 Buffers circulares
Los buffers circulares procesan flujos continuos (audio, mensajes). Una lista circular evita realocar memoria constantemente.
class NodoCircular:
def __init__(self, valor):
self.valor = valor
self.sig = None
class BufferCircular:
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
Se puede fijar un tamaño máximo y, al llenarse, eliminar el nodo más antiguo (el que sigue a cola).
8.4 Listas en sistemas operativos
Los kernels mantienen colas de procesos/hilos con listas enlazadas. Ejemplo simplificado de cola de procesos listos:
class Proceso:
def __init__(self, pid):
self.pid = pid
self.sig = None
class ColaProcesos:
def __init__(self):
self.cabeza = None
self.cola = None
def agregar(self, pid):
proc = Proceso(pid)
if self.cabeza is None:
self.cabeza = self.cola = proc
return
self.cola.sig = proc
self.cola = proc
El planificador mueve procesos entre colas (listos, bloqueados) actualizando solo las referencias de cabeza y cola.
8.5 Algoritmos como Josephus o round-robin
Problemas como Josephus o round-robin se benefician de listas circulares: el puntero puede girar sin llegar a None.
def josephus(lista_circular, salto):
if lista_circular.cola is None:
return None
actual = lista_circular.cola.sig
anterior = lista_circular.cola
while actual != anterior:
for _ in range(salto - 1):
anterior = actual
actual = actual.sig
anterior.sig = actual.sig
if actual == lista_circular.cola:
lista_circular.cola = anterior
actual = anterior.sig
sobreviviente = actual.valor
lista_circular.cola = None
return sobreviviente
Josephus elimina nodos hasta dejar un sobreviviente. Round-robin aplica la misma idea pero reencola en lugar de eliminar.
8.6 Código base reutilizable
Proyecto compacto para probar las aplicaciones en un solo archivo:
# aplicaciones_listas.py
class Nodo:
def __init__(self, valor):
self.valor = valor
self.sig = None
class Pila:
def __init__(self):
self.tope = None
def push(self, valor):
nuevo = Nodo(valor)
nuevo.sig = self.tope
self.tope = nuevo
def pop(self):
if self.tope is None:
return None
victima = self.tope
self.tope = victima.sig
victima.sig = None
return victima.valor
class Cola:
def __init__(self):
self.cabeza = None
self.cola = None
def enqueue(self, valor):
nuevo = Nodo(valor)
if self.cabeza is None:
self.cabeza = self.cola = nuevo
return
self.cola.sig = nuevo
self.cola = nuevo
def dequeue(self):
if self.cabeza is None:
return None
victima = self.cabeza
self.cabeza = victima.sig
if self.cabeza is None:
self.cola = None
victima.sig = None
return victima.valor
class NodoCircular:
def __init__(self, valor):
self.valor = valor
self.sig = None
class BufferCircular:
def __init__(self):
self.cola = None
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 imprimir(self):
if self.cola is None:
print("(buffer vacio)")
return
inicio = self.cola.sig
reco = inicio
while True:
print(reco.valor, end=" -> ")
reco = reco.sig
if reco == inicio:
break
print("(inicio)")
def main():
pila = Pila()
cola = Cola()
buffer = BufferCircular()
pila.push(1)
pila.push(2)
cola.enqueue(10)
cola.enqueue(20)
for v in (100, 200, 300):
buffer.insertar(v)
print("Pila pop:", pila.pop(), pila.pop())
print("Cola dequeue:", cola.dequeue(), cola.dequeue())
print("Buffer circular:")
buffer.imprimir()
if __name__ == "__main__":
main()
Ejecuta este script y agrega variantes (prioridad, round-robin, buffers con tamaño máximo) para afianzar el uso de listas enlazadas.