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:

 

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.