Listas Circulares

Definición:        

Una lista circular es una lista lineal en la que el último nodo a punta al primero.

No existen casos especiales, cada nodo siempre tiene uno anterior y uno siguiente.

Se representa:

 Operaciones básicas

Mostrar:

A la hora de buscar elementos en una lista circular, es necesario almacenar el puntero del nodo en que se empezó la búsqueda, para poder detectar el caso en que no exista el valor que se busca. Por lo demás, la búsqueda es igual que en el caso de las listas abiertas.

Inserción por la cabeza de lista enlazada 
 1. Crear un nuevo nodo. 

 2. Almacenar el dato en el campo correspondiente (datos). 

 3. Como va a ser el primer nodo, su enlace deberá apuntar al que hasta ahora era el primer nodo (apuntado por el enlace externo). 

 4. El enlace externo deberá apuntar al nuevo nodo (que ahora es el primero). 

Eliminacion 
Para ésta operación podemos encontrar tres casos diferentes:

• Eliminar un nodo cualquiera, que no sea el apuntado por lista. 

• Eliminar el nodo apuntado por lista, y que no sea el único nodo.
• Eliminar el único nodo de la lista.

  

eliminar un nodo en una lista circular con mas de  un elemento 

En el primer caso necesitamos localizar el nodo anterior al que queremos borrar. Como el principio de la lista puede ser cualquier nodo, haremos que sea precisamente lista quien apunte al nodo anterior al que queremos eliminar. 

Esto elimina la excepción del segundo caso, ya que lista nunca será el nodo a eliminar, salvo que sea el único nodo de la lista.

Una vez localizado el nodo anterior y apuntado por lista, hacemos que lista->siguiente apunte a nodo->siguiente.

Y a continuación borramos nodo. 

En el caso de que sólo exista un nodo, será imposible localizar el nodo anterior, así que simplemente eliminaremos el nodo, y haremos que lista valga NULL.

Tipos de listas

•          Listas enlazadas circulares simples.

•          Listas enlazada doblemente circular.

Listas enlazadas circulares simples.

Cada nodo tiene un enlace, similar al de las listas enlazadas simples, excepto que el siguiente nodo del ultimo apunta al primero.

 

 Listas enlazada doblemente circular.

En una lista enlazada doblemente circular, cada nodo tiene dos enlaces, las insercciones y eliminaciones se realizan desde cualquier punto.