|
|
|
|
|
|
|
Hemos visto ejemplos de atributos que hacen referencia a otros objetos: referencias explícitas (Sección 12.8). Las listas enlazadas, estructuras de datos bastante comunes, hacen uso de esta característica.
Las listas enlazadas se componen de nodos. Cada nodo presenta dos campos: por una parte, una referencia al siguiente nodo de la lista; por otra, una unidad de información llamada dato.
Las listas enlazadas se definen a partir de una estructura de datos recursiva.
Así, una lista enlazada puede ser
- una lista vacía, representada por None, o
- un nodo con un objeto dato y una referencia a una lista enlazada.
Las estructuras de datos recursivas permiten la utilización de métodos recursivos.
Comentarios
Como siempre, cuando establecemos una nueva clase, empezamos con los métodos de inicialización y __str__. De esta manera, podemos comprobar el mecanismo básico de creación y visualización del nuevo tipo:
class Nodo:
def __init__(self, dato=None, siguiente=None):
self.dato = dato
self.siguiente = siguiente
def __str__(self):
return str(self.dato)
Los parámetros del método de inicialización son opcionales. Por defecto, el campo dato y el enlace siguiente poseen el valor None.
La representación como cadena de un nodo no es más que la representación como cadena del campo dato. Gracias a la función str, podemos almacenar cualquier valor en una lista.
Para comprobar la implementación realizada, podemos crear un Nodo y visualizarlo:
>>> nodo = Nodo("comprobar")
>>> print nodo
comprobar
Para que resulte más interesante, podemos utilizar una lista en la que figure más de un nodo:
>>> nodo1 = Nodo(1)
>>> nodo2 = Nodo(2)
>>> nodo3 = Nodo(3)
Este código nos permite crear tres nodos. Sin embargo, aún no podemos hablar de lista, ya que los nodos no están enlazados. El diagrama de estado quedaría de la siguiente forma:
Para enlazar los nodos, tenemos que relacionar el primero con el segundo, y el segundo con el tercero:
>>> nodo1.siguiente = nodo2
>>> nodo2.siguiente = nodo3
El tercer nodo apunta a None, lo que indica el final de la lista. En este punto, el diagrama de estado sería el siguiente:
Ahora, ya sabes crear nodos y relacionarlos para formar una lista. Pero, ¿para qué?
Comentarios
Las listas son bastante útiles, pues nos permiten almacenar múltiples objetos en una única entidad: colección. En el ejemplo, el primer nodo sirve de referencia para la lista entera.
Para considerar la lista un parámetro, simplemente tenemos que asignar una referencia al primer nodo. Por ejemplo, la función printLista permite considerar cada nodo un argumento. A partir de la cabecera de la lista, se muestra en pantalla cada nodo hasta llegar al final:
def printLista(nodo):
while nodo:
print nodo,
nodo = nodo.siguiente
print
Para invocar este método, simplemente hay que asignar una referencia al primer nodo:
>>> printLista(nodo1)
1 2 3
Con printLista, obtenemos una referencia para el primer nodo de la lista. Sin embargo, no contamos con una variable que permita relacionarlo con el resto de los nodos. Para ello, tendremos que usar el valor siguiente de cada nodo.
Para recorrer una lista enlazada, se suele emplear una variable bucle. Esta funciona como un nodo que permite hacer referencia al resto de los nodos de manera sucesiva.
El siguiente diagrama muestra el valor de la lista y los valores que toma el nodo:
Por convención, las listas se suelen visualizar entre corchetes, y con comas entre cada uno de los elementos: [1, 2, 3]. A modo de ejercicio, intenta modificar la función printLista para generar resultados en el citado formato.Comentarios
Para expresar numerosas operaciones relacionadas con la lista, se suelen emplear métodos recursivos. A continuación, y a modo de ejemplo, mostramos un algoritmo recursivo que permite visualizar una lista desde atrás hacia adelante:
Evidentemente, el segundo paso (llamada recursiva) implica la existencia de un método que posibilite mostrar en pantalla una lista desde atrás hacia adelante. Si presuponemos que la llamada recursiva funciona, una posibilidad bastante factible, no podemos dudar del éxito de este algoritmo.
Lo único que necesitamos es un caso base y una manera de demostrar que se puede encontrar uno para cualquier lista. Dada la definición recursiva de las listas, la lista vacía ya es un caso base natural, representado por None:
def printAtras(lista):
if lista == None: return
cabecera = lista
cola = lista.siguiente
printAtras(cola)
print cabecera,
La primera línea muestra cómo conseguir un caso base sin hacer nada. En las dos siguientes, observamos que la lista se divide en cabecera y cola. Las dos últimas líneas permiten visualizar la lista. La coma final impide que Python muestre un salto de línea después de cada nodo.
Para invocar este método, hacemos la misma operación efectuada con printLista:
>>> printAtras(nodo1)
3 2 1
El resultado es la visualización de una lista desde atrás hacia adelante.
Probablemente, te estés preguntando por qué printLista y printAtras son funciones, y no métodos, en la clase Nodo. La razón es muy sencilla: deseamos utilizar None para representar las listas vacías, y no está permitido invocar un método a partir de dicho valor. Esta limitación hace que sea muy complicado escribir códigos para manipular la lista con un estilo orientado a objetos en el que reine la claridad.
Ahora bien, ¿podemos demostrar que la función printAtras siempre logra completarse? Es decir, ¿nos permitirá encontrar un caso base en todo momento? La respuesta es no. Algunas listas no funcionan con este método.
Comentarios
No hay nada que impida que un nodo apunte a otro anterior, o a él mismo. Por ejemplo, en la siguiente ilustración, podemos observar una lista con dos nodos, uno de los cuales se apunta a sí mismo:
Si invocamos printLista en esta lista, comenzará una oleada eterna de bucles. Si invocamos printAtras, la recursión no tendrá fin. Este es el gran inconveniente de las listas infinitas.
Sin embargo, en algunas ocasiones, pueden ser bastante útiles. Por ejemplo, podemos representar un número como una lista de dígitos y utilizar una lista infinita para representar una fracción que se repite.
A pesar de esto, siempre es un problema no poder demostrar que printLista y printAtras se completan en todos los casos. Lo único que podemos hacer es establecer sentencias hipotéticas: “Estos métodos se completan cuando la lista no tiene bucles”. Estas afirmaciones se denominan condiciones previas. Estas hacen referencia a una restricción relacionada con alguno de los parámetros, y describen la respuesta del método en caso de que esta se cumpla. Más adelante, te mostraremos más ejemplos.
Comentarios
Algún aspecto de printAtras puede habernos causado sorpresa:
cabecera = lista
cola = lista.siguiente
Tras la primera asignación, vemos que cabecera y lista son del mismo tipo y poseen el mismo valor. ¿Por qué creamos entonces una nueva variable?
La razón es simple: ambas variables desempeñan diferentes funciones. Mientras que cabecera hace referencia a un único nodo, lista apunta al primer nodo de una lista. Estas "funciones" no forman parte del programa, sino que se encuentran en la mente del programador.
Normalmente, no podemos determinar la función que cumple una variable con solo ver el programa. A pesar de que esta ambigüedad puede resultar útil, es posible que dificulte la lectura del programa. A menudo empleamos nombres de variables tales como nodo y lista para especificar el uso que pretendemos hacer de una variable, y, en ocasiones, creamos variables adicionales con el fin de desambiguar.
Podríamos haber escrito printAtras sin cabecera y cola, lo que haría que la variable fuera más concisa, pero menos clara:
def printAtras(lista):
if lista == None: return
printAtras(lista.siguiente)
print lista,
Al observar las dos llamadas a función, debemos recordar que, mientras que printAtras considera su argumento una colección, print trata el suyo como un único objeto.
El teorema fundamental de la ambigüedad describe la ambigüedad inherente a la referencia de un nodo:
Una variable que apunta a un nodo puede considerar ese nodo de dos maneras: un único objeto o el primer objeto de una lista de nodos.Comentarios
Existen dos formas de modificar una lista enlazada. A pesar de que podemos cambiar los datos de uno de los nodos, las operaciones más interesantes son las que nos permiten añadir, eliminar y reorganizar los nodos.
Como ejemplo, escribamos un método que elimine el segundo nodo de una lista y que nos devuelva una referencia al nodo eliminado:
def eliminarSegundo(lista):
if lista == None: return
primero = lista
segundo = lista.siguiente
# hacer que el primer nodo apunte al tercero
primero.siguiente = segundo.siguiente
# separar el segundo nodo del resto de la lista
segundo.siguiente = None
return segundo
Estamos utilizando de nuevo variables temporales para que el código sea más legible. A continuación, podrás ver cómo se utiliza este método:
>>> printLista(nodo1)
1 2 3
>>> eliminado = eliminarSegundo(nodo1)
>>> printLista(eliminado)
2
>>> printLista(nodo1)
1 3
Este diagrama de estado muestra el resultado de la operación:
¿Qué ocurre si invocas este método en una lista que consta de un único elemento (instancia única o singleton)? Y ¿qué ocurre si tratas una lista vacía como si fuera un argumento? ¿Existe alguna condición previa para este método? Si la hay, establece un método para manejar, de un modo razonable, una posible violación de la condición previa.
Comentarios
En ocasiones, puede resultar útil dividir el funcionamiento de una lista en dos métodos. Por ejemplo, si queremos visualizar una lista desde atrás hacia adelante en el formato de lista convencional [3, 2, 1], podemos utilizar el método printAtras para mostrar en pantalla 3, 2,, pero necesitaríamos un método distinto para visualizar los corchetes y el primer nodo. Llamémoslo printAtrasBien:
def printAtrasBien(lista) :
print "[",
if lista != None :
cabecera = lista
cola = lista.siguiente
printAtras(cola)
print cabecera,
print "]",
Sería conveniente probar métodos como este para comprobar si son válidos para casos especiales, tales como una lista vacía o una instancia única.
Podemos emplear este método en cualquier parte del programa: con él invocamos directamente printAtrasBien, y este último invoca printAtras por nosotros. En este sentido, printAtrasBien actúa como envoltorio, y utiliza printAtras como ayudante.
Comentarios
Existen algunos problemas delicados en lo referente a la forma en la que hemos estado implementando las listas. En el caso de producirse una inversión de causa y efecto, propondríamos, primero, una implementación alternativa; y, a continuación, explicaríamos los problemas que esta soluciona.
En primer lugar, crearemos una nueva clase denominada ListaEnlazada. Esta clase posee dos atributos: una referencia al primer nodo y un número entero que expresa la longitud de la lista. Los objetos ListaEnlazada sirven para manipular listas de objetos Nodo:
class ListaEnlazada :
def __init__(self) :
self.longitud = 0
self.cabecera = None
Una de las ventajas de la clase ListaEnlazada es que proporciona un lugar idóneo para las funciones del envoltorio, tales como printAtrasBien. Así, podemos convertir esta función en un método de la clase ListaEnlazada:
class ListaEnlazada :
...
def printAtras(self):
print "[",
if self.cabecera != None:
self.cabecera.printAtras()
print "]",
class Nodo:
...
def printAtras(self):
if self.siguiente != None:
cola = self.siguiente
cola.printAtras()
print self.dato,
Para complicar algo más las cosas, hemos denominado este método printAtrasBien. Ahora hay dos métodos con el nombre printAtras: uno de ellos se encuentra en la clase Nodo (ayudante); y el otro en la clase ListaEnlazada (envoltorio). Cuando el envoltorio invoca self.cabecera.printAtras, está invocando al ayudante, ya que self.cabecera es un objeto Nodo.
Otra de las ventajas de la clase ListaEnlazada es que facilita la adición o la eliminación del primer elemento de una lista. Por ejemplo, agregarPrimero es un método para las ListasEnlazadas. Este método considera que un dato es un argumento, y lo coloca al principio de la lista:
class ListaEnlazada:
...
def agregarPrimero(self, dato):
nodo = Nodo(dato)
nodo.siguiente = self.cabecera
self.cabecera = nodo
self.longitud = self.longitud + 1
De nuevo, te recomendamos que compruebes estos códigos para ver si son válidos para los casos especiales. Por ejemplo, ¿qué pasaría si, al principio, la lista estuviera vacía?
Comentarios
Algunas listas están "bien formadas", pero otras, no. Pongamos un ejemplo: si una lista contiene un bucle, este hará que muchos de nuestros métodos fallen. Por ello, la ausencia de bucles en las listas sería un requisito esencial. Otro requisito sería que el valor longitud en el objeto ListaEnlazada fuera igual al número actual de nodos de la lista.
Estos requisitos reciben el nombre de invariantes, pues se supone que deberían cumplirse siempre en todos los objetos. La tarea de especificar invariantes para los objetos es una práctica de programación muy útil, ya que facilita la detección de errores y la comprobación tanto de la validez de los códigos como de la integridad de las estructuras de datos.
Un dato confuso, en lo que hace referencia a las invariantes, es que, en ocasiones, no se respetan. Por ejemplo, en medio de agregarPrimero, después de haber añadido el nodo, y antes de haber incrementado la longitud, se viola la invariante. No obstante, este tipo de violación es aceptable; de hecho, muchas veces, es imposible modificar un objeto sin violar, aunque sea por poco tiempo, una invariante. Por lo general, es necesario que los métodos que violan una invariante sean capaces también de restablecerla.
Si se violara una invariante situada en una parte importante de un código, sería imprescindible que este hecho se reflejara en los comentarios, con el fin de que no se realizara ninguna operación dependiente de esa invariante.
Comentarios
|
|
|
|
|
|
|