Una lista circular simplemente encadenada la podemos representar gráficamente:
Observemos que el puntero sig del último nodo apunta al primer nodo. En este tipo de listas si avanzamos raiz no perdemos la referencia al nodo anterior ya que es un círculo.
Una lista circular puede también ser doblemente encadenada:
El puntero ant del primer nodo apunta al último nodo de la lista y el puntero sig del último nodo de la lista apunta al primero.
Resolveremos algunos métodos para administrar listas genéricas circulares doblemente encadenadas para analizar la mecánica de enlace de nodos.
Programa: programa172.c
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct nodo {
int info;
struct nodo *sig;
struct nodo *ant;
};
struct nodo *raiz=NULL;
void liberar()
{
if (raiz != NULL) {
struct nodo *reco = raiz->sig;
struct nodo *bor;
while (reco != raiz)
{
bor = reco;
reco = reco->sig;
free(bor);
}
free(raiz);
}
}
int vacia()
{
if (raiz == NULL)
return 1;
else
return 0;
}
void insertarPrimero(int x)
{
struct nodo *nuevo;
nuevo=malloc(sizeof(struct nodo));
nuevo->info = x;
if (raiz == NULL)
{
nuevo->sig = nuevo;
nuevo->ant = nuevo;
raiz = nuevo;
}
else
{
struct nodo *ultimo = raiz->ant;
nuevo->sig = raiz;
nuevo->ant = ultimo;
raiz->ant = nuevo;
ultimo->sig = nuevo;
raiz = nuevo;
}
}
void insertarUltimo(int x)
{
struct nodo *nuevo;
nuevo=malloc(sizeof(struct nodo));
nuevo->info = x;
if (raiz == NULL)
{
nuevo->sig = nuevo;
nuevo->ant = nuevo;
raiz = nuevo;
}
else
{
struct nodo *ultimo = raiz->ant;
nuevo->sig = raiz;
nuevo->ant = ultimo;
raiz->ant = nuevo;
ultimo->sig = nuevo;
}
}
void imprimir()
{
if (!vacia()) {
struct nodo *reco = raiz;
do {
printf("%i ",reco->info);
reco = reco->sig;
} while (reco != raiz);
printf("\n");
}
}
int cantidad()
{
int cant = 0;
if (!vacia())
{
struct nodo *reco = raiz;
do {
cant++;
reco = reco->sig;
} while (reco != raiz);
}
return cant;
}
void borrar(int pos)
{
if (pos <= cantidad())
{
if (pos == 1)
{
if (cantidad() == 1)
{
free(raiz);
raiz = NULL;
}
else
{
struct nodo *bor = raiz;
struct nodo *ultimo = raiz->ant;
raiz = raiz->sig;
ultimo->sig = raiz;
raiz->ant = ultimo;
free(bor);
}
}
else {
struct nodo *reco = raiz;
int f;
for (f = 1; f <= pos - 1; f++)
reco = reco->sig;
struct nodo *bor = reco;
struct nodo *anterior = reco->ant;
reco = reco->sig;
anterior->sig = reco;
reco->ant = anterior;
free(bor);
}
}
}
int main()
{
insertarPrimero(100);
insertarPrimero(45);
insertarPrimero(12);
insertarPrimero(4);
printf("Luego de insertar 4 nodos al principio\n");
imprimir();
insertarUltimo(250);
insertarUltimo(7);
printf("Luego de insertar 2 nodos al final\n");
imprimir();
printf("Cantidad de nodos:%i\n", cantidad());
printf("Luego de borrar el de la primer posicion:\n");
borrar(1);
imprimir();
printf("Luego de borrar el de la cuarta posicion:\n");
borrar(4);
imprimir();
liberar();
getch();
return 0;
}
Para insertar al principio de una lista circular doblemente encadenada:
void insertarPrimero(int x)
Creamos un nodo y guardamos la información:
struct nodo *nuevo;
nuevo=malloc(sizeof(struct nodo));
nuevo->info = x;
Si la lista está vacía luego tanto el puntero sig y ant apuntan a si mismo ya que debe ser circular (y raiz apunta al nodo creado):
if (raiz == NULL)
{
nuevo->sig = nuevo;
nuevo->ant = nuevo;
raiz = nuevo;
}
En caso que la lista no esté vacía disponemos un puntero al final de la lista (el puntero ant del primer nodo tiene dicha dirección):
else
{
struct nodo *ultimo = raiz->ant;
El nodo a insertar lo enlazamos previo al nodo apuntado por raiz:
nuevo->sig = raiz;
nuevo->ant = ultimo;
raiz->ant = nuevo;
ultimo->sig = nuevo;
Finalmente hacemos que raiz apunte al nodo creado luego de haber hecho todos los enlaces:
raiz = nuevo;
Para insertar un nodo al final de la lista:
void insertarUltimo(int x)
El algoritmo es idéntico al método que inserta al principio con la salvedad que no desplazamos raiz con la dirección del nodo creado (es decir al insertar en la posición anterior del primer nodo lo que estamos haciendo realmente es insertar al final de la lista):
void insertarUltimo(int x)
{
struct nodo *nuevo;
nuevo=malloc(sizeof(struct nodo));
nuevo->info = x;
if (raiz == NULL)
{
nuevo->sig = nuevo;
nuevo->ant = nuevo;
raiz = nuevo;
}
else
{
struct nodo *ultimo = raiz->ant;
nuevo->sig = raiz;
nuevo->ant = ultimo;
raiz->ant = nuevo;
ultimo->sig = nuevo;
}
}
Para imprimir la lista ya no podemos disponer un puntero reco que apunte al primer nodo y que se detenga cuando encuentre un nodo que el atributo sig almacene NULL.
void imprimir ()
Si la lista no está vacía disponemos un puntero en el primer nodo y utilizamos un do/while para recorrer la lista. La condición del do/while es que se repita mientras el puntero reco sea distinto a raiz (es decir que no haya dado toda la vuelta a la lista):
void imprimir()
{
if (!vacia()) {
struct nodo *reco = raiz;
do {
printf("%i ",reco->info);
reco = reco->sig;
} while (reco != raiz);
printf("\n");
}
}
Para borrar el nodo de una determinada posición:
void borrar (int pos)
Debemos primero identificar si es el primero de la lista (ya que en este caso se modifica el puntero externo raiz):
if (pos <= cantidad())
{
if (pos == 1)
Si es el primero y el único de la lista hacemos que raiz apunte a NULL y borramos el nodo:
if (cantidad() == 1)
{
free(raiz);
raiz = NULL;
}
Sino disponemos un puntero al final de la lista, avanzamos raiz y enlazamos el último nodo con el segundo de la lista:
struct nodo *bor = raiz;
struct nodo *ultimo = raiz->ant;
raiz = raiz->sig;
ultimo->sig = raiz;
raiz->ant = ultimo;
free(bor);
En caso que queremos borrar un nodo que se encuentra en medio de la lista o inclusive al final debemos recorrer con un for hasta el nodo que queremos borrar y luego disponemos un puntero en el nodo anterior y otro puntero en el nodo siguiente. Seguidamente procedemos a enlazar los nodos:
struct nodo *reco = raiz;
int f;
for (f = 1; f <= pos - 1; f++)
reco = reco->sig;
struct nodo *bor = reco;
struct nodo *anterior = reco->ant;
reco = reco->sig;
anterior->sig = reco;
reco->ant = anterior;
free(bor);
void liberar()
Para borrar todos los nodos de la lista mediante un ciclo repetitivo avanzamos a partir del segundo nodo de la lista mientras el puntero reco sea distinto a la dirección del primer nodo:
void liberar()
{
if (raiz != NULL) {
struct nodo *reco = raiz->sig;
struct nodo *bor;
while (reco != raiz)
{
bor = reco;
reco = reco->sig;
free(bor);
}
free(raiz);
}
}
Cuando salimos de la estructura repetitiva eliminamos el último nodo que nos queda que es el primero de la lista, utilizamos el mismo puntero raiz para eliminarlo:
free(raiz);