Next Up Previous Hi Index

Chapter 17

Listas enlazadas

17.1 Referencias incrustadas

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:

Recursive data structures lend themselves to recursive methods.

17.2 La clase Node

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?

17.3 Listas como colecciones

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.

17.4 Listas y recursividad

Es natural expresar muchas operaciones con listas usando métodos recursivos. El siguiente ejemplo es un algoritmo recursivo pra imprimir una lista invertida:

  1. Separar la lista en dos partes: el primer nodo (llamado cabecera); y el resto (llamado cola).
  2. Imprimir la cola invertida.
  3. Imprimir la cabecera.

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.

17.5 Listas infinitas

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.

17.6 Teorema fundamental de la ambigüedad

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.

17.7 Modificando listas

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.

17.8 Envoltorios y ayudantes

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.

17.9 La clase LinkedList

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?

17.10 Invariantes

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.

17.11 Glosario

referencia incrustada
Es una referencia almacenada en un atributo de un objeto.
Lista enlazada
Estructura de datos que implementa una colección usando una secuencia de nodos enlazados.
Nodo
Elemento de una lista, normalmente implementado como un objeto que contiene una referencia a otro objeto del mismo tipo.
Carga
Dato contenido en un nodo.
Enlace
Referencia incrustada usada para enlazar un objeto con otro.
Precondición
Afirmación que debe ser cierta para que un método funcione correctamente.
Teorema fundamental de la ambigüedad
Referencia a un nodo de una lista para tratarlo como un nodo individual o como el primero de la lista.
Singleton
Lista enlazada con un solo nodo.
Envoltorio
Método que actúa como mediador entre un método invocador y método ayudante, haciendo a menudo más fácil de invocar.
Ayudante
Método al que no se invoca directamente por un método invocador sino por otro método para formar parte de una operación.
Invariante
Afirmación que debería ser cierta para un objeto en todo momento (excepto tal vez cuando se está modificando el objeto).


Next Up Previous Hi Index