Resumen
Las listas son estructuras lineales y dinámicas de datos. La principal ventaja del dinamismo lo representa el hecho de que se adquieren posiciones de memoria a medida que se necesitan y se liberan cuando ya no se requieren. Es decir, se llegan a expandir o contraer, dependiendo de la aplicación. El dinamismo de estas estructuras soluciona el problema de decidir cuánto espacio se necesita a priori, por ejemplo, en una estructura de datos estática como el arreglo. En este capítulo estudiaremos las listas lineales, circulares y doblemente ligadas. También se presentan estas estructuras con un enfoque orientado a objetos.
En el presente trabajo se presenta la estructura de datos listas. Este es un tipo de estructura lineal y dinámica de datos. Lineal porque a cada elemento le puede seguir solo otro elemento; dinámica porque se puede manejar la memoria de manera flexible, sin necesidad de reservar espacio con antelación.
La principal ventaja de manejar un tipo dinámico de datos es que se puede adquirir posición de memoria a medida que se necesitan; éstas se liberan cuando ya no se requieren. Así es posible crear estructuras dinámicas que se expandan o contraigan, según se les agregue o elimine elementos. El dinamismo de estas estructuras soluciona el problema de decidir cuál es la cantidad óptima de memoria que se debe reservar para un problema específico. Sin embargo, es importante destacar que las estructuras dinámicas no pueden reemplazar a los arreglos en todas sus aplicaciones. Existen numerosos casos que podrían facilitarte ser solucionados aplicando arreglos, mientras que si se utilizan estructuras dinámicas, como las listas, la solución de estos problemas se complicaría.
Las listas ligadas son colecciones de elementos llamados nodos, el orden entre estos se establece por medio de un tipo de datos denominado punteros, apuntadores, direcciones o referencias a otros nodos. Por tanto, siempre es importante distinguir entre un dato de tipo apuntador y el dato contenido en la celda al cual este apunta. Se usará la notación P (^D para indicar que P es un apuntador al nodo D, Crear (P) para señalar el proceso de asignación de memoria al nodo P, y Quitar (P) para indicar el proceso inverso; es decir, cuando se libera una posición de memoria apuntada por P.
Las operaciones mas importantes que se realizan en las estructuras de datos son las de busqueda, insercion y eliminacion. Se utilizan tambien para comparar la eficiencia de las estructuras de datos y de esta forma observar cual es la estructura que mejor se adpta al tipo de problema que se quiere resolver. La busqueda por ejemplo, es una operación que no se puede realizar en forma eficiente en las listas. Por otra parte, las operaciones de insercion y eliminacion se efectuan de manera eficiente en este tipo de estructura de datos. Este capitulo se dedicara a las estructuras dinamicas lineales llamadas listas; entre se distinguen tres tipos: listas simplemente enlazadas ligadas, listas doblemente ligadas y listas circulares.
Listas enlazadas
Una lista enlazada o estructura ligada, es una estructura lineal que almacena una colección de elementos generalmente llamados nodos, en donde cada nodo puede almacenar datos y ligas a otros nodos. De esta manera los nodos pueden localizarse en cualquier parte de la memoria, utilizando la referencia que lo relaciona con otro nodo dentro de la estructura.
Las listas enlazadas son estructuras dinámicas que se utilizan para almacenar datos que están cambiando constante mente. A diferencia de los vectores, las estructuras dinámicas se expanden y se contraen haciéndolas más flexibles a la hora de añadir o eliminar información.
Las listas enlazadas permiten almacenar información en posiciones de memoria que no sean contiguas; y se almacena en los elementos nodos. Estos nodos poseen dos campos uno para almacenar la información o valor del elemento y otro para el enlace que determina la posición del siguiente elemento o nodo de la lista.
Figura N° 1. Estructura de un nodo
Se compone de dos partes: una que contiene la información en sí y la segunda es un puntero y q su función es apuntar al siguiente nodo que haya.
Listas enlazadas simples
Una lista enlazada simple es una colección de nodos que tienen una sola dirección y que en conjunto forman una estructura de datos lineal. Cada nodo es un objeto compuesto que guarda una referencia a un elemento (dato) y una referencia a otro nodo (dirección).
La referencia que guarda un nodo a otro nodo se puede considerar un enlace o un puntero hacia el segundo nodo y el salto que los relaciona recibe el nombre de salto de enlace o salto de puntero. El primer nodo de una lista recibe el nombre de cabeza, cabecera o primero y el último es llamado final, cola o último (es el único nodo con la referencia a otro objeto como nula).
Un nodo de una lista enlazada simple puede determinar quien se encuentra después de él pero no puede determinar quien se encuentra antes, ya que solo cuenta con la dirección del nodo siguiente pero no del anterior.
Figura
Figura N° 1.1 Se observa un puntero que va a apuntar al primer elemento que se ingresa y otro puntero que apuntara al último que será NULO.
Cuando tenemos una lista de la siguiente manera cada puntero apuntara al nodo siguiente y el puntero de la última lista como no tiene a donde apuntar entonces apuntara a NULO.
Para acceder a un nodo se utiliza la anterior con excepción del primero (no tiene a nadie antes) al que se tiene que acceder a través de un puntero externo a la lista, entonces se usa los punteros INICIO que es el que apunta constantemente al primero y el puntero ultimo q es el q apunta constantemente al último.
Figura N° 1.2 Esquema de una lista simple enlazada.
Antes de analizar cada una de estas operaciones, se presentara un algoritmo que permite crear una lista simplemente ligada, al incorporar cada nudo al inicio.
Algoritmo 1.1 Crea_inicio
Crea_inicio
{Este algoritmo permite crear una lista simplemente ligada, agregando cada nuevo nodo al inicio de la misma}
{P y Q son variables de tipo puntero. Los campos del nodo son INFO, que sera el tipo de datos que se quiera almacenar en la lista, y LIGA de tipo apuntador, P apunta al inicio de la lista. RES es una variable de tipo entero}
1. Crear (P) {Se crea un primer nodo de la lista simplemente ligada}
2. Leer P^.INFO
3. Hacer P^.LIGA(NILL
4. Escribir "¿Desea ingresar mas nodos a la lista? SI:1 , NO : 0"
5. Leer RES
6. Mientras (RES=1) Repetir
Crear (Q)
Leer Q^.INFO
Hacer Q^.LIGA(P y P(Q
Escribir"¿ Desea ingresar mas nodos a la lista? SI:1 , NO : 0"
Leer RES
7. Fin- mientras
8. Fin
Veamos un ejemplo para ilustrar el fundamento de este algoritmo.
Ejemplo 1.1
Dados los siguientes datos: García, Perez, Lopez y Santos, genere una lista simplemente ligada mediante el algoritmo 1.1. En la siguiente figura se puede observar, paso a paso, cómo se va construyendo la lista.
Como observaramos en la figura 1.3, la lista quedo en orden inverso con respecto al orden en el que fueron dados, se debe agregar cada nodo al final de la lista. A continuacion se presenta un algoritmo que permite crear una lista simplemente ligada, al incorporar cada nuevo nodo al final.
Figura 1.3 Creación de listas. A) Luego de crear el primer nodo. B) Luego de insertar a "Pérez". C) Luego de insertar a "López". D) Luego de insertar a "Santos".
NOTA: Las flechas discontinuas indican los cambios originados al insertar un nuevo elemento al inicio de la lista.
Algoritmo 1.2 Crea_final
Crea_final
{Este algoritmo permite crear una lista simplemente ligada, agregando cada nuevo nodo al final de la misma} {P, Q y T son variables de tipo apuntador. Los campos del nodo son INFO, que sera el tipo de datos que se quiera almacenar en la lista, y LIGA de tipo apuntador, P apunta al inicio de la lista. RES es una variable de tipo entero}
1. Crear (P) {Se crea un primer nodo de la lista}
2. Leer P^.INFO
3. Hacer P^.LIGA(NILL T( P
4. Escribir "¿Desea ingresar mas nodos a la lista? SI:1 , NO : 0"
5. Leer RES
6. Mientras (RES=1) Repetir
Crear (Q)
Leer Q^.INFO
Hacer Q^.LIGA( NILL, T^.LIGA(Q y T (Q{T apunta al ultimo nodo}
Escribir"¿ Desea ingresar mas nodos a la lista? SI:1 , NO : 0"
Leer RES
7. Fin- mientras
8. Fin
Veamos un ejemplo para ilustrar el funcionamiento de este algoritmo.
Ejemplo 1.2. Se utilizan los datos del ejercicio anterior para crear una lista aplicando el algoritmo 1.2. Es importante observar que en este algoritmo se utiliza otra variable de tipo apuntador para mantener la dirección del ultimo nodo de la lista, de tal manera que se pueda establecer el enlace entre este y el nuevo nodo. En la figura 1.3 se puede observar, paso a paso, como se va construyendo esta lista.
Figura 1.3. Esquema de inserción al final.
Operaciones básicas de listas enlazadas simples
Recorrido de una lista simplemente enlazada
La operación de recorrido en una lista simplemente ligada consiste en visitar cada uno de los nodos que forman la lista. La isita puede implicar una operación simple; por ejemplo, imprimir la información del nodo, o una compleja, dependiendo del problema que se intenta resolver.
Para recorrer todos los nodos de una lista simplemente ligada se comienza con el primero. Se toma el valor del campo Liga de este y se avanza al segundo, y así sucesivamente hasta llegar al último nodo, cuyo campo LIGA tiene el valor NILL. En general, la dirección de un nodo, excepto el primero, está dada por el campo LIGA de su predecesor.
El algoritmo 2.1.1.presenta los pasos necesarios para recorrer una en forma iterativa.
Algoritmo 1.3 Recorre_iterativo
Recorre_iterativo (P)
{Este algritmo recorre una lista cuyo primer nodo esta apuntado por P}
{Q es una variable de tipo apuntador. INFO y LIGA son los campos de cada nodo de la lista}
Hacer Q( P
Miestras (Q NIL) Repetir
Escribir Q^.INFO
Hacer Q(Q^.LIGA {Apunta al siguiente nodo de la lista}
{Fin miestras}
FIN
Las listas se pueden manejar facilmente con procesos recursivos. El algoritmo constituye una versión recursiva para recorrer una lista simplemete ligada.
Algoritmo 1.4 Recorre_recursivo
Recorre_recursivo (P)
{Este algoritmo recorre una lista simplemente ligada en forma recursiva. P es un apuntador al nodo que se va a visitar. La primera vez trae la direccion del primer nodo de la lista}
{INFO y LIGA son los campos de cada nodo de la lista}
1. Si P NIL entonces
Escribir P^. INFO
Llamar a Recorre_recursivo con P^.LIGA
{Llamada recursiva con el apuntador al siguiente nodo de la lista}
2. Fin- Si
Veamos ahora la operación de insercion en listas simplemente ligadas.
Inserción en listas simplemente enlazadas
La operación de inserción en listas simplemente ligadas consiste en agregar un nuevo nodo a la lista, sin embargo, dependiendo de la posición en la que se deba insertar el nodo, se puede presentar diferentes casos, como los que se señalan a continuación.
Insertar un nodo al inicio de la lista.
Insertar un nodo al final de la lista.
Insertar un nodo antes que otro cuya información es X.
Insertar un nodo después de otra cuya información es X.
No se considerara en estos algoritmos el caso de que la lista este vacía; esta condición se puede incluir ya sea al inicio del algoritmo o en programa principal. Se considerara entonces que la lista en la cual se va a insertar el nodo ya existe -por lo menos tiene un nodo—.
a) Inserción al inicio de una lista simplemente ligada
En este caso el nodo se coloca al principio de la lista simplemente ligada, convirtiéndose en la primera de ellas. El proceso es relativamente simple como se puede observar en el siguiente algoritmo.
Algoritmo 1.5 Inserta_inicio
Inserta_inicio (PP, DATO)
{Este algoritmo inserta un nodo al inicio de una lista simplemente ligada. P es el apuntador al primer nodo de la misma, y DAO es la información que se almacenara en el nuevo nodo} {Q es una variable de tipo apuntador, INFO y LIGA son los campos de cada nodo de la lista}
1. Crear (Q)
2. Hacer Q^.INFO (DATO.Q^.LIGA(P y P ( Q
Figura 1.4 inserción al inicio de una lista.
b) Inserción al final de una lista simplemente Ligada
En este caso el nuevo nodo se coloca al final de la lista simplemente Ligada, convirtiéndose en el último, el algoritmo 5. 6 describe este proceso.
Algoriitmo 1.6 Inserta_Final
Inserta_final (P;DATO)
{este algoritmo insera un nodo final de una lista simplemente ligada. P es el apuntador al primer nodo de la lista, y DATOesla informacion que se almacenara en el nuevo nodo}
{Q y t son variables de tipo puntero. INFOy LIGA son los campos de cada nodo de la lista}
1) Hacer T( P
2) Mientras (T^.LIGANIL) repetir
{recorre la lista hastallegar al ultimo elemento}
Hacer T(T^.LIGA
3) Fin-Mientras
4) Crear {Q}
5) Hacer Q^.INFO ( DATOQ^.LIGA ( NIL y T^.LIGA(Q
Ejemplo 1.4
En la figura 1.5 se presenta un ejemplo de insercion final de la lista. Si cada lista simplemente ligada se utilizaran dos apuntadores,uno al primer nodo y el otro al ultimo, entonces el proceso de insercion al final se simplificaria, ya que no seria necesario recorrerla toda para llegar al final. El nuevo nodo se podra incorporar directamente, como en el caso de insercion al inicio de la lista.
Figura 1.5. Inserción al final de la lista
c) Insercion de un nodo antes que otro en la lista siplemnete ligada
Eneste tipo de insercion en las listas simplemente ligadas , el nuevo nodo se debe colocar antes de ptro nodo dado como referencia. Se pueden presentar diferentes caso; por ejemplo, que el nodo dado como refrencia no se encuentre en la lista o que el nuevo nodo a insertar se convierta en el primero . Se asume , como se ha señalado anteriormente, que la lista no esta vacia.
Algoritmo 1.7 Inserte_antes_X
Inserte_antes_X (P, DATO, X)
{Este algoritmo inserta un nodo dado como referencia en una lista simplemente ligada. P es el apuntador al primer nodo de la lista, DATO indica la información se almacenara en el nuevo nodo, y X representa el contenido – información—del nodo dado como referencia}
{Q, X y T son variables de tipo apuntador, INFO y LIGA son los campos de los nodos de la lista. BAND es una variable de tipo entero}
1) Hacer Q( P y BAND ( 1
2) Mientras ((Q^.INFO X) y (BAND =1) repetir
Si (Q^.LIGANIL) Entonces
Hacer T( Qy Q^.LIGA
Sino
Hacer BAND(0
Fin – Si
Fin – Mientras
3) Si (BAND=1) Entonces
Crear(X)
Hacer X^.INFO ( DATO
Si (P=Q) Entonces {El nodo dado como refrencia es el primero}
Hacer X^.LIGA (P y P (X
Si no
Hacer T^.LIGA(X y X^.LIGA ( Q
Fin – Si
Si no
Escribir "el nodo dado como referencia no se encuentra en la lista "
Fin – Si
d) Insercion de un nodo despues de otro en una lista completamente ligada
En estetipo de insercion en listas simplemete ligadas, el nuevo nodo s debe colocar despues de otro lado coo referencia. Sepueden presentar diferentes casos: por ejemplo, que el nodo dado como referencia no se encuentre en la lista o queel nuevo se convierta en el ultimo de la lista. Se asume, como se haseñalado, que la lista no esta vacia. A continuacion se presenta el algoritmo correspondiente.
Algoritmo 1.8 Inserta_despues_X
Inserta_despues_X (P; DATO, X)
{Este algoritmo inserta un nodo despues de otro dado como referencia en una lista simplemente ligada P es el apuntador al primer nodo de la lista,DATO indica la informacion sea alamacenara el nuevo nodo, y X representa el contenido , informacion, del nodo dado como refrencia}
{Q yT son variables de tipo apuntador , INFO y LIGA son los campos de nodo de la lista BAND es una variable de tiipo entero}
Hacer Q(P y BAND (1
Mietras ((Q^.INNFOX)y(BAND=1)) Repetir
Si Q ^.LIGANIL Entonces
Hacer Q(Q^.LIGA
Si no
Hacer BAND( 0
Fin-Si
Fin – Mientras
Si (BAND=1) Entonces
Crear (T)
Hacer T^.INFO ( DATO, T^.LIGA ( Q^.LIGA (T
Si no
Escribir "El nodo dado como referencia no se encuentra en la lista"
Fin Si
Figura.1.6. Las flechas discontinuas indican los cambios originados por la inserción de un nuevo nodo precediendo a otro, dado como referencia.
Eliminación en listas simplemente enlazadas
La operación de eliminacion en listas simplemnte ligadas consiste en eliminar un numero de la lista y liberar el espaciode memoria correspondiente. Dependiendo de la posicion en la que este se encuentre, se pueden presentar diferentes casos, como los que se señalan a continuacion:
Eliminar el primer nodo
Eliminar el ultimo nodo
Eliminar un nodo con informacion X
Eliminar el nodo anterior al nodo con informacion X
Eliminar el nodo posterior al nodo con informacion X
Cabe desacar que en los algoritmos que se presentan a continuacion no se consideran que la lista este vacia. Esta condicion se puede evaluar facilmente al inicio del algoritmo o bien e el programa principal.
a) Eliminar el primer nodo de una lista simplemente ligada
Esta operación es muy sencilla, ya que solo es necesario redefinir el apuntador al inicio de la lista. Si esta quedara vacia ( es decir, si la lista tenia solo un elemento), entonces apuntaria a NIL. Ene el siguiente algoritmo se describe este caso.
Algoritmo 1.9 Elimina_Inicio
Elimina_Inicio(P)
{Este algoritmo permite eliminar el primer elemento de una lista simplemente ligada. P es el apuntador al primer nodo de la lista}
Hacer Q ( P {Si la lista tuviera solo un elemento a P se le asigna NIL, que es el valor de Q^.LIGA. En caso contrario, queda con la direccion del siguiente nodo}
Hacer P( Q^.LIGA. {redefine el puntero al inicio de la lista}
Quitar (Q)
Figura 1.7 muestra la eliminación del primer nodo utilizando el algoritmo anterior.
b) Eliminacion del ultimo nodo de la lista simplemente ligada
En este caso se debe eliminar el ultimo nodo de una lista simplemente ligada. Es importante observar que para alcanzar el ultimo nodo, se debe recorrer toda la lista, exepto si se usara un apuntador que indique su final. A continuacion se presenta un algoritmo de solucion, considerando que solamente se tiene un apuntador al inicio de la lista.
Algoritmo 1. 10 Elimina_ultimo
Elimina_ultimo (P)
{este algoritmo permite eliminar el ultimo nodo de una lista simplemente ligada. P es el apuntador al primer nodo de la lista}
{Q y T son variables de tipo apuntador. INFO y LIGA son los campos de los nodos de la lista}
Hacer Q(P
Si (P^.LIGA = NIL) {Se berifica si la lista tiene solo un nodo} entonces
Hacer P(NIL
sino
Mientras (Q^.LIGA!=NIL) Repetir
Hacer T(Q y Q(Q^.LIGA
Fin-Mientras
Hacer T^.LIGA(NIL
Fin-Si
Qyutar(Q)
Figura 1.8. La flecha discontinua indica los cambios originados por la eliminación del último nodo de la lista.
c) Eliminar un nodo con informacion X de una lista simplemente ligada
La eliminacion de un nodo con informacion X es uno de los casos complicados una operación, porque se pueden presentar diferentes variantes. Por ejemplo, el nodo, puede ser el primero, el ultimo, el unico o no encontrarse en la lista. El algoritmo 1.11 demuestra este proceso.
Algoritmo 1.11 elimina_X
Elimina_X(P,X)
{este algoritmo elimina un nodo con informacion X de una lista simplemente ligada. P es el apuntador al primer nodo de la lista}
{Q y T son son variables de tipo apuntador. BAND es una variable de tipo entero, INFO y LIGA son los campos de los nodos de la lista}
Hacer Q(P y BAND( 1
Mientras ((Q^.INFO X) y (band = 1)) Repetir
Si Q^. LIGA NIL entonces
Hacer T(Q y Q ( Q^.LIGA
Sino
Hacer BAND ( 0
FIN SI
FIN – Mientras
Si (BAND=0) entonces
Enscribir "El elemento con informacion X no se encuentra en la lista"
Si (P= Q) {se verifia si el elemento a eliminar es el primero} entonces
Hacer P(Q^.LIGA
Sino
Hacer T^.LIGA ( Q^.LIGA
FIN-SI
FIN-si
Figura 1.9. Eliminación de un nodo con información X.
d) Eliminar el nodo anterior al nodo con informacion X en una lista simplemente ligada
Este es el caso de eliminacion mas complicando en listas simplemente ligadas, porque tiene muchas variantes. Por ejemplo, el nodo con informacion X puede ser el primero – entonces no hay nada que eliminar -, el segundo – entonces hay que eliminar el primero de la lista-, estar en cualquier otra posicion, o bien no encontrarse en la lista.
Algoritmo 1.12 elimina_ante_X
elimina_ante_X (P,X)
{este algoritmo permite eliminar el nodo anterior al nodo que contiene la informacion X en una lista simplemente ligada. P es el apuntador al primer nodo de la lista}
{Q ,T y R son son variables de tipo apuntador. BAND es una variable de tipo entero, INFO y LIGA son los campos de los nodos de la lista}
Búsqueda en listas simplemente enlazadas
La operación de búsqueda de un elemento en una lista simplemente ligada es muy fácil de realizar, aunque ineficiente ya que se lleva a cabo de forma secuencial. Se debe haber recorrido los nodos hasta encontrar el que estamos buscando o hasta que se llega al final de la lista. El algoritmo es similar a los que se desarrollaron para recorrer una lista en forma iterativa o recursiva.
Al igual que en las operaciones vistas anteriormente, existe diferencias en los algoritmos si las listas se encuentran ordenadas o desordenadas. Se comenzara en el primer término, con el algoritmo de búsqueda para listas simplemente ligadas que encuentran desordenadas.
Figura 1.10. eliminacion de nodos . la flecha discontinua indica los cambios originados por la eliminacion del nodo anterior a un nodo dado como referencia
Algoritmo 1.13. Busqueda desordenada
Busqueda desordenada (P,X)
{Este algoritmo permite buscar el elemento con informacion X en una lista simplemente ligada que se encuentra desordenada. P es el apuntador al primer nodo de la lista}
{Q es una variable de tipo apuntador. INFO y LIGA son campos de los nodos de la lista}
Hacer Q ( P
Mientras ((QNIL) y (Q^.INFOX))
Hacer Q ( Q^.LIGA
FIN Mientras
SI (Q = NIL) entonces
Escribir " El elemento no se encuentra en la lista"
Sino
Escribir "el elemento si se encuentra en la lista"
Fin- si
Es importante destacar que con una simple modificacion en la condicion del ciclo del paso 2 se adapte este algoritmo para la busqueda de elementos en listas simplemente ligadas que se encuentran ordenadas. A continuacion se presenta el algoritmo de busqueda en listas simplemente ligadas que se encuentran ordenadas en forma ascendente.
Algoritmo 1.14. Busqueda_ordenada
Busqueda_ordenada (P,X)
{este algoritmo permite buscar el elemneto con informacion X en una lista simplemente ligada que se encuentra ordenada en forma ascendente. P es el apuntador al primer nodo de la lista}
{Q es una variable de tipo apuntador, INFO y LIGA son los campos de los nodos de la lista}
Hacer Q (P
Mintras ((QNIL) y (Q^.INFO/font>
Hacer Q ( Q^.LIGA
Fin- Mientras
Si ((Q=NIL) o (Q^.INFO > X)) entonces
Escribir "el elemento no se encuentra en la lista"
Sino
Escribir "el elemento si se encuentra en la lista"
Fin- Si
Todos los algoritmos pressentados tanto para la busqueda, insercion y eliminacion se pueden implementar de forma recursiva. A continuacion se muestra una version recursiva del algoritmo 1.13.
Algoritmo 1.15. Busqueda_recursivo
Busqueda_recursivo (P,X)
{este algoritmo permite buscar recursivamente a un elemento con informacion X en una lista simplemente ligada que se encuentra desordenada. P es el apuntador al primer elemento de la lista}
Si (P NIL) entonces
Si (P^.INFO = X) entonces
Escribir "el elemento se encuentra en la lista"
Sino
Llamar a Busqueda_recursivo con P^.LIGA y X
Fin-Si
Sino
Escribir "el elemento se encuentra en la lista"
Fin-Si
Listas circulares
Las listas circulares son similares a las listas simplemente ligadas. Sin embargo, tiene las características de que el último elemento de la lista apunta al primero, en lugar a apuntar al vacío NL.
Se define una lista simplemente ligada circular como una colección de elementos llamados nodos en el cual el último nodo apunta al primero. En la figura 5.14 se presenta una gráfica de una lista circular.
Las operaciones son similares a las operaciones en listas lineales; por tanto, no se trataran nuevamente en esta sección. Sin embargo es importante.
Figura 2.1 Lista circular
Figura 2.2 Lista circular con nodo cabecera
Señalar que para el caso de la operación de recorrido de listas circulares se necesita considerar algún criterio para detectar cuando se han visitado todos los nodos de la lista. Esto último con el propósito de evitar caer en ciclos infinitos. Una ´posible solución al problema planteado consiste en usar un nodo extra llamado nodo de cabecera, para indicar el inicio de la lista. Este nodo contendrá información especial, de tal manera que se distinga de los demás y así podrá hacer una referencia al principio de la lista. La figura 5.15 presenta una gráfica en una lista circular con nodo de cabecera.
En los algoritmos presentados para operar con listas simplemente ligadas se puede apreciar que solo se tiene acceso a un nodo y al sucesor de este. Si se necesitara su predecesor, por ejemplo, se tendrían que usar variables auxiliares (Véase el algoritmo 5.12). Una manera de evitar esta situación, es teniendo acceso a los nodos en cualquier orden, antecesor o sucesor, ya demás recorrer la lista del inicio al fin, o viceversa. Las listas que cuentan con esta facilidad son las doblemente ligadas. A continuación se presenta este tipo de estructuras.
Listas doblemente enlazadas
Una lista doblemente ligada es una colección de nodos, en la cual cada uno de ellos tiene dos apuntadores (fig. 3.1a), uno apuntando a su predecesor (LIGAIZQ) y otro a su sucesor (LIGADER). Por medio de estos punteros se podrá entonces avanzar o retroceder a través de la lista, según se tomen las direcciones de uno u otro puntador. La figura 3.1b) representa una lista doblemente ligada que almacena apellidos.
Para tener un fácil acceso a la información de la lista es recomendable usar dos apuntadores, P y F, que apunten al principio y al final de esta, respectivamente.
Operaciones básicas de listas doblemente enlazadas
Las operaciones que se pueden llevar a cabo en este tipo de estructuras son las mismas que con listas simplemente ligadas. En esta sección se presentarán las operaciones de:
Recorrido de lista.
Inserción de un elemento.
Borrado de un elemento.
Figura 3.1 a) Estructura de un nodo. B) lista doblemente ligada.
Recorrido de una lista doblemente enlazada
Al tener cada nodo una doble liga, la lista se puede recorrer tanto del inicio al final, mediante las ligas derechas, como en sentido inverso; es decir, del final al principio, con las ligas izquierdas. Cualquiera que sea la direccion del recorrido, el algoritmo es similar al que se presenta para listas simplemente ligadas. Se deja al lector su diseño.
Inserción en listas doblemente enlazadas
La inserción de un elemento consiste en agregar un nuevo nodo a la lista y establecer los apuntadores correspondientes. No se considerará el caso de lista vacía. La inserción se puede llevar a cabo :
Al inicio de la lista doblemente ligada.
Al final de la lista doblemente ligada.
Antes/después de un nodo con información X.
a) Inserción al inicio de la lista doblemente ligada
En este caso el nuevo nodo se coloca al principio dse la lista y se establecen las listas correspondientes. El nuevo nodo insertado se convierte, entonces, en el primero de la lista doblemente ligada. El algoritmo 5.16 describe este proceso.
Algoritmo 5.16 Inserta_principio
Inserta_principio (P,DATO)
{ Este algoritmo inserta un nodo al inico de una lista doblemente ligada. P es el apuntador al primer nodo de la lista y DATO es la información que se almacenara ( en el nuevo nodo}
{Q es una variable de tipo apuntador. INFOR, LIGADER y LIGAIZQ son los campos de cada nodo de la lista}
Crear (Q)
Hacer Q^.INFOR (DATO, Q^.LIGADER(P. P^.LIGAIZQ ( Q.
Q^.LIGAIZQ(NIL y P(Q
b) Inserción al final de la lista doblemente ligada
En este caso el nuevo nodo se coloca al final de la lista doblemente ligada, convirtiéndose en el último. El algoritmo 5.17 describe este proceso.
Algoritmo 3.1. Inserta_final
Inserta_final (F, DATO)
(Este algoritmo inserva un nodo al final de una lista doblemente ligada. F es el apuntador al último nodo de la lista y DATO es la información que se almacenará en el nuevo nodo) (Q es una variable de tipo puntero. INFOR. LIGAIZQ y LIGADER son los campos de cada nodo de la lista)
Crear (Q)
Hacer Q^.INFOR ( DATO F^.LIGADER(Q, Q^.LIGAIZQ( F.
Q^.LIGADER ( NIL y F ( Q
Figura 3.2. Inserción al final de la lista. Las flechas discontinuas indican los cambios originados en la lista doblemente ligada, por la inserción doblemente ligada.
Al trabajar con un apuntador al último elemento de la lista, F, la operación de inserción se simplifica notablemente ya que evita recorrer toda la lista.
c) Inserción de un nodo antes que otro en una lista doblemente ligada
En este caso el nuevo nodo se coloca precediendo a otro dado como referencia. Cabe señalar que solo se presentará la operación de inserción de un nodo antes de otro como referencia, ya que las operaciones Antes_que_otro_y Después_que_otro sion métricas.
Algoritmo 3.2. Inserta_antes_X
Inserta_antesX (P,DATO,X)
{Este algoritmo inserta un nodo antes de otro dado como referencia, con informacion X.P es el apuntador al primer nodo de la lista, y DATO es la información que se almacenara en el nuevo nodo}
{Q, T y R son variables de tipo apuntador, INFOR, LIGADER y LIGAIZQ son los campos de cada nodo de la lista}
1. Hacer Q( P
2. Mientras ((Q^.LIGADER NIL) y (Q^.INFOR X)) Repetir Hacer Q ( Q^.LIGADER
3. Fin- Mientras
4. Si ( Q^INFOR = X) entonces
Crear (T) (Se crea el nuevo nodo)
Hacer T^. INFOR ( DATO. T^-LIGADER ( Q.R ( Q^.LIGAIZQ
Y Q^-LIGAIZQ ( T
4.1. Si (P = Q) entonces
Hacer P ( T y T^.LIGAIZQ ( NIL
Si no
Hacer R^.LIGADER ( T y T^.LIGAIZQ ( R
4.2. Fin- Si
si no
Escribir ¨El elemento no se encuentra en la lista¨
5. Fin – Si
Eliminación en listas doblemente enlazadas
La operación de eliminación de un nodo en una lista doblemente ligada al igual que en el caso de las listas simplemente ligadas, consiste en eliminar un elemento de la lista, redefiniendo los apuntadores correspondientes y liberando el espacio de la memoria ocupado por el nodo. En la eliminación se pueden presentar diferentes casos, aunque algunos de ellos son simétricos, ya que cada nodo tiene apuntadores hacia delante – derecha – y atráz-izquierda
Eliminar el primer nodo.
Eliminar el último nodo.
Eliminar el nodo con información X.
Eliminar el nodo anterior/posterior al nodo con información X.
En los algoritmos que presentan la solución a los diferentes casos de borrado de un elemento de una lista, no se considera que ésta se encuentre vacía. Este caso, como ya se ha repetido en varias ocasiones, se puede controlar en el programa principal o bien con una condición simple al inicio de cada algoritmo.
a) Eliminar el primer nodo de una lista doblemente ligada
Consiste en quitar el primer nodo de la lista, cualquiera que sea su información reteniendo puntero al inicio de la misma. El algoritmo 5.19 describe este proceso.
Algoritmo 3.3 Elimina_inicio
Elimina_inicio (P,F)
{Este algoritmo elimina el primer elemento de una lista doblemente ligada. P y F son los apuntadores al primer y último nodo de la lista, respectivamente}
{Q es una variable de tipo apuntador: INFOR, LIGADER y LIGAIZQ son los campos de cada nodo de la lista}
1. Hacer Q ( P
2. Si (Q ^.LIGADER NIL.) (Verifica si la lista tiene solo un nodo) entonces
Hacer P ( Q^.LIGADER y P^.LIGAIZQ ( NIL
si no
Hacer P ( NIL y F ( NIL
3. (Fin del condicional paso 2)
4. Quitar (Q)
Figura 3.3. Las flechas discontinuas indican los cambios originados en la lista doblemente ligada por la eliminación del primer nodo.
b) Eliminar el ultimo nodo de una lista doblemente ligada
Este caso es simétrico al anterior; consiste en eliminar el último nodo de una lista doblemente ligada y redefinir el apuntador al final de ella.
Algoritmo 3.4 Elimina_último
Elimina_último (P,F)
{Este algoritmo elimina el último elemento de una lista doblemente ligada P y F son los apuntadores al primero y último nodo de la lista, respectivamente}
1. Hacer Q ( F
2. Si (Q^.LIGAIZQ NIL) (Verifica si la lista tiene un solo nodo) entonces
Hacer F ( Q^.LIGAIZQ y F^.LIGADER ( NIL
si no
Hacer F ( NIL y P ( NIL
3.Quitar (Q)
figura 3.4 se presenta un ejemplo de eliminación del último nodo de una lista doblemente ligada el algoritmo anterior.
c) Eliminar un nodo con información X
Estes caso consiste en eliminar el nodo que contenga la información X, y establece los apuntadores correspondientes entre su antecesor y su sucesor, respectivamente. Este caso tiene algunas variantes. El nodo que se quiere eliminar puede que no se encuentre en la lista, o bien que se halle y sea el primero , el último, el único, o que esté en cualquier posición intermedia de la estructura.
Algoritmo 3.5 Elimina_X
Elimina_X (P, F, X)
(Este algoritmo el nodo con información X de una lista doblemente ligada. P y F son los apuntadores al primero y último nodos de la lista, respectivamente)
(Q, T y R son variables de tipo apuntador. INFOR, LIGADER y LIGAIZQ son los campos de cada nodo de la lista)
d) Eliminar el nodo anterior al nodo con información X
En este caso se trata de eliminar el nodo anterior a uno dado como referencia que tenga la información X. El caso también tiene algunas variantes. Puede ser que el nodo con información X no se encuentre en la lista o bien se encuentre, y sea el primero en ese caso no hay nada que eliminar—, el segundo— se elimina el primero de la lista—, o se encuentre en cualquier otra posición. El algoritmo 5.22 describe los pasos necesarios para llevar a cabo esta operación.
Algoritmo 3.6 Elimina_antes_X
Elimina_antes_X (P,X)
{Este algoritmo elimina, si se puede, el nodo anterior a aquel que contiene la información X.P es el apuntador al primer nodo de la lista}
{Q, T y R son variables de tipo apuntador, INFOR, LIGADER y LIGAIZQ son los campos de cada nodo de la lista}
La figura 3.5. contiene un ejemplo de eliminación, mediante el algoritmo anterior.
Figura 3.6 eliminación de nodos. Las flechas discontinuas indican los cambios originados e la lista doblemente ligada por la eliminación de un nodo.
Listas circulares doblemente enlazadas
En las listas doblemente ligadas circulares, el campo liga izquierda del primer nodo de la lista apunta al último, y el campo liga derecho de éste apunta al primero. La figura 3.6 representa una estructura de este tipo.
La principal ventaja de las listas circulares es que permiten la navegacion en cualquier sentido a travéz de la misma y, además,se puede recorrer toda la lista partiendo de cualquier nodo, siempre que tengamos un apuntador a éste. Sin embargo, debemos destacar que es necesario establecer condiciones adecuadas para detener el recorrido de una lista y evitar caer en ciclos infinitos. Al igual que en el caso de listas simplemente ligadas circulares, se suele utilizar un nodo de cabecera ( fig. 3.6) .
Este nodo tendrá las características descritas anteriormente y servirá como referencia para detectar cuándo se ha recorrido totalmente la lista.
| Página siguiente |