Algoritmos de Programación con Python

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:

Nodos enlazados

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.

Advertencia Las listas circulares no tienen nada de malo en sí mismas, mientras su representación sea finita. El problema, en cambio, es que debemos tener mucho cuidado al escribir programas para recorrerlas, ya que el recorrido debe ser acotado (por ejemplo no habría problema en ejecutar un programa que liste los 20 primeros nodos de una lista circular).

Cuando una función recibe una lista y el recorrido no está acotado por programa, se debe aclarar en su precondición que la ejecución de la misma terminará sólo si la lista no contiene ciclos. Ése es el caso de la función verLista(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

Copyright (c) 2011-2014 Rosita Wachenchauzer, Margarita Manterola, Maximiliano Curia, Marcos Medrano, Nicolás Paez. La copia y redistribución de esta página se permite bajo los términos de la licencia Creative Commons Atribución - Compartir Obras Derivadas Igual 3.0 siempre que se conserve esta nota de copyright.