Listas Circulares

Definición.
Una lista circular es una lista lineal en la que el último nodo a punta al primero.
Las listas circulares evitan excepciones en la operaciones que se realicen sobre ellas.Cada nodo siempre tiene uno anterior y uno siguiente.

¿Por qué utilizar una estructura Circular?

En una lista simplemente enlazada, el movimiento siempre fluirá desde la cabeza en dirección hacia el final de la lista, pero ¿qué ocurre cuando desde el último nodo se necesita operar con el primero?, este es el punto diferencial de una estructura abierta y una cerrada.

En una lista circular:

-         No existe algún elemento que apunte a NULL

-         Se integra una estructura tipo anillo

-         Solo hay una cabeza

-         La cabeza siempre será el siguiente enlace para algún nodo

-         Se pueden llegar a crear recorridos en bucles infinitos

Declaraciones de tipos para manejar listas circulares

Los tipos que definiremos normalmente para manejar listas cerradas son los mismos que para para manejar listas abiertas:

typedef struct _nodo \{
   int dato;
   struct _nodo *siguiente;
} tipoNodo;
 
typedef tipoNodo *pNodo;
typedef tipoNodo *Lista;

tipoNodo es el tipo para declarar nodos, evidentemente.

pNodo es el tipo para declarar punteros a un nodo.

Lista es el tipo para declarar listas, tanto abiertas como circulares. En el caso de las circulares, apuntará a un nodo cualquiera de la lista.

Pueden existir Listas Circulares Simplemente Enlazadas y Doblemente Enlazadas.

Gráficamente se tendría:

                    Simplemente Enlazadas                            Doblemente enlazadas

                                                                                                                                            

-         Nótese que con simple o doble referencia, siempre se tendrá solo una cabeza

 Operaciones básicas con listas circulares

A todos los efectos, las listas circulares son como las listas abiertas en cuanto a las operaciones que se pueden realizar sobre ellas:

• Añadir o insertar elementos.
• Borrar elementos.
• Moverse a través de la lista, siguiente.

Añadir elemento en una lista circular.

Partiremos de un nodo a insertar.

El proceso es muy sencillo:

1. Hacemos que nodo->siguiente apunte a lista->siguiente.
2. Después que lista->siguiente apunte a nodo.

Eliminar un nodo en una lista circular con más de un elemento

                                                          Lista con más de un elemento

1. El primer paso es conseguir que lista apunte al nodo anterior al que queremos eliminar. Esto se consigue haciendo que lista valga lista->siguiente mientras lista->siguiente sea distinto de nodo.
2. Hacemos que lista->siguiente apunte a nodo->siguiente.
3. Eliminamos el nodo.