Listas Enlazadas

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.

Introducción

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.

Fundamento teórico

• 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.