6 - Colas con listas enlazadas

6.1 Cuándo elegir una lista enlazada

Las colas basadas en listas enlazadas mantienen el modelo FIFO sin depender de un tamaño fijo de arreglo. Crecen y se encogen en función del número real de elementos, lo que evita reservar memoria ociosa.

• Capacidad elástica: ideal cuando la tasa de llegadas es impredecible o el pico supera a una cola estática.
• Inserciones O(1): solo se modifica el puntero final, sin necesidad de desplazar datos.
• Consumo proporcional: cada nodo existe mientras contenga un dato, lo que facilita liberar memoria tempranamente.

Su costo principal es la gestión de referencias y la necesidad de controlar los invariantes al insertar o quitar nodos, por lo que conviene encapsular las operaciones en métodos pequeños y consistentes.

6.2 Nodo y estructura base

Un nodo almacena el valor y un enlace al siguiente. La cola mantiene punteros a frente y final para operar en tiempo constante:

class Nodo:
  def __init__(self, dato):
    self.dato = dato
    self.siguiente = None


class ColaLista:
  def __init__(self):
    self.frente = None
    self.final = None
    self.cantidad = 0

Al iniciar, ambos punteros deben apuntar a None para indicar que la cola está vacía.

6.3 Operación enqueue paso a paso

El encolado crea un nodo nuevo, copia el dato y ajusta el puntero final. En Python no hay que reservar memoria manualmente, pero conviene validar los invariantes.

class ColaLista:
  ...

  def encolar(self, valor):
    nuevo = Nodo(valor)
    if self.cantidad == 0:
      self.frente = nuevo
    else:
      self.final.siguiente = nuevo
    self.final = nuevo
    self.cantidad += 1

Cuando la cola estaba vacía, frente y final pasan a apuntar al mismo nodo.

6.4 Desencolado seguro y liberación

El desencolado recupera el valor del primer nodo y avanza el puntero. Si el último elemento sale de la cola, ambos punteros vuelven a None.

class ColaLista:
  ...

  def desencolar(self):
    if self.cantidad == 0:
      raise IndexError("Cola vacia")
    nodo = self.frente
    self.frente = nodo.siguiente
    if not self.frente:
      self.final = None
    self.cantidad -= 1
    return nodo.dato

Si la cola está vacía se lanza una excepción; también podría retornarse None dependiendo del contrato.

6.5 Estrategias de gestión de memoria

• Chequeo de asignaciones: aunque Python gestiona la memoria, al crear muchos nodos conviene manejar excepciones y validar condiciones de negocio.
• Función de vaciado: una rutina que desencole todos los nodos facilita liberar referencias y forzar el GC.
• Contadores diagnósticos: registrar cantidad y operaciones fallidas ayuda a auditar el uso de la estructura.

Si los nodos almacenan objetos complejos, documenta quién es dueño de liberar recursos externos.

6.6 Variantes y extensiones

• Nodo centinela: mantener un nodo vacío permanentemente reduce las comprobaciones de casos borde.
• Listas doblemente enlazadas: permiten convertir la cola en un deque sin reescribir la estructura principal.
• Colas genéricas: usar objetos Python o genéricos con typing.Generic permite compartir el mismo código para distintos tipos sin código duplicado.

Documenta las convenciones sobre propiedad y ciclo de vida de los objetos que viajan en la cola para evitar referencias colgantes o liberaciones duplicadas.

6.7 Ejemplo completo en Python

El siguiente programa simula solicitudes que llegan a la cola, imprime su estado y realiza limpiezas antes de salir.

class Nodo:
  def __init__(self, dato):
    self.dato = dato
    self.siguiente = None


class ColaLista:
  def __init__(self):
    self.frente = None
    self.final = None
    self.cantidad = 0

  def encolar(self, valor):
    nuevo = Nodo(valor)
    if not self.frente:
      self.frente = nuevo
    else:
      self.final.siguiente = nuevo
    self.final = nuevo
    self.cantidad += 1

  def desencolar(self):
    if not self.frente:
      return None
    nodo = self.frente
    self.frente = nodo.siguiente
    if not self.frente:
      self.final = None
    self.cantidad -= 1
    return nodo.dato

  def imprimir(self):
    elementos = []
    actual = self.frente
    while actual:
      elementos.append(str(actual.dato))
      actual = actual.siguiente
    print(f"[cola] cantidad={self.cantidad} -> {' '.join(elementos)}")

  def vaciar(self):
    while self.desencolar() is not None:
      pass


if __name__ == "__main__":
  cola = ColaLista()

  for i in range(1, 4):
    cola.encolar(i * 10)
  cola.imprimir()

  valor = cola.desencolar()
  print("desencolado:", valor)
  cola.imprimir()

  cola.encolar(99)
  cola.encolar(100)
  cola.imprimir()

  while cola.cantidad:
    valor = cola.desencolar()
    print("procesado:", valor)
  cola.imprimir()

  cola.vaciar()

Prueba el ejemplo con distintas secuencias para verificar que los punteros regresen a None cuando la cola se vacía y que no se pierdan nodos.