![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
Hemos visto ejemplos de atributos que hacen referencia a otros objetos, a los que llamamos referencias incrustadas (véase la sección ). Una estrutura de datos común, la lista enlazada, gana ventaja con esta característica.
Las listas enlazadas se componen de nodos, donde cada nodo contiene una referencia al próximo nodo de la lista. Además, cada nodo contiene una unidad de datos llamada carga
Podemos considerar una lista enlazada como una estructura de datos recursiva
Una lista enlazada puede ser:
- la lista vacía, representada por None, o bien
- un nodo que contiene un objeto de carga y una referencia a una lista enlazada.
Recursive data structures lend themselves to recursive methods.
Como es usual cuando se escribe una clase, comenzaremos con la inicialización y los métodos __str__, así que podemos comprobar el mecanismo básico de crear y mostrar el nuevo tipo:
class Node:
def __init__(self, cargo=None, next=None):
self.cargo = cargo
self.next = next
def __str__(self):
return str(self.cargo)
Como es habitual, los parámetros para el método de inicialización son opcionales. Por defecto, la carga y el enlace, next, se ponen a None.
La representación alfanumérica de un nodo es únicamente la de la carga. Ya que se puede pasar cualquier valor a la función str, podemos guardar cualquier valor en una lista.
Para comprobar la implementación en este punto, podemos crear un Nodee imprimirlo:
>>> node = Node("test")
>>> print node
test
Para hacerlo más interesante, necesitaremos una lista que contenga más de un nodo:
>>> node1 = Node(1)
>>> node2 = Node(2)
>>> node3 = Node(3)
Este código crea tres nodos, pero aún no tenemos una lista porque los nodos todavía no están enlazados. El diagrama de estados tiene el siguiente aspecto:

Para enlazar los nodos, debemos hacer que el nodo haga referencia al segundo, y que éste haga referencia al tercero:
>>> node1.next = node2
>>> node2.next = node3
La referencia del tercer nodo será None, que indica que es el final de la lista. Ahora el diagrama de estados tendrá el siguiente aspecto:

Ahora sabemos cómo crear nodos y enlazarlos en listas. ¿Se puede explicar de forma más sencilla?
Las listas son utiles porque aportan un modo de ensamblar múltiples objetos dentro de una entidad simple, a veces llamada colección. En el ejemplo, el primer nodo de la lista sirve como referendcia a la lista completa.
Para pasar la lista como parámetro, sólo tenemos que hacer referencia al primer nodo. Por ejemplo, la función printList toma como argumento un nodo simple. Empezando con el cabeza de lista, imprime cada nodo hasta que llega al final.
def printList(node):
while node:
print node,
node = node.next
print
Para llamar a este método, pasamos una referencia al primer nodo:
>>> printList(node1)
1 2 3
Dentro de printList tenemos una referencia al primer nodo de la lista, pero no hay una variable que haga referencia al otro nodo. Tendremos que usar el valor next de cada nodo para acceder al siguiente nodo.
Para atravesar una lista enlazada, es común usar una variable de un bucle como node para ahacer referencia a cada uno de los nodos de la sucesión.
Este diagrama muestra el valor de list y los valores que va tomando node:

Por convenio, generalmente las listas se imprimen entre corchetes con comas entre los elementos, como [1, 2, 3]. Como ejercicio, modifique printList para que genere una salida con este formato.
Es natural expresar muchas operaciones con listas usando métodos recursivos. El siguiente ejemplo es un algoritmo recursivo pra imprimir una lista invertida:
Por supuesto, el paso 2, la llamada recursiva supone que tenemos una
manera de imprimir una lista invertida. Pero si suponemos que la
llamada recursiva funciona dogma de fe entonces podemos estar
convencidos de que este algoritmo funciona.
Todo lo que necesitamos es un caso inicial y una forma de probar que para cualquier lista, podemos obtener el caso inicial. Dada la definición recursiva de una lista, un caso inicial natural es la lista vacía, representada por None:
def printBackward(list):
if list == None: return
head = list
tail = list.next
printBackward(tail)
print head,
La primera línea maneja el caso inicial de no hacer nada. Las dos siguientes líneas dividen la lista en cabecera y cola. Las dos últimas líneas imprimen la lista. La coma que hay al final de la línea evitan que Python imprima en una nueva línea después de imprimir un nodo.
Llamamos este método tal como lo hemos nombrado, printList:
>>> printBackward(node1)
3 2 1
el resultado es una lista invertida.
Usted se podría preguntar por qué printList y printBackwardson funciones y no métodos de la clase Node. La razón es que queremos usar None para representar la lista vacía y no es legal llamar un método de una lista vacía, None. Esta limitación resulta algo incómoda a la hora de escribir estilos de código limpios para manipulación de listas de forma orientada a objetos.
¿Se puede probar que printBackward siempre acabará? En otras palabras, ¿siempre alcanzaremos el caso inicial? De hecho, la respuesta es no. Algunas listas harán que el método no funcione.
No hay manera de prevenir que un nodo haga referencia a un nodo anterior de la lista, incluida él mismo. Por ejemplo, esta figura muestra una lista con dos nodos, uno de los cuales apunta a sí mismo:

Si llamamos a printList en la lista, entrará en un bucle infinito. si llamamos a printBackward, lo hará de forma infinitamente recursiva. Eeste tipo de comportamiento da lugar a que las listas infinitas hagan muy difícil poder trabajar con ellas.
Sin embargo, hay ocasiones que resultan útiles Por ejemplo, podríamos representar un número como una lista de dígitos y usar una lista infinita para representar una fracción repetida:
A pesar de todo, es problemático que no podamos probar que printListy printBackward puedan terminar correctamente. Lo mejor que podemos hacer es seguir la hipotésis de que "si la lista no contiene bucles, entonces estos métodos podrán terminar." Este tipo de afirmación se conocen como precondiciones. Imponen una restricción en uno de los parámetros del método si la restricción se satisface. Veremos más ejemplos más adelante.
Una parte de printBackward podría habernos sorprendido:
head = list
tail = list.next
Después de la primera asignación, la cabecera y la cola tienen el mismo tipo. Asi que, ¿por qué no hemos creado un nueva variable?
The reason is that the two variables play different roles. We think
La razón es que las dos variables juegan papeles diferentes. Pensamos en la cabecera como una referencia al primer nodo de la lista. Estos "papeles" no forman parte del programa, sino en la mente del programador.
En general no podemos decir con sólo mirar un programa qué papel desempeñará un variable. Esta ambigüedad es útil, pero hará más difícil la lectura del programa. A menudo usaremos nombres para las variables como node y list para explicar cómo intentamos usar una variable y a veces crear variables adicionales para prevenir ambigüedades.
Podríamos haber escrito printBackward sin cabecera ni cola, que lo haría mas conciso, pero posiblemente menos claro:
def printBackward(list) :
if list == None : return
printBackward(list.next)
print list,
Mirando esas dos llamadas, hemos de recordar que printBackwardtrata sus argumentos como una colección y print los trata como a un sólo objeto.
El teorema fundamental de la ambigüedad indica que la ambigüedad que es inherente en una referencia a un nodo:
Una variable que hace apunta a nodo puede tratar a este nodo como un objeto o como el primero de una lista de nodos.
Hay dos formas de modificar una lista enlazada. Obviamente, podemos cambiar la carga de uno de los nodos, pero las operaciones más interesantes son las que añaden, quitan o reordenan los nodos.
Como ejemplo, escribamos un método que quite el segundo nodo de la lista y devuelva una referencia al nodo quitado:
def removeSecond(list):
if list == None: return
first = list
second = list.next
# make the first node refer to the third
first.next = second.next
# separate the second node from the rest of the list
second.next = None
return second
De nuevo, estamos usando variables temporales para hacer más legible el código. Ésta es la fomrma como usamos este método:
>>> printList(node1)
1 2 3
>>> removed = removeSecond(node1)
>>> printList(removed)
2
>>> printList(node1)
1 3
El diagrama de estado nos muestra el efecto de la operación:

¿Qué ocurriría si llamamos a este método y pasamos una lista de un único elemento (un singleton)? ¿Qué pasaría si pasamos una lista vacía como argumento? ¿Hay una precondición para este método? Si es así, establecer el método para manejar una violación de una precondición sería una forma razonable.
A menudo es útil dividir una operación de listas en dos métodos. Por ejemplo, para imprimir una lista invertida en el formato convencional [3, 2, 1] podemos usar el método printBackward para imprimir 3, 2, pero necesitaremos un método aparte para imprimir los corchetes y el primer nodo. Llamémoslo printBackwardNicely:
def printBackwardNicely(list) :
print "[",
if list != None :
head = list
tail = list.next
printBackward(tail)
print head,
print "]",
De nuevo, vemos que es buena idea comprobar métodos como éste para ver si funcionan con casos especiales como una lista vacía o un singleton.
Cuando usamos este método en algún otro lugar del programa, llamamos a printBackwardNicely directamente, y llama a printBackward en nuestro lugar. En cierto modo, printBackwardNicely actúa como un envoltorio, y utiliza printBackward como ayudante.
Existen ciertos problemas de licados con la forma en que se implementaron las listas. Inviertiendo el orden de causa y efecto, propondremos primero una implementación alternativa y explicaremos luego lo problemas que ésta resuelve.
En primer lugar crearemos un nueva clase llamada LinkedList. Sus atributos son un entero que contiene la longitud de la lista y una referencia al primer nodo. Los objetos LinkedList sirven de instrumentos para la manipulación de las listas de los objetos de tipo Node:
class LinkedList :
def __init__(self) :
self.length = 0
self.head = None
Una ventaja de la clase LinkedList es que suministra un marco natural para poner funciones como printBackwardNicely, del cual podemos crear un método de la clase LinkedList:
class LinkedList:
...
def printBackward(self):
print "[",
if self.head != None:
self.head.printBackward()
print "]",
class Node:
...
def printBackward(self):
if self.next != None:
tail = self.next
tail.printBackward()
print self.cargo,
Para complicar un poco más las cosas, renombramos printBackwardNicely. Ahora hay dos métodos llamados printBackward: uno en la clase Node (el ayudante); y otro en la clase LinkedList (el envoltorio). Cuando el envoltorio llama a self.head.printBakward, está llamando al ayudante, ya que self.head es un objeto de tipo Node
Otra ventaja de la clase LinkedList es que facilita la forma de añadir o quitar el primer elemento de una lista. Por ejemplo, addFirst es un método para LinkedList; toma un elemento de la carga como argumento y lo coloca en el principio de la lista:
class LinkedList:
...
def addFirst(self, cargo):
node = Node(cargo)
node.next = self.head
self.head = node
self.length = self.length + 1
Como suele ser usual, deberíamos comprobar código como éste para ver si maneja casos especiales. Por ejemplo, ¿qué ocurriría si la la lista está unicialmente vacía?
Algunas listas están "bien formadas"; otras no lo están. Por ejemplo, si una lista contiene un bucle, provocará que nuestros métodos se cuelguen, así que podríamos las listas no contengan bucles. Otro requisito es que el valor de la longitud en el objeto de tipo LinkedList debería ser igual al número actual de nodos de la lista.
A este tipo de requisitos los llamaremos invariantes porque, idealmente deberían cumplirse en todos los onjetos en todo momento. Especificando invariantes para objetos la práctica de la programación resulta útil porque hace más fácil probar la corrección de código, comprobar la integridad de las estructyuras de datos y la detección de errores.
Una cosa que a veces confunde respecto a los invariantes es que hay veces que son violados. Por ejemplo, en medio de addFirst, después de haber incrementado la longitud, se viola el invariante. Se acepta este tipo de violación; de hecho, a menudo es imposible modificar un objeto sin violar un invariante durante al menos un corto espacio de tiempo. Normalmente, se requiere que todo método que viole un invariante deba restablecerlo a éste.
If there is any significant stretch of code in which the invariant is violated, it is important for the comments to make that clear, so that no operations are performed that depend on the invariant.
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |