16.3. La clase ListaEnlazada

Basándonos en los nodos implementados anteriormente, pero buscando deslindar al programador que desea usar la lista de la responsabilidad de manipular las referencias, definiremos ahora la clase ListaEnlazada, de modo tal que no haya que operar mediante las referencias internas de los nodos, sino que se lo pueda hacer a través de operaciones de lista.

Más allá de la implementación en particular, se podrá notar que implementaremos los mismos métodos de las listas de Python, de modo que más allá del funcionamiento interno, ambas serán listas.

Definimos a continuación las operaciones que inicialmente deberá cumplir la clase ListaEnlazada.

• __str__, para mostrar la lista.
• __len__, para calcular la longitud de la lista.
• append(x), para agregar un elemento al final de la lista.
• insert(i, x), para agregar el elemento x en la posición i (levanta una excepción si la posición i es inválida).
• remove(x), para eliminar la primera aparición de x en la lista (levanta una excepción si x no está).
• pop([i]), para borrar el elemento que está en la posición i y devolver su valor. Si no se especifica el valor de i, pop() elimina y devuelve el elemento que está en el último lugar de la lista (levanta una excepción si se hace referencia a una posición no válida de la lista).
• index(x), devuelve la posición de la primera aparición de x en la lista (levanta una excepción si x no está).

Más adelante podrán agregarse a la lista otros métodos que también están implementados por las listas de Python.

Valen ahora algunas consideraciones más antes de empezar a implementar la clase:

• Por lo dicho anteriormente, es claro que la lista deberá tener como atributo la referencia al primer nodo que la compone.
• Como vamos a incluir un método __len__, consideramos que no tiene sentido recorrer la lista cada vez que se lo llame, para contar cuántos elementos tiene, alcanza con agregar un atributo más (la longitud de la lista), que se inicializa en 0 cuando se crea la lista vacía, se incrementa en 1 cada vez que se agrega un elemento y se decrementa en 1 cada vez que se borra un elemento.
• Por otro lado, como vamos a incluir todas las operaciones de listas que sean necesarias para operar con ellas, no es necesario que la clase Nodo esté disponible para que otros programadores puedan modificar (y romper) las listas a voluntad usando operaciones de nodos. Para eso incluiremos la clase Nodo de manera privada (es decir oculta), de modo que la podamos usar nosotros como dueños (fabricantes) de la clase, pero no cualquier programador que utilice la lista.

Python tiene una convención para hacer que atributos, métodos o clases dentro de una clase dada no puedan ser usados por los usuarios, y sólo tengan acceso a ellos quienes programan la clase: su nombre tiene que empezar con un guión bajo y terminar sin guión bajo. Así que para hacer que los nodos sean privados, nombraremos a esa clase como _Nodo, y la dejaremos tal como hasta ahora.

16.3.1. Construcción de la lista

Empezamos escribiendo la clase con su constructor.

class ListaEnlazada(object):
    " Modela una lista enlazada, compuesta de Nodos. "

    def __init__(self):
        """ Crea una lista enlazada vacía. """
        # prim: apuntará al primer nodo -None con la lista vacía
        self.prim = None
        # len: longitud de la lista - 0 con la lista vacía
        self.len = 0

Nuestra estructura ahora será como la representada por la Figura 16.2.

Figura 16.2 Una lista enlazada

Ejercicio 16.1. Escribir los métodos __str__ y __len__ para la lista.

16.3.2. Eliminar un elemento de una posición

Analizaremos a continuación pop([i]), que borra el elemento que está en la posición i y devuelve su valor. Si no se especifica el valor de i, pop() elimina y devuelve el elemento que está en el último lugar de la lista. Por otro lado, levanta una excepción si se hace referencia a una posición no válida de la lista.

Dado que se trata de una función con cierta complejidad, separaremos el código en las diversas consideraciones a tener en cuenta.

Si la posición es inválida (i menor que 0 o mayor o igual a la longitud de la lista), se considera error y se levanta la excepción ValueError.

Esto se resuelve con este fragmento de código:

# Verificación de los límites
if (i < 0) or (i >= self.len):
    raise IndexError("Índice fuera de rango")

Si no se indica posición, i toma la última posición de la lista. Esto se resuelve con este fragmento de código:

# Si no se recibió i, se devuelve el último.
if i == None:
    i = self.len - 1

Cuando la posición es 0 se trata de un caso particular, ya que en ese caso, además de borrar el nodo, hay que cambiar la referencia de self.prim para que apunte al nodo siguiente. Es decir, pasar de self.prim → nodo0 → nodo1 a self.prim → nodo1).

Esto se resuelve con este fragmento de código:

# Caso particular, si es el primero,
# hay que saltear la cabecera de la lista
if i == 0:
    dato = self.prim.dato
    self.prim = self.prim.prox

Vemos ahora el caso general:

Mediante un ciclo, se deben ubicar los nodos npi - 1 y npi que están en las posiciones i − 1 e i de la lista, respectivamente, de modo de poder ubicar no sólo el nodo que se borrará, sino también estar en condiciones de saltear el nodo borrado en los enlaces de la lista. La lista debe pasar de contener el camino npi - 1 → npi → npi.prox a contener el camino npi-1 → npi.prox.

Nos basaremos un esquema muy simple (y útil) que se denomina máquina de parejas:

Si nuestra secuencia tiene la forma ABCDE, se itera sobre ella de modo de tener las parejas AB, BC, CD, DE. En la pareja XY, llamaremos a X el elemento anterior y a Y el elemento actual. En general estos ciclos terminan o bien cuando no hay más parejas que formar, o bien cuando el elemento actual cumple con una determinada condición.

En nuestro problema, tenemos la siguiente situación:

• Las parejas son parejas de nodos.
• Para avanzar en la secuencia se usa la referencia al próximo nodo de la lista.
• La condición de terminación es siempre que la posición del nodo en la lista sea igual al valor buscado. En este caso particular no debemos preocuparnos por la terminación de la lista porque la validez del índice buscado ya fue verificada más arriba.

Esta es la porción de código correspondiente a la búsqueda:

n_ant = elf.prim
n_act = n_ant.prox
for pos in xrange(1, i):
    n_ant = n_act
    n_act = n_ant.prox

Al finalizar el ciclo, n_ant será una referencia al nodo i − 1 y n_act una referencia al nodo i.

Una vez obtenidas las referencias, se obtiene el dato y se cambia el camino según era necesario:

# Guarda el dato y elimina el nodo a borrar
dato = n_act.dato
n_ant.prox = n_act.prox

Finalmente, en todos los casos de éxito, se debe devolver el dato que contenía el nodo eliminado y decrementar la longitud en 1:

# hay que restar 1 de len
self.len -= 1

# y devolver el valor borrado
return dato

Finalmente, en el código 16.1 se incluye el código completo del método pop.

16.3.3. Eliminar un elemento por su valor

Análogamente se resuelve remove(self,x), que debe eliminar la primera aparición de x en la lista, o bien levantar una excepción si x no se encuentra en la lista.

Nuevamente, dado que se trata de un método de cierta complejidad, lo resolveremos por partes, teniendo en cuenta los casos particulares y el caso general.

# Código 16.1: pop: Método pop de la lista enlazada

def pop(self, i = None):
    """ Elimina el nodo de la posición i, y devuelve el dato contenido.
        Si i está fuera de rango, se levanta la excepción IndexError.
        Si no se recibe la posición, devuelve el último elemento. """

    # Si no se recibió i, se devuelve el último.
    if i is None:
        i = self.len - 1

    # Verificación de los límites
    if not (0 <= i < self.len):
        raise IndexError("Índice fuera de rango")

    # Caso particular, si es el primero,
    # hay que saltear la cabecera de la lista
    if i == 0:
        dato = self.prim.dato
        self.prim = self.prim.prox

    # Para todos los demás elementos, busca la posición
    else:
        n_ant = self.prim
        n_act = n_ant.prox
        for pos in xrange(1, i):
            n_ant = n_act
            n_act = n_ant.prox

        # Guarda el dato y elimina el nodo a borrar
        dato = n_act.dato
        n_ant.prox = n_act.prox

    # hay que restar 1 de len
    self.len -= 1
    # y devolver el valor borrado
    return dato

Los casos particulares son: la lista vacía, que es un error y hay que levantar una excepción; y el caso en el que x está en el primer nodo, en este caso hay que saltear el primer nodo desde la cabecera de la lista.

El fragmento de código que resuelve estos casos es:

if self.len == 0:
    # Si la lista está vacía, no hay nada que borrar.
    raise ValueError("Lista vacía")

# Caso particular, x esta en el primer nodo
elif self.prim.dato == x:
    # Se descarta la cabecera de la lista
    self.prim = self.prim.prox

El caso general también implica un recorrido con máquina de parejas, sólo que esta vez la condición de terminación es: o bien la lista se terminó o bien encontramos un nodo con el valor (x) buscado.

# Obtiene el nodo anterior al que contiene a x (n_ant)
n_ant = self.prim
n_act = n_ant.prox
while n_act != None and n_act.dato != x:
    n_ant = n_act
    n_act = n_ant.prox

En este caso, al terminarse el ciclo será necesario corroborar si se terminó porque llegó al final de la lista, y de ser así levantar una excepción; o si se terminó porque encontró el dato, y de ser así eliminarlo.

# Si no se encontró a x en la lista, levanta la excepción
if n_act == None:
    raise ValueError("El valor no ester en la lista.")

# Si encontró a x, debe pasar de n_ant -> n_x -> n_x.prox
# a n_ant -> n_x.prox
else:
    n_ant.prox = n_act.prox

Finalmente, en todos los casos de éxito debemos decrementar en 1 el valor de self.len. En el código 16.2 se incluye el código completo del método remove.

16.3.4. Insertar nodos

Debemos programar ahora insert(i, x), que debe agregar el elemento x en la posición i (y levantar una excepción si la posición i es inválida).

Veamos qué debemos tener en cuenta para programar esta función.

Si se intenta insertar en una posición menor que cero o mayor que la longitud de la lista debe levantarse una excepción.

# Código 16.2: remove: Método remove de la lista enlazada

def remove(self, x):
    """ Borra la primera aparición del valor x en la lista.
        Si x no está en la lista, levanta ValueError """

    if self.len == 0:
        # Si la lista está vacía, no hay nada que borrar.
        raise ValueError("Lista vacía")

    # Caso particular, x esta en el primer nodo
    elif self.prim.dato == x:
        # Se descarta la cabecera de la lista
        self.prim = self.prim.prox

    # En cualquier otro caso, hay que buscar a x
    else:
        # Obtiene el nodo anterior al que contiene a x (n_ant)
        n_ant = self.prim
        n_act = n_ant.prox
        while n_act != None and n_act.dato != x:
            n_ant = n_act
            n_act = n_ant.prox

        # Si no se encontró a x en la lista, levanta la excepción
        if n_act == None:
            raise ValueError("El valor no ester en la lista.")

        # Si encontró a x, debe pasar de n_ant -> n_x -> n_x.prox
        # a n_ant -> n_x.prox
        else:
            n_ant.prox = n_act.prox

    # Si no levantó excepción, hay que restar 1 del largo
    self.len -= 1

    if (i > self.len) or (i < 0):
        # error
        raise IndexError("Posición inválida")

Para los demás casos, hay que crear un nodo, que será el que se insertará en la posición que corresponda. Construimos un nodo nuevo cuyo dato sea x.

# Crea nuevo nodo, con x como dato:
nuevo = _Nodo(x)

Si se quiere insertar en la posición 0, hay que cambiar la referencia de self.prim.

# Insertar al principio (caso particular)
if i == 0:
    # el siguiente del nuevo pasa a ser el que era primero
    nuevo.prox = self.prim
    # el nuevo pasa a ser el primero de la lista
    self.prim = nuevo

Para los demás casos, nuevamente será necesaria la máquina de parejas. Obtenemos el nodo anterior a la posición en la que queremos insertar.

# Insertar en cualquier lugar > 0
else:
    # Recorre la lista hasta llegar a la posición deseada
    n_ant = self.prim
    for pos in xrange(1,i):
        n_ant = n_ant.prox

    # Intercala nuevo y obtiene n_ant -> nuevo -> n_ant.prox
    nuevo.prox = n_ant.prox
    n_ant.prox = nuevo

En todos los casos de éxito se debe incrementar en 1 la longitud de la lista.

# En cualquier caso, incrementar en 1 la longitud
# self.len += 1

En el Código 16.3 se incluye el código resultante del método insert.

Ejercicio 16.2. Completar la clase ListaEnlazada con los métodos que faltan: append e index.

Ejercicio 16.3. En los bucles de máquina de parejas mostrados anteriormente, no siempre es necesario tener la referencia al nodo actual, puede alcanzar con la referencia al nodo anterior. Donde sea posible, eliminar la referencia al nodo actual. Una vez hecho esto, analizar el código resultante, ¿Es más elegante?

Ejercicio 16.4. Mantenimiento: Con esta representación conseguimos que la inserción en la posición 0 se realice en tiempo constante, sin embargo ahora append es líneal en la longitud de la lista. Como nuestro cliente no está satisfecho con esto debemos agregar un atributo más a los objetos de la clase, la referencia al último nodo, y modificar append para que se pueda ejecutar en tiempo constante. Por supuesto que además hay que modificar todos los métodos de la clase para que se mantenga la propiedad de que ese atributo siempre es una referencia al útimo nodo.

# Código 16.3: insert: Método insert de la lista enlazada
def insert(self, i, x):
    """ Inserta el elemento x en la posición i.
        Si la posición es inválida, levanta IndexError """

    if (i > self.len) or (i < 0):
        # error
        raise IndexError("Posición inválida")

    # Crea nuevo nodo, con x como dato:
    nuevo = _Nodo(x)

    # Insertar al principio (caso particular)
    if i == 0:
        # el siguiente del nuevo pasa a ser el que era primero
        nuevo.prox = self.prim
        # el nuevo pasa a ser el primero de la lista
        self.prim = nuevo

# Insertar en cualquier lugar > 0
else:
    # Recorre la lista hasta llegar a la posición deseada
    n_ant = self.prim
    for pos in xrange(1,i):
        n_ant = n_ant.prox

    # Intercala nuevo y obtiene n_ant -> nuevo -> n_ant.prox
    nuevo.prox = n_ant.prox
    n_ant.prox = nuevo

# En cualquier caso, incrementar en 1 la longitud
self.len += 1