Estructuras de datos: Un entero puede ser muy útil si necesitamos un contador, una suma o un índice en un programa, pero generalmente también tenemos que tratar con datos que tienen muchas partes tales como una lista. Cuando la información de un programa está formada de partes, tenemos que considerar una estructura de datos adecuada. Las estructuras de datos tienen algunas características propias. Primero, pueden ser descompuestas en sus elementos componentes. Segundo, la forma de colocar los elementos es una característica de la estructura que afectará a cómo se accede a cada elemento. Tercero, la forma de colocar los elementos y la forma en la que se accede a ellos puede ser encapsulada. Consideremos un ejemplo de la vida real, como ser una biblioteca. Una biblioteca puede descomponerse en sus elementos, los libros. La colección de libros puede colocarse de varias formas: todos agrupados, en orden alfabético, por temas, etc. Obviamente la forma en que se ubican en la biblioteca particular a la que nos estamos refiriendo, no se deja que cada una se sirva sus libros. Si alguien quiere un libro, le da su petición al bibliotecario, quien hace la entrega de la lista de libros pertinentes. La estructura de datos biblioteca está compuesta por elementos (libros) colocados de forma particular. Por ejemplo, puede estar ordenada sobre la base del sistema decimal de Dewey. El acceso a un libro concreto requiere el conocimiento de la forma en que son situados los libros. El usuario de la biblioteca no tiene porqué conocer este método de acceso, porque la estructura ha sido encapsulada: el acceso de los usuarios a los libros se hace sólo a través del bibliotecario. Usaremos este mismo método para las estructuras de datos de nuestros programas. Una estructura de datos se definirá como • la forma lógica de colocar los elementos, combinados con • el conjunto de operaciones que necesitamos para acceder a los elementos. Así definimos estructura de datos como una colección de elementos (datos) cuya asignación se caracteriza por las operaciones de acceso usadas para almacenar y recuperar los elementos individuales. En el diseño de las estructuras de datos, debemos determinar la descripción lógica de los datos en un programa particular, elegir la representación de los datos y desarrollar las operaciones que encapsularán este almacenamiento. Consideremos las estructuras desde tres perspectivas o niveles diferentes de datos: • El nivel de aplicación (o usuario), una forma de modelar los datos de la vida real en un contexto específico. • El nivel abstracto (o lógico), una colección abstracta de elementos y sus conjuntos correspondientes de operaciones de acceso. • El nivel de implementación, una representación específica de la estructura y sus operaciones de acceso en un lenguaje de programación (tal como el Pascal). Veamos que es lo que significan estos puntos de vista diferentes en términos de nuestro ejemplo de la biblioteca. En el nivel de aplicación, el usuario de la biblioteca observa que entidades tales como La Biblioteca del Congreso de la Nación, la Biblioteca Nacional y otras. En el nivel abstracto, trata con preguntas sobre ¿qué?: ¿qué es una biblioteca?, ¿qué servicios puede ofrecer una biblioteca? La estructura puede ser vista de forma abstracta como una colección de libros, para los que se 1

especifican estas operaciones: • Comprobar un libro. • Consultar un libro. • Reservar un libro que está actualmente prestado. • Llevarse un libro en préstamo. • Pagar un suplemento por un libro vencido. • Pagar por un libro perdido. • Suspensiones por pérdida de libros. • Suspensiones por devoluciones fuera de término. • Otras. Como se organicen los libros en sus estanterías no es importante a nivel lógico, debido a que realmente los usuarios no tienen acceso a los libros. La visión abstracta del servicio biblioteca no se refiere a cómo el bibliotecario organiza realmente los libros en la biblioteca. Por ejemplo, la visión abstracta de consultar un libro puede ser: dar una solicitud del libro al bibliotecario y recibir una nota si el libro está prestado. A nivel de implementación, tratamos con respuestas sobre preguntas relativas al ¿cómo?: ¿Cómo están catalogados los libros?, ¿Cómo están organizados?, ¿Cómo procede el bibliotecario cuando el libro está en consulta? Por ejemplo, la información de implementación incluye el hecho de que los libros están catalogados de acuerdo con el sistema decimal de Dewy y colocados en cuatro niveles de apilamiento, con catorce filas de estanterías en cada nivel. El bibliotecario necesita tal conocimiento para poder localizar un libro. Esta información también incluye los detalles relativos a lo que sucede cuando se realiza cada operación. Por ejemplo, cuando un libro llega tarde, calcular las penalizaciones, comprobar la lista de reserva para ver si alguien está esperando dicho libro, actualizar los registros de la biblioteca para mostrar que el libro está disponible y colocar el libro de nuevo en su lugar. Por supuesto todo esto es desconocido por el usuario de la biblioteca. El objetivo de nuestro método de diseño es ocultar el nivel de implementación al usuario. Nivel de uso o Aplicación Nivel de uso o Aplicación Nivel de uso o Aplicación Si nos imaginamos a nosotros mismos en una parte y a otro programador en otra, ¿Cómo pueden comunicarse entre sí con la visión distinta y separada de los datos? Igualmente, ¿cómo hace el usuario de la biblioteca y el bibliotecario para relacionarse en la biblioteca? El usuario de la biblioteca y el bibliotecario se comunican a través de la abstracción de datos. La visión abstracta nos suministra la especificación de las operaciones de acceso sin decir cómo funcionan las operaciones, nos dice el qué, pero no el cómo. La única comunicación del usuario del nivel de implementación se realiza en términos de las especificaciones de entrada y suposiciones permitidas, las precondiciones de las rutinas de acceso. La única salida del nivel de implementación hacia el usuario es la estructura de datos transformada y descripta por las especificaciones de salida o postcondiciones de la rutina. La visión abstracta encapsula la estructura de datos, pero suministra ventanas a través de la especificación de las operaciones de acceso. Cuando se escribe un programa, como una tarea de clase, normalmente se trata de datos a los tres niveles. Sin embargo, en una situación de trabajo puede que no sea así. Algunas veces puede tener que programarse una aplicación que utilice una estructura de datos implementada por otro programador. Otras veces se puede tener que desarrollar utilidades que serán llamadas por otros programas.

2

Los lenguajes de programación usualmente suministran algunas estructuras de datos que se constituyen en el lenguaje: por ejemplo, Pascal suministra registros, arreglos de distintas dimensiones, conjuntos y punteros. Listas enlazadas: Introducción: Todos sabemos intuitivamente lo que es una lista debido a que la utilizamos a diario: una lista de alimentos a comprar en un supermercado, una lista de amigos que vamos a invitar cuando ofrecemos una fiesta, una lista de elementos que necesitamos para pintar y alfombrar el cuarto de una casa, etc. En los programas de computadoras, las listas son unas estructuras de datos muy útiles y frecuentes. Desde un punto de vista de programación, una lista es una colección de elementos homogéneos relacionados linealmente entre sí. Esto significa que cada elemento de la lista excepto el primero tiene un único predecesor y cada elemento excepto el último tiene un único sucesor en la lista propiamente dicha. El orden de los elementos en la lista afecta a su función de acceso; por ejemplo, si la lista esta ordenada ascendentemente, el sucesor de cualquier elemento será mayor o igual que este elemento. Las listas pueden representarse gráficamente de la siguiente manera: Esta no es la primera vez que se utiliza el concepto de lista, ya que en el primer curso de programación se han tratado a los arreglos como una lista de elementos. De hecho es fácil confundir los términos lista y array. Pero hasta aquí hemos hablado sobre listas como tipo abstracto de datos, mientras que un arreglo no es más que una forma de implementar una lista de datos. Para saber diferenciarlos, el usuario de una lista, a nivel lógico, conoce qué información ha de almacenarse para cada elemento, el tamaño potencial de la lista y el orden de sus elementos. Lo anteriormente escrito no es más que el nivel de aplicación. Dicho nivel no necesita saber cómo ha de representarse la lista en la memoria física de la computadora, ya que la visión de la implementación está encapsulada por el tipo abstracto de dato lista. Por supuesto, para utilizar la lista, el usuario debe tener alguna forma de llegar a los elementos almacenados en ella. Las ventanas de la implementación de la lista se suministran mediante un paquete de operaciones que se realizan con la lista. Hay muchas operaciones diferentes que podríamos dar para una lista; para diferentes aplicaciones podemos imaginar todas las cosas que podemos hacer con una lista de elementos. Hay varias formas de presentar las operaciones que se pueden definir para trabajar con listas, pero las dos que sobresalen a estas son las que me permiten operar en forma totalmente abstracta (con un elemento corriente), y la otra no lo es completamente (sin elemento corriente). El elemento corriente en una estructura de datos se utiliza en la definición de la estructura a implementar y a aplicar, como un elemento que apunta a la posición de la estructura donde nos hallamos ubicados. De esta manera, adoptar este tipo de definición posee una ventaja, y es utilizar de la estructura a un nivel completamente abstracto, sin necesidad de tocar la implementación en la invocación a las primitivas que realizan determinadas tareas. En la mayoría de las aplicaciones de las listas simplemente enlazadas, se las utiliza de forma tal, que sus elementos (nodos) se encuentren ordenados por una o varias claves definidas por el nivel de aplicación. Las operaciones que utilizaremos para trabajar con listas simplemente enlazadas son:

3

• Crear lista • Insertar antes • Insertar después • Mover corriente • Modificar corriente • Eliminar corriente • Obtener corriente • Lista vacía • Vaciar lista A nivel usuario, estas son operaciones lógicas sobre una lista. A un nivel más bajo, estas operaciones se desarrollarán como primitivas, que manipulan el medio de almacenamiento de datos para mantener los elementos de la lista. Representación de las listas: La representación de una lista puede ser secuencial o enlazada. En una lista secuencial, la ubicación física de los elementos coincide con su orden lógico. Por ejemplo, considerando una lista de alimentos a comprar en un supermercado: (leche, galletitas, dulce de leche, pan, manteca, una botella de vino blanco, una botella de vino tinto, champagne, carne, frutas, verduras) Una representación secuencial de la lista anterior sería: • Leche • Galletitas • Dulce de leche • Pan • Manteca • Botella de vino blanco • Botella de vino tinto • Champagne • Carne • Frutas • Verduras El primer elemento, leche, está en la primera posición, el segundo elemento, galletitas, se encuentra en la segunda posición, y así sucesivamente. Para cualquier elemento de la lista, la identidad del sucesor esta definida implícitamente: es el elemento que está en la posición física siguiente. Ya estamos familiarizados con las representaciones secuenciales de listas por la escritura de programas en las que los elementos se almacenan uno después de otro en un array. Entonces definimos lista secuencial a una representación de lista en la que el sucesor de cada elemento de la lista esta implícito por la posición del elemento: los datos se colocan en posiciones secuenciales en la estructura. En una lista enlazada, el orden lógico de los elementos no es necesariamente equivalente a su ubicación física; los elementos de la lista del ejemplo anterior, (leche, galletitas, dulce de leche, pan, manteca, una botella de vino blanco, una botella de vino tinto, 4

champagne, carne, frutas, verduras) pueden estar ordenados físicamente como • Botella de vino blanco • Manteca • Frutas • Dulce de leche • Galletitas • Champagne • Botella de vino tinto • Verduras • Carne • Leche • Pan El problema ahora es cómo sabemos cuál es el primer elemento y en qué orden estén almacenados los restantes. En una lista enlazada la identidad del siguiente elemento, el enlace, debe definirse explícitamente. Definimos lista enlazada a la representación de lista en la que el orden de los elementos está determinado por un campo enlace explícito en cada elemento, en vez de por su posición secuencial. ¿Por qué usamos listas enlazadas? Utilizamos listas enlazadas para evitar movimientos de datos en la estructura, como los corrimientos en los arrays. Con una representación enlazada, los elementos existentes pueden permanecer como y donde están mientras que se añaden o suprimen otros. Esto significa que no es necesario tener almacenados los datos en el orden estipulado, ya que el enlace con el siguiente es el encargado de mantener el orden preestablecido. Visión abstracta de una lista enlazada: Una lista enlazada puede describirse como una colección de elementos, o nodos, cada uno conteniendo datos y un enlace, o puntero, al siguiente nodo de la lista. Un puntero externo llamado cabeza de la lista (uno que no está conectado a cualquier nodo) nos dice dónde comienza la lista. No se puede acceder a los nodos de una lista enlazada directamente, esto significa que no podemos obtener directamente un elemento de la lista, a menos que el corriente este parado justamente en él. Si el corriente no es el elemento buscado, debemos alcanzar el elemento deseado mediante la cabeza de la lista y, mediante el paso secuencial de los nodos, llegaríamos a la componente citada. Este paso secuencial se logra mediante el movimiento del elemento corriente de la lista. Dicho movimiento se logra conectándonos con la posición (puntero) siguiente del nodo en el cual estamos parados. Anatomía de un nodo: Cada nodo de una lista enlazada debe contener al menos dos campos. El primero es el campo donde almacenaremos el dato o información del usuario. A este campo suele llamárselo Info. El segundo campo contiene el puntero o enlace al siguiente nodo de la lista. Nos referiremos a este campo como Siguiente o Próximo o Enlace o Conexión. Esta parte del elemento contiene los datos que son importantes para la implementación del programador, pero no la visión del usuario de sus datos. Dibujaremos un nodo simple de 5

la siguiente forma: En el campo info puede almacenarse un entero, un real, un enumerado, un array, un conjunto, un record, etc. Si trabajamos con listas ordenadas y como info utilizamos un record, los nodos se colocarán de acuerdo con una o varias claves dispuestas por el usuario en relación con los campos de la variable compuesta, teniendo en cuenta que deberán definirse la prioridad de cada clave, en caso de haber más de una. Algunas notaciones sobre listas: Hasta que empecemos a estudiar una implementación particular de lista enlazada, necesitamos indicar alguna forma de indicar las partes de un nodo. Esta notación se utiliza sólo para describir algoritmos, no tiene nada que ver con el código de un lenguaje en particular. ¿Qué ocurre si no hay más nodos que enlazar en la lista?, esto significa: ¿qué pasaría si el corriente es el último? El campo siguiente del último nodo de la lista debe contener la información necesaria para indicar que el siguiente del nodo corriente es, algún valor que me indique que no hay más nodos que apuntar, que hemos alcanzado el final de la lista. Este valor, el cual normalmente se llama Nulo o posición nula (Nil en Pascal o Null en C), nos dice que se ha alcanzado el final de la lista. Cuando la cabeza de la lista apunta a la posición nula, decimos que la lista se encuentra vacía, pues no apunta a ninguna dirección, por lo tanto no contiene elementos. Gráficamente, a la posición nula la simbolizamos de dos maneras a saber: Ambas representaciones indican la posición nula en un nodo. El nivel de implementación: Una forma de implementar una lista enlazada es mediante un array de registros. Podemos dibujar cada nodo de una lista como un registro con dos campos: Info y Siguiente. Estos registros pueden almacenarse en cualquier orden físico en un array de registros y enlazarse juntos mediante sus campos Siguiente. Este esquema contrasta con una representación de lista secuencial, en donde el sucesor de cada elemento de la lista sería el que ocupe la posición siguiente del arreglo. De esta manera, el vector queda con los nodos almacenados en posiciones contiguas. Esta forma de implementación, si bien no es la más óptima, es aplicable a cualquier algoritmo que necesite de este tipo de estructura de datos para procesarse. Para la representación secuencial, no es necesario utilizar un campo siguiente en el nodo, ya que, al ser de almacenamiento físico continuo, basta con realizar un corrimiento en el vector, cada vez que insertamos o retiramos un elemento. (Se incluye la implementación de este tipo de lista en el apéndice de esta parte utilizando el lenguaje de programación C). En la representación enlazada, el campo enlace de cada nodo apunta al elemento siguiente de la lista. ¿Qué podemos almacenar en el campo siguiente para informarnos cuál es el nodo que va a continuación? Si trabajamos con arreglos, basta con recordar cómo accedemos a sus elementos: por medio de un índice. Ésta es una forma de implementar una lista enlazada, pero no es la única. Un problema con esta representación es que nos obliga a declarar un array lo suficientemente grande como para poder almacenar el máximo número posible de elementos de la lista. En la declaración de un array, la especificación del rango índice es un tipo; por lo tanto no puede variar. En otras palabras, la variable es estática; el compilador debe 6

saber cuánto espacio de memoria asignar al array permaneciendo este espacio durante toda la ejecución del bloque que lo tenga definido. Otra manera de definir una lista es mediante la implementación estática con cursores. Éstos permiten utilizar los nodos de los vectores de manera que no tengan que realizarse los corrimientos pertinentes, ya que un campo disponible en la definición del tipo lista nos permite utilizar aquellas posiciones del array que no fueron ocupadas o en su defecto quedaron sin elementos debido a una eliminación (en el apéndice de esta sección se incluye la declaración e implementación de listas simplemente enlazadas con cursores en Pascal). Sería ideal no necesiar asignar espacio a un elemento de una lista, hasta el momento en que sea necesario añadirlo. Si, mediante alguna operación podemos obtener el espacio de memoria necesario para insertar un nodo en la lista, podrían crearse, en tiempo de ejecución, las variables conforme se requieran. Como la mayoría de los lenguajes de alto nivel, Pascal y C, tienen un mecanismo que permiten crear variables dinámicas. Esto es, podemos definir un tipo de nodo en tiempo de compilación, pero no realmente instanciarlo (crear cualquier variable de ese tipo) hasta el tiempo de ejecución. De esta manera, nos referiremos a este proceso como asignación dinámica de memoria, creando variables (o destruyéndolas) en tiempo de ejecución. La implicación de esta idea en la confección de esta estructura es obvia. Si podemos obtener espacio para nuevos nodos a medida que se necesitan, no será útil declarar un array lo suficientemente grande como para almacenar el máximo número posible de elementos en la lista. Así, no necesitaremos saber de antemano que tan grande va a ser la lista. La única limitación es la cantidad de memoria disponible en la computadora. Definición dinámica de listas simplemente enlazadas utilizando un nodo corriente: {La abreviatura ls, indica lista_simple, y la utilizamos para sintetizar su escritura.} type tipo_dato = ; tipo_movimiento_ls = (primero, siguiente); tipo_ptr_nodo_ls = ^tipo_nodo_ls; tipo_nodo_ls = record info : tipo_dato; enlace : tipo_ptr_nodo_ls end; {tipo_nodo_ls} tipo_lista_simple = record cabeza, corriente : tipo_ptr_nodo_ls end;

7

Una lista simplemente enlazada puede representarse gráficamente de la siguiente manera: Las operaciones que nos permiten manipular este tipo de dato (primitivas) son: • Crear lista. • Insertar antes del corriente. • Insertar después del corriente. • Mover corriente. • Modificar corriente. • Eliminar corriente. • Obtener corriente. • Lista vacía. • Vaciar lista. La definición completa de este tipo de dato abstracto se reúne en una unidad de biblioteca. unit listas_simples; interface {La abreviatura ls, indica lista_simple, y la utilizamos para sintetizar su escritura.} type tipo_dato = ; tipo_movimiento_ls = (primero, siguiente); tipo_ptr_nodo_ls = ^tipo_nodo_ls; tipo_nodo_ls = record info : tipo_dato; enlace : tipo_ptr_nodo_ls end; {tipo_nodo_ls} tipo_lista_simple = record cabeza, corriente : tipo_ptr_nodo_ls end; {tlista_enlazada} {A continuación se presenta el listado de primitivas de la estructura de dato tipo_lista_simple } procedure ls_crear ( var ls : tipo_lista_simple ); {Pre: La lista ls no existe aún.

8

Post: La lista ls está creada y se encuentra vacía .} function ls_vacia ( ls : tipo_lista_simple ) : boolean; {Pre: La lista ls fue creada. Post: Devuelve true si la lista ls no posee elementos, Sino false.} procedure ls_insertar_antes ( var ls : tipo_lista_simple ; elemento : tipo_dato ; var error : boolean ); {Pre: La lista ls fue creada. Elemento es el dato a insertar en la lista ls, inmediatamente antes del corriente. Post: Si hubo lugar para insertar el elemento en la lista ls antes del corriente, entonces la operación tuvo éxito, error es false y el dato recién insertado es el nuevo corriente de la lista ls. sino error es true, pues no se pudo realizar la operación.} procedure ls_insertar_despues ( var ls : tipo_lista_simple ; elemento : tipo_dato ; var error : boolean ); {Pre: La lista ls fue creada. Elemento es el dato a insertar en la lista ls, inmediatamente después del corriente. Post: Si hubo lugar para insertar el elemento en la lista ls después del corriente,

9

entonces la operación tuvo éxito, error es false y el dato recién insertado es el nuevo corriente de la lista ls. sino error es true, pues no se pudo realizar la operación.} procedure ls_mover_corriente ( var ls : tipo_lista_simple ; movimiento : tipo_movimiento_ls ; var error : boolean ); {Pre: La lista ls fue creada y no está vacía. Movimiento indica hacia dónde queremos movernos en la la lista ls: primero o siguiente. Post: Si nos queremos ubicar en el primer elemento de ls y la lista no está vacía, entonces error es false y el nuevo corriente es el primer elemento de la lista ls sino error es true, pues ls no contiene elementos. Si nos queremos ubicar en el siguiente elemento del corriente de ls, y éste no es el último, entonces error es false y el nuevo corriente es el siguiente elemento de la lista ls, sino error es true, pues el corriente era el último elemento.} procedure ls_obtener_corriente ( ls : tipo_lista_simple ; var elemento : tipo_dato ); {Pre: La lista ls fue creada y no está vacía. Post: En el parámetro Elemento se encuentra la información

10

del elemento corriente de la lista ls.} procedure ls_modificar_corriente ( var ls : tipo_lista_simple ; elemento : tipo_dato ); {Pre: La lista ls fue creada y no está vacía. Elemento contiene la nueva información para modificar el corriente de la lista ls. Post: El elemento corriente contiene ahora la nueva información suministrada. } procedure ls_eliminar_corriente (var ls : tipo_lista_simple); {Pre: La lista ls fue creada y no está vacía. Post: El nodo corriente que se deseaba eliminar ya no forma parte de la lista ls. Si la lista ls no quedó vacía, entonces si el elemento eliminado no era el último, entonces el nuevo corriente es el siguiente sino el nuevo corriente es el primero de la lista ls.} procedure ls_vaciar ( var ls : tipo_lista_simple ); {Pre: La lista ls fue creada. Post: La lista ls no posee elementos.} implementation procedure ls_crear ( var ls : tipo_lista_simple ); begin with ls do begin cabeza := nil;

11

corriente := nil end {with} end; {ls_crear} function ls_vacia ( ls : tipo_lista_simple ) : boolean; begin ls_vacia := (ls.cabeza = nil) end; {ls_vacia} procedure ls_insertar_antes ( var ls : tipo_lista_simple ; elemento : tipo_dato ; var error : boolean ); var nuevo_nodo, ptr_auxiliar : tipo_ptr_nodo_ls; begin error:= Maxavail < sizeof(tipo_nodo_ls); if (not (error)) then begin new(nuevo_nodo); {Preparo el nodo para insertarlo en la lista ls} with nuevo_nodo^ do begin info := elemento; {cargo el dato} enlace := nil {así queda listo} end; {with} {El nodo está listo para ser insertado en ls} {Ahora busco la posición donde corresponde colocar el nuevo nodo}

12

with ls do {Para que sea más cómodo} begin if (cabeza <> corriente) then begin {El nodo corriente no se encuentra en la primera posición. Obviamente la lista ls no está vacía.} {Primeramente busco el nodo anterior al corriente. Esto lo hago con un puntero auxiliar} ptr_auxiliar := cabeza; {Comienzo a buscar el anterior al corriente} while (ptr_auxiliar^.enlace <> corriente) do ptr_auxiliar := ptr_auxiliar^.enlace; {Encontré el nodo anterior al corriente} {Ahora procedo a conectar el nodo entre el corriente y su anterior, teniendo en cuenta de no dejar referencias colgadas, ya que si esto ocurre, la lista pierde su estructura} nuevo_nodo^.enlace := corriente; ptr_auxiliar^.enlace := nuevo_nodo; end {then} else begin if (cabeza <> nil) then nuevo_nodo^.enlace := cabeza; cabeza := nuevo_nodo end {else} corriente := nuevo_nodo {nodo insertado} end {with} {pues no hay lugar para el campo info del nodo a insertar, y estaría dejando una referencia colgada sino libero el nodo que se creo al principio del subprograma} end; {ls_insertar_antes} procedure ls_insertar_despues ( var ls : tipo_lista_simple ;

13

elemento : tipo_dato ; var error : boolean ); var nuevo_nodo : tipo_ptr_nodo_ls; begin error:= Maxavail < sizeof(tipo_nodo_ls); if (not (error)) then begin new(nuevo_nodo); {preparo el nuevo nodo para insertarlo en la lista ls} with nuevo_nodo^ do begin info := elemento; enlace := nil end; {with} {Ahora el nuevo nodo esta listo para ser insertado en la lista ls inmediatamente después del corriente} with ls do begin if (cabeza = nil) {la lista ls está vacía} then cabeza := nuevo_nodo {el nuevo es el primero} else begin {la lista no está vacía} nuevo_nodo^.enlace := corriente^.enlace; corriente^.enlace := nuevo_nodo end; {else} corriente := nuevo_nodo end {with} end {then}

14

{pues no hay lugar para el elemento a insertar en el campo info de la lista, y así evito dejar referencias colgadas.} end{then} end; {ls_insertar_despues} procedure ls_mover_corriente ( var ls : tipo_lista_simple ; movimiento : tipo_movimiento ; var error : boolean ); begin error := false; with ls do case (movimiento) of primero : if (cabeza <> nil) then corriente := cabeza else error := true; siguiente : if (corriente^.enlace <> nil) then corriente := corriente^.enlace else error := true end {case} end; {ls_mover_corriente} procedure ls_obtener_corriente ( ls : tipo_lista_simple ; var elemento : tipo_dato ); begin elemento := ls.corriente^.info end; {ls_obtener_corriente} procedure ls_modificar_corriente ( var ls : tipo_lista_simple ; elemento : tipo_dato ); begin 15

ls.corriente^.info := elemento end; {ls_modificar_corriente} procedure ls_eliminar_corriente (var ls : tipo_lista_simple); var ptr_aux, ptr_anterior : tipo_ptr_nodo_ls; begin with ls do begin ptr_aux := corriente; if (cabeza = corriente) then cabeza := corriente^.enlace else begin ptr_anterior := cabeza; {Comienzo a buscar el anteior para conectarlo con el nodo siguiente del que quiero eliminar} while (ptr_anterior^.enlace <> corriente) do ptr_anterior := ptr_anterior^.enlace; {Nodo anterior encontrado} {Ahora hago los enlaces entre los nodos que estaban antes y después del que quiero eliminar y no quedan referencias colgadas} ptr_anterior^.enlace := corriente^.enlace; if (cabeza = nil) {la lista ls esta vacía} then corriente := nil else if (corriente^.enlace <> nil) then corriente := corriente^.enlace else corriente := cabeza end {else} end; {with} 16

{Acá se libera el nodo auxiliar completamente de la memoria} ptr_aux^.enlace := nil; {para desvincular el nodo completamente } dispose(ptr_aux) {libero la memoria ocupada por el elemento que se queria eliminar de la lista} end; {ls_eliminar_corriente} procedure ls_vaciar ( var ls : tipo_lista_simple ); var ptr_aux : tipo_ptr_nodo_ls; begin with ls do begin while (cabeza <> nil) do begin ptr_aux := cabeza; cabeza := cabeza^.enlace; ptr_aux^.enlace := nil; dispose(ptr_aux) end; {while} {Ahora la lista esta vacia.} {Dejo los nodos indicadores liberados de apuntar a posiciones de memoria que ya no son válidas} cabeza := nil; corriente := nil end {with} end; {ls_vaciar} {período de inicialización} end. El nivel de aplicación:

17

Las listas se utilizan en todos los tipos de aplicaciones de las computadoras. Son raros los programas que no utilizan una lista de datos de algún tipo. Un aplicación de las listas enlazadas se efectúa en un editor de línea, con cada nodo conteniendo un número de línea, un número de texto y un puntero al siguiente nodo de línea Info. Ya que no podemos predecir cuantas líneas se necesitan, esta aplicación es ideal para trabajar con el tipo de dato dinámico. También podemos aplicar listas simples como representación de cadenas de caracteres más largos que el tipo string (aunque Pascal ya tiene predefinido el tipo pchar). El tipo cadena puede declararse como un registro que contiene un contador en el cual se almacena la longitud de dicha cadena (o también podemos crear una primitiva que cuente sus caracteres). Cabe señalar que a diferencia con el tipo string de Pascal, aquí hay similitud entre longitud física y lógica. Una implementación eficiente es desarrollar tipos de datos numéricos más grandes que el longint. De esta manera el uso de una lista enlazada nos permite trabajar dentro de un rango numérico mucho más amplio que los predefinidos por los lenguajes. Otra aplicación matemática es la manipulación de polinomios, donde cada nodo de la lista guardara el coeficiente y la potencia a la cual se eleva la variable dependiente que lo acompaña. No necesariamente debemos tener polinomios cuyo cuerpo sea el de los números reales o enteros: también existen los números complejos. Si definimos coeficientes complejos en los polinomios, y el lenguaje en el que estamos trabajando no nos provee este tipo de dato (como lo es el caso de Pascal, pero no del lenguaje C), deberemos definirlo en forma abstracta. Si ocurre esto último, estamos trabajando con dos niveles de abstracción, ya que la manipulación de las operaciones entre complejos, como sabemos, están definidas en las primitivas de dicho tipo de dato. Si en cambio queremos utilizar los coeficientes de tipo entero largo, según la primera aplicación matemática, también tendremos dos niveles de abstracción, pero cada nodo posee ahora una lista enlazada, es decir, que tendremos tantas listas representando a los coeficientes del polinomio, como términos tenga el polinomio (cantidad de nodos). A esta forma de tratar listas de listas las llamamos listas encadenadas. Una representación gráfica de listas encadenadas es la siguiente: Listas circulares enlazadas: En el uso de listas lineales simplemente enlazadas se presenta un problema: en las situaciones en que es necesario alcanzar un nodo que preceda al corriente, debemos recorrer la lista NUEVAMENTE comenzando por la cabeza. Sin embargo, podemos cambiar algo en la implementación de la lista lineal, haciendo que el puntero del campo enlace del ultimo nodo apunte a la cabeza de la lista, en vez de contener la posición nula. Esto lo representamos gráficamente de la siguiente manera: Ahora nuestra lista, es una lista enlazada circular en vez de una lista lineal simplemente enlazada. En ella podemos colocar la cabeza de la lista como nodo de acceso en cualquier posición de la lista, y aún así acceder a todos los nodos. De hecho, una verdadera lista circular no tiene primero o último nodo, es simplemente un anillo de elementos enlazados entre sí. En el apunte tomaremos como convención que la cabeza de la lista circular apuntará al primer nodo de la lista. Por consiguiente, para ingresar a la lista, lo haremos a través del primer nodo. La ventaja de utilizar listas circulares, es que mediante un solo puntero externo podemos alcanzar ambos extremos de la lista. 18

¿Cómo definimos una lista circular? A nivel declaración de nodos, es la misma que para listas simplemente enlazadas: {La abreviatura lc, indica lista_circular, utilizándose para sintetizar su escritura.} type tipo_dato = ; tipo_movimiento_lc = (primero, siguiente); tipo_ptr_nodo_lc = ^tipo_nodo_lc; tipo_nodo_lc = record info : tipo_dato; enlace : tipo_ptr_nodo_lc end; {tipo_nodo_lc} tipo_lista_circular = record cabeza, corriente : tipo_ptr_nodo_lc end; {tlista_circular} Las primitivas que nos permiten operar en forma abstracta con listas circulares, también son las mismas que para listas simplemente enlazadas: • Crear lista. • Insertar antes del corriente. • Insertar después del corriente. • Mover corriente. • Modificar corriente. • Eliminar corriente. • Obtener corriente. • Lista vacía. • Vaciar lista. Cabe señalar una diferencia a nivel de implementación entre los dos tipos de lista vistos hasta ahora. Éste se ve claramente en la inserción y borrado de nodos, porque el último nodo ya no está definido, y deberá colocársele la dirección de la cabeza en el campo enlace. La definición completa de este tipo de dato deberá programarse en una unidad de biblioteca, guardando la declaración del tipo lista circular junto con las primitivas: unit lista_circular;

19

interface {La abreviatura lc, indica lista_circular, utilizándose para sintetizar su escritura.} type tipo_dato = ; tipo_movimiento_lc = (primero, siguiente); tipo_ptr_nodo_lc = ^tipo_nodo_lc; tipo_nodo_lc = record info : tipo_dato; enlace : tipo_ptr_nodo_lc end; {tipo_nodo_lc} tipo_lista_circular = record cabeza, corriente : tipo_ptr_nodo_lc end; {tlista_circular} {A continuación se presenta el listado de primitivas de la estructura de dato tipo_lista_circular } procedure lc_crear ( var lc : tipo_lista_circular ); {Pre: La lista lc no existe aún. Post: La lista ls está creada y se encuentra vacía.} function lc_vacia ( lc : tipo_lista_circular ) : boolean; {Pre: La lista lc fue creada. Post: Si la lista lc no contiene elementos Entonces lc_vacia devuelve true Sino lc_vacia devuelve false.} procedure lc_insertar_antes ( var lc : tipo_lista_circular ; elemento : tipo_dato ; var error : boolean );

20

{Pre: La lista lc fue creada. Elemento es el dato a insertar en la lista lc, inmediatamente antes del corriente. Post: Si hubo lugar para insertar el elemento en la lista lc antes del corriente, entonces la operación tuvo éxito, error es false y el dato recién insertado es el nuevo corriente de la lista lc. sino error es true, pues no se pudo realizar la operación.} procedure lc_insertar_despues ( var lc : tipo_lista_circular ; elemento : tipo_dato ; var error : boolean ); {Pre: La lista lc fue creada. Elemento es el dato a insertar en la lista lc, inmediatamente después del corriente. Post: Si hubo lugar para insertar el elemento en la lista lc después del corriente, entonces la operación tuvo éxito, error es false y el dato recién insertado es el nuevo corriente de la lista lc. sino error es true, pues no se pudo realizar la operación.} procedure lc_mover_corriente ( var lc : tipo_lista_circular ; movimiento : tipo_movimiento_lc ; var error : boolean );

21

{Pre: La lista lc fue creada y no está vacía. Movimiento indica hacia dónde queremos movernos en la la lista lc: primero o siguiente. Post: Si nos queremos ubicar en el primer elemento de lc Entonces el nuevo corriente es el primer elemento de la lista lc Si nos queremos ubicar en el siguiente elemento del corriente de lc, y éste no es el último, entonces el nuevo corriente es el siguiente elemento de lc.} procedure lc_obtener_corriente ( lc : tipo_lista_circular ; var elemento : tipo_dato ); {Pre: La lista lc fue creada y no está vacía. Post: En el parámetro Elemento se encuentra la información del elemento corriente de la lista lc.} procedure lc_modificar_corriente ( var lc : tipo_lista_circular ; elemento : tipo_dato ); {Pre: La lista lc fue creada y no está vacía. Elemento contiene la nueva información para modificar el corriente de la lista lc. Post: El elemento corriente contiene ahora la nueva información suministrada. } procedure lc_eliminar_corriente (var lc : tipo_lista_circular ); {Pre: La lista lc fue creada y no está vacía. Post: El nodo corriente que se deseaba eliminar ya no forma parte de la lista lc. Si la lista lc no quedó vacía, entonces si el elemento eliminado no era el último,

22

entonces el nuevo corriente es el siguiente sino el nuevo corriente es el primero de la lista lc.} procedure lc_vaciar ( var lc : tipo_lista_circular ); {Pre: La lista lc fue creada. Post: La lista lc no posee elementos.} Implementation procedure lc_crear ( var lc : tipo_lista_circular ); begin with lc do begin cabeza:= nil; corriente:= nil end {with} end; {lc_crear} function lc_vacia ( lc : tipo_lista_circular ) : boolean; begin lc_vacia:= (lc.cabeza = nil) end;{lc_vacia} procedure lc_insertar_antes ( var lc : tipo_lista_circular ; elemento : tipo_dato ; var error : boolean ); var nuevo_nodo : tipo_ptr_nodo_lc; begin error:= Maxavail < sizeof(tipo_nodo_lc); if (not error)

23

then begin {hay lugar en la memoria para insertar un nuevo nodo en la lista lc} new(nuevo_nodo); nuevo_nodo^.info:= elemento; nuevo_nodo^.proximo:= nil; if (lc.cabeza = nil) then begin lc.cabeza:= nuevo_nodo; lc.cabeza^.proximo:= nuevo_nodo end {then} else begin nuevo_nodo^.proximo:= lc.corriente; nodo_aux:= lc.cabeza; while (nodo_aux^.proximo <> lc.corriente) do nodo_aux:= nodo_aux^.proximo; if (lc.cabeza = lc.corriente) then {es el primer elemento de la lista lc} lc.cabeza:= nuevo_nodo else {Busco el nodo anterior al corriente para realizar la conexión} nodo_aux^.proximo:= nuevo_nodo; end; {else} lc.corriente:= nuevo_nodo end {then} end {then} end; {lc_insertar_antes}

24

procedure lc_insertar_despues ( var lc : tipo_lista_circular ; elemento : tipo_dato ; var error : boolean ); var nuevo_nodo : tipo_ptr_nodo_lc; begin error:= Maxavail < sizeof(tipo_nodo_lc); if (not error) then begin new(nuevo_nodo); nuevo_nodo^.info:= elemento; nuevo_nodo^.proximo:= nil; if ( lc.cabeza = nil) then begin {la lista lc está vacía} lc.cabeza:= nuevo_nodo; lc.cabeza^.proximo:= nuevo_nodo end {then} else begin {la lista lc tiene al menos un elemento} nuevo_nodo^.proximo:= lc.corriente^.proximo; lc.corriente^.proximo:= nuevo_nodo end {else} lc.corriente:= nuevo_nodo end {then} end; {lc_insertar_despues} procedure lc_mover_corriente ( var lc : tipo_lista_circular ; movimiento : tipo_movimiento_lc ; var error : boolean );

25

begin case (movimiento) of primero : lc.corriente:= lc.cabeza; siguiente : lc.corriente:= lc.corriente^.proximo end {case} end; {lc_mover_corriente} procedure lc_obtener_corriente ( lc : tipo_lista_circular ; var elemento : tipo_dato ); begin elemento:= lc.corriente^.info end; {lc_obtener_corriente} procedure lc_modificar_corriente ( var lc : tipo_lista_circular ; elemento : tipo_dato ); begin lc.corriente^.info:= elemento end; {lc_modificar_corriente} procedure lc_eliminar_corriente (var lc : tipo_lista_circular ); var nodo_anterior, {lo utilizo para buscar el nodo anterior al corriente y poder así realizar la conexión de los nodos de la lista lc} nodo_aux : tipo_ptr_nodo_lc; {en nodo_aux elimino el corriente} begin nodo_aux:= lc.corriente; {Busco el nodo anterior al que quiero eliminar para realizar la conexión, y así no dejar referencias colgadas} nodo_anterior:= lc.cabeza; while (nodo_anterior.proximo <> lc.corriente) do

26

nodo_anterior:= nodo_anterior^.proximo; {Anterior al corriente encontrado} if(lc.cabeza = lc.corriente) then { quiero eliminar el primer elemento de la lista} if (lc.cabeza^.proximo = lc.corriente){lc tiene un elemento} then lc.cabeza:= nil {lc quedará vacía} else begin {hay más de un elemento en la lista lc} lc.cabeza:= lc.corriente^.proximo; nodo_anterior^.proximo:= lc.corriente^.proximo end {else} else begin {eliminaré un elemento entre el segundo y el último} nodo_anterior^.proximo:= lc.corriente^.proximo; end {else} {A continuación procederé a actualizar el puntero del elemento corriente de la lista, teniendo en cuenta que lc puede estar vacía, o que, en su defecto, haya eliminado el último elemento, con lo que no debo apuntar al siguiente, sino al primero.} if(lc.cabeza = nil) then lc.corriente:= nil else if(lc.corriente^.proximo <> nil) then lc.corriente:= lc.corriente^.proximo {No era el último} else lc.corriente:= lc.cabeza; {Como era el ultimo, y lc no queda vacía, entonces hago que apunte al primer elemento según la postcondicion de la primitiva} {Voy a liberar la memoria dinámica correspondiente al elemento que quería eliminar. Este nodo esta identificado como nodo_aux} with nodo_aux do begin {Antes de liberar todo, debo prevenirme de borrar los posibles} 27

proximo:= nil;{punteros que contengan los campos de su nodo, para} dispose(info) {así evitar tener referencias colgadas} end; {with} dispose(nodo_aux) {Ahora sí libero la memoria disponible} end; {lc_eliminar_corriente} procedure lc_vaciar ( var lc : tipo_lista_circular ); var ultimo_nodo nodo_aux : tipo_ptr_nodo_lc; begin {Como primer paso, busco el ultimo nodo de la lista circular, para luego así poder ir modificando el puntero al próximo de este nodo} ultimo_nodo:= lc.cabeza; while (ultimo_nodo^.proximo <> lc.cabeza) do ultimo_nodo:= ultimo_nodo^.proximo; {Encontré el ultimo nodo de la lista, y procedo a borrar todos sus nodos, realizando una actualización de la posición a la que apunta el último nodo de la lista, o sea la cabeza de la lista circular} {Procedo a eliminar siempre la cabeza de la lista lc, actualizando su posición} while (lc.cabeza <> nil) do begin nodo_aux:= lc.cabeza; lc.cabeza:= lc.cabeza^.proximo; {antes de liberar la memoria, engancho los nodos correspondientes, para no tener referencias colgadas} ultimo_nodo^.proximo:= lc.cabeza; {De esta manera mantenemos el

28

concepto de lista circular} nodo_aux^.proximo:= nil; dispose(nodo_aux) end; {while} with lc do begin cabeza:= nil; corriente:= nil end {with} end; {lc_vaciar} end. Listas doblemente enlazadas: Las listas circulares nos facilita alcanzar cualquier nodo de la lista desde cualquier punto de comienzo. Aunque esta estructura tiene una ventaja sobre una lista lineal simplemente enlazada, aun es demasiado limitada para ciertos tipos de aplicaciones. Si queremos recorrer una lista simplemente enlazada o una lista circular en orden inverso, necesitamos de la recursividad como herramienta de trabajo. Pero ¿qué pasa si el lenguaje no posee esta propiedad? Necesitamos, de alguna manera poder acceder a los nodos que preceden al nodo corriente (o donde se encuentre el puntero parado, según otra implementación). Podemos solucionar este inconveniente agregando en la definición del nodo de la lista, otro puntero, que será el que me indique dónde se encuentra el nodo anterior, si es que hay uno. A una estructura cuyos nodos contienen, a parte del campo Info, un puntero que lo enlaza con el nodo siguiente, y otro que lo hace con el anterior, la llamamos lista doblemente enlazada. Una representación gráfica de este tipo de lista se encuentra a continuación: Las operaciones que manipulan estas listas, son exactamente las mismas que para listas simplemente enlazadas. La diferencia es que en cuanto a movimientos del nodo corriente, se puede hacer al primero, al siguiente, al anterior o al último. Obviamente, las implementaciones no serán las mismas porque cumplen funciones similares a las de listas simples, pero se agregan instrucciones al insertar y el eliminar nodos. Podemos definir una lista doblemente enlazada de la siguiente manera: type {La abreviatura ld, indica lista_doble, se utiliza para sintetizar su escritura.} 29

tipo_dato = ; tipo_movimiento_ld = (primero, anterior, siguiente, ultimo); tipo_ptr_nodo_ld = ^tipo_nodo_ld; tipo_nodo_ld = record info : tipo_dato; previo, proximo : tipo_ptr_nodo_ld tipo_lista_doble = record cabeza, final, corriente : tipo_ptr_nodo_ld end; { tlista_doble } Entonces, el tipo de dato abstracto lista doblemente enlazada se puede encapsular como sigue: unit listas_dobles; interface type {La abreviatura ld, indica lista_doble, se utiliza para sintetizar su escritura.} tipo_dato = ; tipo_movimiento_ld = (primero, anterior, siguiente, ultimo); tipo_ptr_nodo_ld = ^tipo_nodo_ld; tipo_nodo_ld = record info : tipo_dato; previo, proximo : tipo_ptr_nodo_ld end; {tipo_nodo_ld} tipo_lista_doble = record

30

cabeza, ultimo, corriente : tipo_ptr_nodo_ld end; { tlista_doble } {A continuación se presenta el listado de primitivas de la estructura de dato tipo_lista_simple } procedure ld_crear ( var ld : tipo_lista_doble ); {Pre: La lista ld no existe aún. Post: La lista ld existe y se encuentra vacía.} function ld_vacia ( ld : tipo_lista_doble ) : boolean; {Pre: La lista ld fue creada. Post: Si ld no tiene elementos, Entonces devuelve true, pues la lista está vacía Sino devuelve false, porque la lista ld tiene por lo menos un elemento.} procedure ld_insertar_antes ( var ld : tipo_lista_doble ; elem : tipo_dato ; var error : boolean ); {Pre: La lista ld fue creada. Elem contiene la información que se desea insertar en la lista justo antes del actual elemento corriente. Post: Si hubo lugar en la lista para realizar la inserción, Entonces error es false, pues elem se insertó en la lista ld y es el nuevo corriente Sino error es true porque no había lugar en la lista para que elem sea insertado.} procedure ld_insertar_despues ( var ld : tipo_lista_doble ;

31

elem : tipo_dato ; var error : boolean); {Pre: La lista ld fue creada. Elem contiene la información que se desea insertar en la lista justo antes del actual elemento corriente. Post: Si hubo lugar en la lista para realizar la inserción, Entonces error es false, pues elem se insertó en la lista ld y es el nuevo corriente Sino error es true porque no había lugar en la lista para que elem sea insertado.} procedure ld_mover_corriente ( var ld : tipo_lista_doble ; movimiento : tipo_movimiento_ld ; var error : boolean ); {Pre: La lista doble ld fue creada y no se encuentra vacía. Movimiento informa hacia dónde queremos movernos en la lista ld: primero, anterior, siguiente y ultimo. Post: Como la lista ld no está vacía, entonces los movimientos al primero y/o al ultimo elemento serán exitosos, con lo que error será false, debido a que no hay casos en los que se pueda cometer error alguno. Si movimiento es al siguiente y existe siguiente del corriente, Entonces error será false, y el nuevo corriente de ld es el elemento siguiente al corriente de la precondición Sino error es true, porque se trataba del último elemento de ld, y no tiene siguiente donde moverse.

32

Si el movimiento es al anterior y existe anterior al corriente, Entonces error será false, y el nuevo corriente de ld es elemento anterior al corriente de la precondición Sino error será true, porque el elemento era el primero, y no tiene anterior donde desplazarse.} procedure ld_obtener_corriente ( ld : tipo_lista_doble ; var elem : tipo_dato ); {Pre: La lista ld fue creada y no está vacía. Post: Elem contiene la información que posee el elemento corriente de la lista doble ld.} procedure ld_modificar_corriente ( var ld : tipo_lista_doble ; elem : tipo_dato ); {Pre: La lista ld fue creada y no está vacía. Elem contiene la información que se necesita para modificar el elemento corriente de la lista doble ld. Post: El elemento corriente de ld contiene la nueva información suministrada por el parámetro elem.} procedure ld_eliminar_corriente (var ld : tipo_lista_doble ); {Pre: La lista ld fue creada y no está vacía. Post: El elemento corriente de ld se eliminó de ella. El nuevo corriente es el siguiente al eliminado; pero, si éste era el último, el nuevo corriente es el primer elemento de la lista doble ld.} procedure ld_vaciar (var ld : tipo_lista_doble ); {Pre: La lista ld fue creada.

33

Post: La lista ld no contiene elementos.} Implementation procedure ld_crear ( var ld : tipo_lista_doble ); begin with ld do begin cabeza := nil; final:= nil; corriente := nil end {with} end; {ld_crear} function ld_vacia ( ld : tipo_lista_doble ) : boolean; begin ld_vacia := (ld.cabeza = nil) end; {ld_vacia} procedure ld_insertar_antes ( var ld : tipo_lista_doble ; elem : tipo_dato ; var error : boolean ); var nuevo_nodo : tipo_ptr_nodo_ld; begin error:= Maxavail < sizeof(tipo_nodo_ld); if (not error) then begin new(nuevo_nodo); {podemos insertar el nodo en ld sin problemas de memoria}

34

{preparo el nodo nuevo para insertarlo en ld, antes del corriente} with nuevo_nodo^ do begin info:= elem; previo:= nil; proximo:= nil end; {with} if (ld.cabeza = nil) then begin {la lista ld estaba vacía} ld.cabeza:= nuevo_nodo; ld.final:= nuevo_nodo end {then} else if (ld.cabeza = ld.corriente) then begin {el elemento será el primero} nuevo_nodo^.proximo:= ld.corriente; ld.corriente^.previo:= nuevo_nodo; ld.cabeza:= nuevo_nodo end {then} else begin {esta del segundo en adelante} nuevo_nodo^.proximo:= ld.corriente; nuevo_nodo^.previo:= ld.corriente^.previo; ld.corriente^.previo^.proximo:= nuevo_nodo; ld.corriente^.previo:=nuevo_nodo; end; {else} ld.corriente:= nuevo_nodo end {then}

35

end; {ld_insertar_antes} procedure ld_insertar_despues ( var ld : tipo_lista_doble ; elem : tipo_dato ; var error : boolean); var nuevo_nodo : tipo_ptr_nodo_ld; begin error:= Maxavail < sizeof(tipo_nodo_ld); if (not error) then begin new(nuevo_nodo); with nuevo_nodo^ do begin info:= elem; previo:= nil; proximo:= nil end; {with} if(ld.cabeza = nil) then begin {la lista ld está vacía} ld.cabeza:= nuevo_nodo; ld.final:= nuevo_nodo end {then} else begin if (ld.corriente = ld.final) then begin nuevo_nodo^.previo:= ld.corriente; ld.corriente^.proximo:= nuevo_nodo;

36

ld.final:= nuevo_nodo end {then} {pues lo debo insertar al final de ld} else begin {el elemento corriente forma parte de un elemento intermedio de ld} nuevo_nodo^.previo:= ld.corriente; nuevo_nodo^.proximo:= ld.corriente^.proximo; ld.corriente.proximo^.previo:= nuevo_nodo; ld.corriente.proximo:= nuevo_nodo end; {else} ld.corriente:= nuevo_nodo {el nuevo nodo es el nuevo elemento corriente de ld} end {else} end {then} end; {ld_insertar_despues} procedure ld_mover_corriente ( var ld : tipo_lista_doble ; movimiento : tipo_movimiento_ld ; var error : boolean ); begin error:= false; case (movimiento) of primero : ld.corriente:= ld.cabeza; anterior : if (ld.corriente^.previo <> nil) then ld.corriente:= ld.corriente^.previo else error:= true; siguiente : if (ld.corriente^.proximo <> nil) then ld.corriente:= ld.corriente^.proximo

37

else error:= true; ultimo : ld.corriente:= ld.final end {case} end; {ld_mover_corriente} procedure ld_obtener_corriente ( ld : tipo_lista_doble ; var elem : tipo_dato ); begin elem:= ld.corriente^.info end; {ld_obtener_corriente } procedure ld_modificar_corriente ( var ld : tipo_lista_doble ; elem : tipo_dato ); begin ld.corriente^.info:= elem end; {ld_modificar_corriente} procedure ld_eliminar_corriente (var ld : tipo_lista_doble ); var nodo_aux : tipo_ptr_nodo_ld; begin nodo_aux:= ld.corriente; {Ahora debo eliminar la posición del corriente en la lista (con nodo_aux), luego liberar la memoria dinámica teniendo cuidado de no dejar referencias colgadas} {Casos a contemplar: • Hay un sólo elemento en ld • Hay más de un elemento: • El corriente es el primero • El corriente es el último • El corriente esta en el medio de ld} if (ld.cabeza = ld.final)

38

then begin {Caso 1: Hay un sólo elemento en la lista ld} ld.cabeza:= nil; ld.final:= nil end {then} else if (ld.cabeza = ld.corriente) then begin {Caso 2.A: El corriente es el primero} ld.corriente^.proximo^.previo:= ld.corriente^.previo; ld.cabeza:= ld.corriente^.proximo end {then} else if (ld.corriente = ld.final) then begin {Caso 2.B: El corriente es el último} ld.corriente^.previo^.proximo:= ld.corriente^.proximo; ld.final:= ld.corriente^.previo end {then} else begin {Caso 2.C: El corriente está en medio de ld} ld.corriente^.previo^.proximo:= ld.corriente^.proximo; ld.corriente^.proximo^.previo:= ld.corriente^.previo end; {else} {Ahora debo actualizar el nuevo corriente de la lista ld} if (ld.cabeza = nil) then ld.corriente:= nil {ld quedó vacía} else if (ld.corriente^.proximo <> nil) then ld.corriente:= ld.corriente^.proximo else ld.corriente:= ld.cabeza; {A continuación libero la memoria dinámica correspondiente al elemento corriente de la lista doble ld, almacenado en nodo_aux}

39

with nodo_aux^ do begin previo:= nil; proximo:= nil; dispose(info) end{with} end;{ld_eliminar_corriente} procedure ld_vaciar (var ld : tipo_lista_doble ); var nodo_aux : tipo_ptr_nodo_ld; begin while (ld.cabeza <> nil) do begin nodo_aux:= ld.cabeza; if (ld.cabeza^.proximo <> nil) then begin ld.cabeza^.proximo^.previo:= nil; ld.cabeza:= ld.cabeza^.proximo end; {then} with nodo_aux^ do begin previo:= nil; proximo:= nil; info:= nil end; {with} dispose(nodo_aux); nodo_aux:= nil

40

end; {while} {Ahora ld está vacía} with ld do begin cabeza:= nil; final:= nil; corriente:= nil end {with} end; {ld_vaciar} {Período de inicialización} end. Variaciones sobre una lista doblemente enlazada: Como vemos en el dibujo anterior, las listas doblemente enlazadas pueden tener una cabecera y un final. Con o sin cabeceras y finales, esta estructura también puede implementarse como circular en vez de lineal. En ambas implementaciones podemos acceder al último elemento. Esto se logra en la figura (a), guardando el puntero que me indica el final de la lista, en la propia definición. En la figura que representa a la lista circular o figura (b), si nuestra cabeza apunta al primer nodo de la lista (que lo adoptaremos por convención), basta con acceder al puntero al anterior del primer elemento para estar parados en el último. La definición e implementación de listas circulares doblemente enlazadas quedará a cargo de los lectores. Niveles de abstracción: Presentamos a continuación, tres ejemplos de distintos niveles de abstracción en la aplicación de listas encadenadas; obviamente éstas son sólo algunas de las tantas ocurrencias. • Lista doblemente enlazada encadenada con una lista simplemente enlazada: 2. Lista circular doblemente enlazada encadenada con otra lista doblemente enlazada (dos niveles de abstracción): 3. Lista doblemente enlazada encadenada con una lista simplemente enlazada, y esta última a su vez, está encadenada con una lista circular simplemente enlazada (tres niveles de abstracción): (Representaremos sólo un nodo de la lista doblemente enlazada, debido a que el espacio que se necesita para el dibujo completo no alcanza para reproducirlo en esta hoja). Más aplicaciones de las listas enlazadas:

41

Un sistema operativo es un programa que gestiona y asigna los recursos de un sistema informático. Los sistemas operativos utilizan listas enlazadas de muchas formas. La asignación de espacio de memoria (uno de los recursos del sistema) puede gestionarse usando una lista doblemente enlazada de bloques de tamaño variables de memoria. el enlace doble de las listas facilita la sustitución de bloques de la mitad de la lista. En un sistema multiusuario, el sistema operativo puede llevar los trabajos en espera del usuario para que se ejecuten mediante colas enlazadas de bloques de control (registros que contienen información sobre la identificación del usuario, el programa a ejecutar los archivos asociados con el programa, etc.). Aunque normalmente una representación enlazada o secuencial de una lista puede usarse con buenos resultados, hay veces en las que la enlazada es una elección mucho mejor. Por ejemplo, las listas enlazadas se utilizan frecuentemente para implementar una matriz rala. Una matriz, al ser tan grande de tamaño, no es posible (o es inútil) definirla como un array de dos dimensiones, porque la mayor parte de sus elementos son nulos, y estaríamos ocupando memoria estática demasiado grande sin sentido alguno. De esta forma, una matriz rala puede especificarse de una forma más eficiente mediante una implementación dinámica, con listas enlazadas, ya que podemos almacenar en el campo info los índices de la matriz donde se encuentra el elemento no nulo (fila y columna), y obviamente el coeficiente correspondiente. Una matriz con estas características la representamos gráficamente a continuación. 1 Especificaciones de entrada (Precondiciones) Nivel de Implementación Nivel de uso o Aplicación Especificaciones de salida (Postcondiciones) ABSTRACCIÓN DE DATOS Info Siguiente Datos del usuario Conexión con el nodo siguiente de la lista

42

Info Info Puntero al primero Último elemento Primer nivel de abstracción (lista simplemente enlazada) Puntero al primer nodo de la lista encadenada Segundo nivel de abstracción (lista simplemente enlazada) Puntero al primer nodo de la lista circular Puntero al primer nodo de la lista doble Puntero al último nodo de la lista doble Primer nivel de abstracción (lista doblemente enlazada) Segundo nivel de abstracción (lista simplemente enlazada) Puntero al último elemento Puntero al primer elemento Primer nivel de abstracción (lista doblemente enlazada) Puntero al primer elemento Segundo nivel de abstracción (lista doblemente enlazada) Primer nivel de abstracción (lista doble) Tercer nivel de abstracción

43

(lista circular) Segundo nivel de abstracción (lista simple)

44