Cap. 24 - Listas enlazadas (Linked Lists)

24.1) Referencias embebidas

Hemos visto ejemplos de atributos que hacen referencia a otros objetos, a los cuales llamamos referencias embebidas. - Una estructura de datos muy común, la lista enlazada, hace uso de este procedimiento. Las listas enlazadas están formadas por nodos, y cada nodo contiene una referencia al siguiente nodo de la lista. - Por otro lado, cada nodo contiene una unidad de datos llamada cargo (o datos, o contenido, etc.). La lista enlazada es un ejemplo de estructura recursiva de datos porque tiene una definición recursiva. Una lista enlazada es o bien: - 1) La lista vacía, representada por None, o - 2) Un nodo que contiene un cargo y una referencia a otra lista enlazada. Las estructuras de datos recursivas se prestan muy bien, como veremos, a la implementación de métodos recursivos.

24.2) La clase Nodo

Como es habitual al escribir una nueva clase, comenzaremos con los métodos de inicialización y __str__, para que podamos testear los mecanismos básicos de creación y display del nuevo tipo: class Nodo: def __init__(self, cargo=None, next=None): self.cargo = cargo self.next = next def __str__(self): return str(self.cargo) Como de costumbre, los parámetros para el método de inicialización son opcionales. Por defecto, tanto el cargo como el link, next, se inicializan a None. La representación como string de un Nodo es simplemente la representación de su cargo. Dado que cualquier valor puede pasarse a la función str, podemos guardar cualquier valor en la lista. Para testear la implementación, podemos crear un Nodo e imprimirlo: >>> nodo = Nodo("test") >>> print(nodo) test Para hacerlo más interesante, necesitamos una lista con más nodos: >>> nodo1 = Nodo(1) >>> nodo2 = Nodo(2) >>> nodo3 = Nodo(3) Este código crea 3 nodos, pero todavía no tenemos una lista porque no están enlazados. El diagrama de estados se ve así: Para enlazar los nodos tenemos que hacer que el primer nodo se refiera al segundo, y que el segundo se refiera al tercero: >>> nodo1.next = nodo2 >>> nodo2.next = nodo3 La referencia del tercer nodo es None, lo que indica que está al final de la lista. Ahora sabes cómo crear nodos y enlazarlos en listas. Lo que todavía tal vez no esté muy claro es por qué lo hacemos.

24.3) Listas como colecciones

Las listas son útiles porque proveen un modo de combinar varios objetos en una única entidad, a veces llamada colección. - En el ejemplo anterior, el primer nodo de la lista sirve como referencia hacia la lista completa. Para pasar la lista como parámetro, alcanza con pasar una referencia al primer nodo. - Por ejemplo, la función print_lista toma un nodo como argumento. - Comenzando por el cabezal de la lista, imprime cada nodo hasta que llega al final: def print_lista(nodo): while nodo is not None: print(nodo, end=" ") nodo = nodo.next print() Para llamar al método, pasamos una referencia al primer nodo: >>> print_lista(nodo1) 1 2 3 Dentro de print_lista tenemos una referencia al primer nodo de la lista, pero no hay variable que se refiera a los otros nodos. - Tenemos que usar el valor de next de cada nodo para alcanzar el nodo siguiente. Para recorrer una lista enlazada, es común utilizar una variable de loop como nodo para irse refiriendo a cada uno de los nodos de la sucesión. El siguiente diagrama muestra el valor de lista y los valores que va tomando nodo durante el bucle:

24.4) Listas y recursión

Es natural expresar varias operaciones de listas usando métodos recursivos. Por ejemplo, el siguiente es un algoritmo recursivo para imprimir una lista al revés: 1. Separar la lista en dos piezas: el primer nodo (llamado la cabeza) y el resto (llamado la cola). 2. Imprimir la cola al revés. 3. Imprimir la cabeza. Por supuesto, el paso 2, que es el llamado recursivo, asume que ya sabemos cómo imprimir una lista al revés. - Pero si aceptamos por el momento que el llamado recursivo funciona, entonces es fácil ver que nuestro algoritmo completo funcionará. Todo lo que necesitamos es un caso base y una forma de probar que, para cualquier lista, tarde o temprano terminaremos en el caso base. - Dada la definición recursiva de lista, un caso base natural es la lista vacía, representada por None def print_lista_invertida(lista): if lista is None: return cabeza = lista cola = lista.next print_lista_invertida(cola) print(cabeza, end=" ") La primera línea maneja el caso baso, haciendo nada (porque si la lista es vacía, no hay nada que imprimir). - Las siguientes dos líneas dividen a la lista en cabeza y cola. - Las últimas dos líneas son las que imprimen la lista (primero se imprime la cola invertida y luego la cabeza, para que toda la lista se imprima al revés). - El argumento end de la sentencia print evita que Python agregue un fin de línea después de imprimir cada nodo. Llamamos a este método del mismo modo que llamamos a print_lista: >>> print_lista_invertida(nodo1) 3 2 1 El resultado es la lista invertida. Tal vez te estés preguntando por qué print_lista y print_lista_invertida se implementaron como funciones y no como métodos de la clase Nodo. - La razón es que queremos usar None para representar la lista vacía, y no es legal llamar a un método sobre None. - Esta limitación hace un poco extraño el manejo de listas (enlazadas) si uno programa con estilo de P.O.O. ¿Podemos demostrar que imprimir_lista_invertida siempre va a terminar? En otras palabras, ¿alcanzará siempre el caso base? - De hecho, la respuesta es no. Algunas listas pueden hacer colgarse a este método (si fueron definidas de forma que nunca se alcance un objeto None). ********************************** Recordando el capítulo de la recursión En el capítulo sobre recursión distinguimos entre el punto de vista de alto nivel que requiere un "acto de fe" y el punto de vista operacional de bajo nivel. - En términos de subdivisión mental de problemas, recomendamos en general el punto de vista de alto nivel, que es más abstracto. Pero si prefieres verlo desde abajo puedes utilizar las herramientas de debug "paso a paso" para ir avanzando a través de los niveles recursivos y examinar así cómo avanza print_lista_invertida a medida que se ejecuta, para comprender cómo funciona la recursión en este caso. **********************************

24.5) Listas infinitas

Nada impide que un nodo haga referencia a otro nodo anterior en la lista, o incluso a sí mismo. - Por ejemplo, esta figura muestra una lista que contiene dos nodos, uno de los cuales se refiere a sí mismo: Si llamamos a print_lista sobre esta lista, caerá en un loop infinito. Si llamamos a print_lista_invertida, caerá en una recursión infinita. - Esta clase de comportamientos hacen que trabajar con listas infinitas sea de por sí difícil, y sus resultados bastante impredecibles. Sin embargo, en algunos casos son útiles. - Por ejemplo, podemos representar un número como una lista de dígitos y usar un loop infinito para representar una fracción que se repite. De todas formas, es problemático que no podamos probar que print_lista y print_lista_invertida van a terminar. - Lo mejor que podemos hacer es hacer una afirmación hipotética como ésta: "Si la lista no contiene loops, entonces estos métodos terminarán." Este tipo de afirmaciones se conocen como precondiciones. - Las precondiciones imponen limitaciones a uno de los parámetros y describen el comportamiento del método si las mismas se cumplen. - Pronto veremos más ejemplos del uso de precondiciones.

24.6) Teorema fundamental de la ambigüedad

Una parte del código de print_lista_invertida debería habernos puesto en alerta: cabeza = lista cola = lista.next Tras la primer asignación, cabeza y cola tienen el mismo tipo y el mismo valor. ¿Por qué entonces creamos una nueva variable? La razón está en que ambas variables cumplen con roles distintos. - Pensamos en cabeza como una referencia a un nodo único, y en lista como la referencia al primer nodo de la lista. - Estos roles no son parte del programa; sólo están en la mente del programador, y son conceptuales. En general no podemos decir, sólo con mirar un programa, cuál es el rol que cumple una variable. - La ambigüedad puede ser útil, pero en ocasiones puede hacer que los programas sean difíciles de leer. - Usamos con frecuencia nombres de variables como nodo y lista para documentar cómo nos proponemos usar una variable y a veces creamos variables adicionales para reducir la ambigüedad. Podríamos haber escrito print_lista_invertida sin usar cabeza y cola, lo que nos da una versión más concisa pero tal vez más difícil de entender: def print_lista_invertida_version_concisa(lista): if lista is None: return print_lista_invertida_version_concisa(lista.next) print(lista, end=" ") Si miramos a los llamados a función de las dos líneas finales, debemos recordar que print_lista_invertida_version_concisa trata su argumento como una colección y print lo trata como un objeto único. El teorema fundamental de ambigüedad describe la ambigüedad que es inherente a una referencia a un nodo: - Una variable que se refiere a un nodo puede tratar al nodo como un objeto único o como el primero de una lista de nodos.

24.7) Modificando listas

Hay dos formas de modificar una lista enlazada. Obviamente podemos modificar el cargo de algún nodo, pero las operaciones más interesantes son las que agregan, eliminan o reordenan los nodos. Como ejemplo, escribamos un método que elimina el segundo nodo de la lista y retorna una referencia al nodo eliminado: def remover_segundo(lista): if lista is None: return primero = lista segundo = lista.next # Hacer que el primer nodo apunte al tercero primero.next = segundo.next # Separar el segundo nodo del resto de la lista segundo.next = None return segundo Una vez más, usamos variables temporales para hacer al código legible. Aquí lo vemos en funcionamiento: >>> print_lista(nodo1) 1 2 3 >>> quitado = remover_segundo(nodo1) >>> print_lista(quitado) 2 >>> print_lista(nodo1) 1 3 Este diagrama de estados muestra el efecto de la operación: Qué pasa si llamamos el método pasándole una lista de un solo elemento? Qué pasa si se le pasa la lista vacía como argumento? Hay una precondición para este método? - De ser así, corrige el método para manejar violaciones de la precondición de un modo razonable. - Respuestas: Si la lista tiene un solo elemento o ningún elemento, la versión actual se colgará porque intentará acceder a valores que no existen. - Caso de 1 elemento: fallará porque en tal caso el segundo elemento es None, y por lo tanto no se puede acceder a segundo.none - Caso de lista vacía: fallará porque ni siquiera existe segundo elemento - La precondición natural que resolvería el problema es: exigir que la lista tenga al menos dos elementos. - La respuesta en caso de que esta precondición no se cumpla: devolver None (como señal de que no se ha quitado ningún elemento). - Dicho todo lo anterior, el código corregido sería el siguiente: def remover_segundo(lista): if lista is None: return if lista.next is None: return primero = lista segundo = lista.next # Hacer que el primer nodo apunte al tercero primero.next = segundo.next # Separar el segundo nodo del resto de la lista segundo.next = None return segundo

24.8) Wrappers y Helpers

A menudo es útil dividir una lista de operaciones en dos métodos. - Por ejemplo, para imprimir una lista al revés en el formato convencional [3, 2, 1], podemos utilizar print_lista_invertida para imprimir 3, 2, 1 pero necesitamos un método aparte para imprimir los paréntesis rectos. Llamémosla print_lista_invertida_formateada: def print_lista_invertida_formateada(lista): print("[", end=" ") print_lista_invertida(lista) print("]") Una vez más, es bueno probar métodos como estos para ver si funcionan con casos especiales, como la lista vacía o la de un solo elemento. - Observación: lo hace bien. Cuando usamos este método, llamamos a print_lista_invertida_formateada directamente, y ésta se encarga de llamar a print_lista_invertida por nosotros. - En ese sentido, print_lista_invertida_formateada actúa como un wrapper (envoltorio), que usa a print_lista_invertida como helper (auxiliar).

24.9) La clase ListaEnlazada

Hay algunos problemas sutiles con la forma en que hemos implementado las listas. - Cambiando el orden habitual, propondremos primero la solución y luego explicaremos qué problema resuelve. Primero, crearemos una nueva clase que llamaremos ListaEnlazada. Sus atributos son un entero que contiene el tamaño de la lista y una referencia al primer nodo. - Los objetos ListaEnlazada sirven como manejadores (handlers) para manipular listas de objetos Nodo: class ListaEnlazada: def __init__(self): self.largo = 0 self.cabeza = None Una ventaja de la clase ListaEnlazada es que nos da un lugar natural para poner funciones envoltorio (wrapper) como print_lista_invertida_formateada, que podemos convertir en un método de ListaEnlazada: class ListaEnlazada: . . . def print_invertida(self): print("[", end=" ") if self.cabeza is not None: self.cabeza.print_invertida() print("]") class Nodo: . . . def print_invertida(self): if self.next is not None: cola = self.next cola.print_invertida() print(self.cargo, end=" ") Ahora en vez de tener un método print_lista_invertida_formateada y otro print_lista_invertida, sustituimos al primero por el print_invertida de ListaEnlazada (el método wrapper), y al segundo por el print_invertida de Nodo (el método helper). - Cuando el wrapper llama a self.cabeza.print_invertida(), está llamando al helper, porque self.cabeza es un objeto None. Otra ventaja de la clase ListaEnlazada es que facilita la adición o eliminación del primer elemento de la lista. - Por ejemplo, agregar_primero es un elemento para ListaEnlazada: recibe como parámetro un item que será el cargo y lo pone en el primer lugar de la lista. class ListaEnlazada: . . . def agregar_primero(self, cargo): nodo = Nodo(cargo) nodo.next = self.cabeza self.cabeza = nodo self.largo += 1 Como siempre, deberás verificar si el método que acabamos de implementar maneja bien los casos especiales. - Por ejemplo, ¿qué pasa si la lista está inicialmente vacía? - Respuesta: en ese caso el método funcionará bien, porque en la línea 1 se crea el nodo con el cargo que se ha recibido como parámetro, en la línea 2 se asigna como siguiente del nodo la cabeza de la lista, que siempre existe (será None si la lista es vacía, pero existe), en la línea 3 se define como nueva cabeza de la lista al nodo que habíamos creado en la línea 1 y en la línea 4 se incrementa (correctamente) el largo de la lista. Es decir que todo funcionaría bien.

24.10) Invariantes

Algunas listas están bien formadas, otras no. - Por ejemplo, si una lista contiene un loop, hará que varios de nuestros métodos se cuelguen, por lo cual podríamos poner como exigencia que las listas no tengan loops. - Otro requerimiento sería que el valor de largo en la ListaEnlazada debería mantenerse siempre igual a la cantidad de nodos en la lista. Requerimientos como éstos se llaman invariantes porque, al menos idealmente, deberían ser siempre verdaderos para toda objeto en todo momento. - Especificar invariantes para objetos es una práctica de programación útil y recomendable porque hace más fácil probar si un código es correcto, chequear la integridad de la estructura de datos y detectar errores. Una cosa que a veces confunde a propósito de los invariantes es que hay veces en que son violados. - Por ejemplo, en el medio de la ejecución de agregar_primero, una vez que hemos agregado el nodo pero antes de incrementar el largo, el invariante no se cumple. - Esta clase de violación es aceptable: de hecho, es a menudo imposible modificar un objeto sin violar un invariante al menos por un instante. - Normalmente, exigimos que todo método que viole un invariante lo restaure antes de retornar. Si hay un trozo importante del código a través del cual el invariante se mantiene violado, es importante poner comentarios para dejarlo bien claro, de forma que no se realicen operaciones que dependan del invariante.

24.11) Glosario

- referencia embebida, lista enlazada, nodo, cargo, precondición, teorema fundamental de ambigüedad, wrapper (envoltorio), helper (ayudador), invariante - enlace (link - una referencia embebida que se usa para enlazar un objeto con otro) - singleton (lista enlazada que tiene un solo nodo)

24.12) Ejercicios

1) Por convención, las listas se imprimen a menudo entre paréntesis rectos con comas entre los elementos, como en [1, 2, 3] - Modificar print_lista para que genere output con este formato. (hacerlo)