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.
Operaciones basicas.
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.
Inserccion de datos.
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.
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.
Eliminar un nodo en una lista circular con más de un elemento.
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.
Hacemos que lista->siguiente apunte a nodo->siguiente.
Eliminamos el nodo.
Eliminar el único nodo en una lista circular.
Este caso es mucho más sencillo. Si lista es el único nodo de una lista circular:
Borramos el nodo apuntado por lista.
Hacemos que lista valga NULL.
Tipos de listas circulares.
Listas enlazadas simples.
Cada nodo tiene un enlace, similar al de las listas enlazadas simples, excepto que el siguiente nodo del ultimo apunta al primero.
Listas enlazadas doblemente circulares.
En una lista enlazada doblemente circular, cada nodo tiene dos enlaces, las insercciones y eliminaciones se realizan desde cualquier punto.
