16.1. Una clase sencilla de vagones

En primer lugar, definiremos una clase muy simple, Nodo, que se comportará como un vagón: tendrá sólo dos atributos: dato, que servirá para almacenar cualquier información, y prox, que servirá para poner una referencia al siguiente vagón.

Además, como siempre, implementaremos el constructor y el método __str__ para poder imprimir el contenido del nodo.

class Nodo(object):
    def __init__(self, dato=None, prox = None):
        self.dato = dato
        self.prox = prox
    def __str__(self):
        return str(self.dato)

Ejecutamos este código:

>>> v3=Nodo("Bananas")
>>> v2=Nodo("Peras", v3)
>>> v1=Nodo("Manzanas", v2)
>>> print v1
Manzanas
>>> print v2
Peras
>>> print v3
Bananas

Con esto hemos generado la estructura de la Figura 16.1.

El atributo prox de v3 tiene una referencia nula, lo que indica que v3 es el último vagón de nuestra estructura.

Hemos creado una lista en forma manual. Si nos interesa recorrerla, podemos hacer lo siguiente:

Figura 16.1 Nodos enlazados

def verLista(nodo):
    """ Recorre todos los nodos a través de sus enlaces,
        mostrando sus contenidos. """

    # cicla mientras nodo no es None
    while nodo:
        # muestra el dato
        print nodo
        # ahora nodo apunta a nodo.prox
        nodo = nodo.prox

>>> verLista(v1)
Manzanas
Peras
Bananas

Es interesante notar que la estructura del recorrido de la lista es el siguiente:

• Se le pasa a la función sólo la referencia al primer nodo.
• El resto del recorrido se consigue siguiendo las cadena de referencias dentro de los nodos.

Si se desea desenganchar un vagón del medio de la lista, alcanza con cambiar el enganche:

>>> v1.prox=v3
>>> verLista(v1)
Manzanas
Bananas
>>> v1.prox = None
>>> verLista(v1)
Manzanas

De esta manera también se pueden generar estructuras impensables.

¿Qué sucede si escribimos v1.prox = v1? La representación es finita y sin embargo en este caso verLista(v1) no termina más. Hemos creado una lista infinita, también llamada lista circular.

16.1.1. Caminos

En una lista cualquiera, como las vistas antes, si seguimos las flechas dadas por las referencias, obtenemos un camino en la lista.

Los caminos cerrados se denominan ciclos. Son ciclos, por ejemplo, la autorreferencia de v1 a v1, como así también una flecha de v1 a v2 seguida de una flecha de v2 a v1.

16.1.2. Referenciando el principio de la lista

Una cuestión no contemplada hasta el momento es la de mantener una referencia a la lista completa. Por ahora para nosotros la lista es la colección de nodos que se enlazan a partir de v1. Sin embargo puede suceder que querramos borrar a v1 y continuar con el resto de la lista como la colección de nodos a tratar (en las listas de Python, del lista[0] no nos hace perder la referencia a lista).

Para ello lo que haremos es asociar una referencia al principio de la lista, que llamaremos lista, y que mantendremos independientemente de cuál sea el nodo que está al principio de la lista:

>>> v3=Nodo("Bananas")
>>> v2=Nodo("Peras", v3)
>>> v1=Nodo("Manzanas", v2)
>>> lista=v1
>>> verLista(lista)
Manzanas
Peras
Bananas

Ahora sí estamos en condiciones de borrar el primer elemento de la lista sin perder la identidad de la misma:

>>> lista=lista.prox
>>> verLista(lista)
Peras
Bananas