3.23. Implementación de una lista ordenada¶
Para implementar la lista ordenada, debemos recordar que las posiciones relativas de los ítems se basan en alguna característica subyacente. La lista ordenada de números enteros dada anteriormente (17, 26, 31, 54, 77 y 93) puede ser representada por una estructura enlazada como se muestra en la Figura 15. De nuevo, la estructura de nodo y enlace es ideal para representar el posicionamiento relativo de los ítems.
Para implementar la clase ListaOrdenada, usaremos la misma técnica que se vio anteriormente con las listas no ordenadas. Una vez más, una lista vacía será denotada por una referencia cabeza a None (ver el Programa 8).
Programa 8
class ListaOrdenada:
def __init__(self):
self.cabeza = None
A medida que consideramos las operaciones de la lista ordenada, debemos tener en cuenta que los métodos estaVacia y tamano se pueden implementar de la misma manera que con las listas no ordenadas ya que sólo tratan con el número de nodos de la lista sin considerar los valores reales del ítem. Del mismo modo, el método remover funcionará bien, ya que todavía necesitamos encontrar el ítem y luego enlazar alrededor del nodo para eliminarlo. Los dos métodos restantes, buscar y agregar, requerirán alguna modificación.
La búsqueda en una lista enlazada no ordenada requería que recorriéramos los nodos de uno en uno hasta encontrar el ítem que buscábamos o quedarnos sin nodos (None). Resulta que el mismo enfoque realmente funciona con la lista ordenada y de hecho, en el caso en que encontramos el ítem, es exactamente lo que necesitamos. Sin embargo, en el caso en que el ítem no esté en la lista, podemos aprovechar el ordenamiento para detener la búsqueda tan pronto como sea posible.
Por ejemplo, la Figura 16 muestra la lista enlazada ordenada a medida que se busca el valor 45. A medida que avanzamos, comenzando en la cabeza de la lista, primero comparamos contra 17. Dado que 17 no es el ítem que estamos buscando, nos movemos al siguiente nodo, en este caso 26. De nuevo, éste valor no es el que queremos, así que pasamos a 31 y luego a 54. Ahora, en este punto, algo es diferente. Puesto que 54 no es el ítem que buscamos, nuestra estrategia anterior sería seguir adelante. Sin embargo, debido al hecho de que se trata de una lista ordenada, continuar ya no será necesario. Una vez que el valor en el nodo sea mayor que el ítem que estamos buscando, la búsqueda puede detenerse y devolver False. No hay manera de que el ítem pueda existir más adelante en la lista enlazada.
Figura 16: Búsqueda en una lista enlazada ordenada¶
Figura 16: Búsqueda en una lista enlazada ordenada
El Programa 9 muestra el método buscar completo. Es fácil incorporar la nueva condición descrita anteriormente añadiendo otra variable booleana, detenerse, e inicializándola en False (línea 4). Mientras detenerse sea False (no detenerse) podemos seguir buscando hacia adelante en la lista (línea 5). Si se descubre algún nodo que contenga datos mayores que el elemento que estamos buscando, cambiaremos el valor de detenerse a True (líneas 9-10). Las líneas restantes son idénticas a la búsqueda en listas no ordenadas.
Programa 9
def buscar(self,item):
actual = self.cabeza
encontrado = False
detenerse = False
while actual != None and not encontrado and not detenerse:
if actual.obtenerDato() == item:
encontrado = True
else:
if actual.obtenerDato() > item:
detenerse = True
else:
actual = actual.obtenerSiguiente()
return encontrado
La modificación más significativa de un método tendrá lugar en agregar. Recuerde que para las listas no ordenadas, el método agregar podía simplemente ubicar un nuevo nodo al principio de la lista. Era el punto de acceso más fácil. Desafortunadamente, esto ya no funcionará con listas ordenadas. Ahora es necesario que descubramos el lugar específico donde pertenece un nuevo ítem en la lista ordenada existente.
Supongamos que tenemos la lista ordenada compuesta por los números 17, 26, 54, 77 y 93 y que queremos agregar el valor 31. El método agregar debe decidir que el nuevo ítem debe estar entre 26 y 54. La Figura 17 muestra la configuración que necesitamos. Como explicamos anteriormente, necesitamos recorrer la lista enlazada buscando el lugar donde se agregará el nuevo nodo. Sabemos que hemos encontrado ese lugar cuando nos quedamos sin nodos (actual se convierte en None) o el valor del nodo actual llega a ser mayor que el ítem que deseamos agregar. En nuestro ejemplo, ver el valor 54 nos detendrá.
Figura 17: Agregar un ítem a una lista enlazada ordenada¶
Figura 17: Agregar un ítem a una lista enlazada ordenada
Como vimos con las listas no ordenadas, es necesario tener una referencia adicional, nuevamente llamada previo, ya que actual no proporcionará acceso al nodo que se debe modificar. El Programa 10 muestra el método agregar completo. Las líneas 2-3 establecen las dos referencias externas y las líneas 9-10 de nuevo permiten que previo siga un nodo detrás de actual cada vez a través de las iteraciones. La condición (línea 5) permite que la iteración continúe mientras haya más nodos y el valor en el nodo actual no sea mayor que el ítem. En cualquier caso, cuando la iteración falla, hemos encontrado la ubicación para el nuevo nodo.
La parte restante del método completa el proceso de dos pasos que se muestra en la Figura 17. Una vez que se ha creado un nuevo nodo para el ítem, la única pregunta restante es si el nuevo nodo se agregará al principio de la lista enlazada o en algún lugar intermedio. De nuevo, previo == None (línea 13) puede utilizarse para proporcionar la respuesta.
Programa 10
def agregar(self,item):
actual = self.cabeza
previo = None
detenerse = False
while actual != None and not detenerse:
if actual.obtenerDato() > item:
detenerse = True
else:
previo = actual
actual = actual.obtenerSiguiente()
temp = Nodo(item)
if previo == None:
temp.asignarSiguiente(self.cabeza)
self.cabeza = temp
else:
temp.asignarSiguiente(actual)
previo.asignarSiguiente(temp)
La clase ListaOrdenada con los métodos discutidos hasta ahora están en el ActiveCode 1. Dejamos los métodos restantes como ejercicios. Usted debe considerar cuidadosamente si las implementaciones no ordenadas funcionarán dado que la lista ahora está ordenada.
3.23.1. Análisis de las listas enlazadas¶
Para analizar la complejidad de las operaciones de lista enlazadas, necesitamos considerar si se requiere recorrerlas. Considere una lista enlazada que tiene n nodos. El método estaVacia es \(O(1)\) ya que requiere un paso para comprobar si la referencia de la cabeza es None. tamano, por otro lado, siempre requerirá n pasos ya que no hay forma de saber cuántos nodos hay en la lista enlazada sin recorrerla desde la cabeza hasta el final. Por lo tanto, tamano es \(O(n)\). Agregar un ítem a una lista no ordenada siempre será \(O(1)\) ya que simplemente colocamos el nuevo nodo en la cabeza de la lista enlazada. Sin embargo, buscar y remover, así como agregar para una lista ordenada, requieren el proceso de recorrido. Aunque en promedio pueden necesitar recorrer sólo la mitad de los nodos, estos métodos son todos \(O(n)\) ya que en el peor de los casos procesarán cada nodo de la lista.
Quizás usted también haya notado que el desempeño de esta implementación difiere del desempeño real dado anteriormente para las listas de Python. Esto sugiere que las listas enlazadas no son la forma en que se implementan las listas de Python. La implementación real de una lista de Python se basa en la noción de una matriz. Discutiremos esto con más detalle en el Capítulo 8.