19.4. Cola Enlazada Mejorada

Nos gustaría una implementación del TAD Cola capaz de realizar todas las
operaciones en tiempo constante. Una forma de hacerlo es modificar la clase
Cola de modo que mantenga una referencia tanto al primero como al ultimo
nodo, como se muestra en la figura:

Sin título

 

La implementación de ColaMejorada es así:

   1: class ColaMejorada:
   2:     def __init__(self):
   3:         self.longitud = 0
   4:         self.cabeza = None
   5:         self.ultimo = None
   6:     def estaVacia(self):
   7:         return (self.longitud == 0)

 

Hasta ahora, el único cambio es el atributo ultimo. Se usa en los métodos
inserta y quita:



   1: class ColaMejorada:
   2: ...
   3: def inserta(self, carga):
   4:     nodo = Nodo(carga)
   5:     nodo.siguiente = None
   6:     if self.longitud == 0:
   7:         # si la lista esta vac³a, el nuevo nodo es cabeza y ultimo
   8:         self.cabeza = self.ultimo = nodo
   9:     else:
  10:         # encontrar el ultimo nodo
  11:         ultimo = self.ultimo
  12:         # añaadir el nuevo nodo
  13:         ultimo.siguiente = nodo
  14:         self.ultimo = nodo
  15:     self.longitud = self.longitud + 1

 


Como ultimo sigue el rastro del ultimo nodo, no necesitamos buscarlo. A causa
de esto, este metodo funciona en tiempo constante.


Debemos pagar un precio por esa velocidad. Tenemos que añadir un caso especial
a quita para apuntar ultimo a None cuando quitamos el ultimo nodo:




   1: class ColaMejorada:
   2: ...
   3:     def quita(self):
   4:         carga = self.cabeza.carga
   5:         self.cabeza = self.cabeza.siguiente
   6:         self.longitud = self.longitud - 1
   7:         if self.longitud == 0:
   8:         self.ultimo = None
   9:     return carga

 


Esta implementación es mas complicada que la de la Lista Enlazada, y es mas
difícil demostrar que es correcta. La ventaja es que hemos alcanzado la meta:
tanto inserta como quita son operaciones de tiempo constante.


 


 


Como ejercicio, escriba una implementación del TAD Cola usando
una lista de Python. Compare el rendimiento de esta implementación
con la de la ColaMejorada para varias longitudes de cola.

0