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:
#include <iostream>
using namespace std;
class ListaCircular {
private:
class Nodo {
public:
int info;
Nodo *sig;
Nodo *ant;
};
Nodo *raiz;
public:
ListaCircular();
~ListaCircular();
void insertarPrimero(int x);
void insertarUltimo(int x);
bool vacia();
void imprimir();
int cantidad();
void borrar(int pos);
};
ListaCircular::ListaCircular()
{
raiz = NULL;
}
ListaCircular::~ListaCircular()
{
if (raiz != NULL) {
Nodo *reco = raiz->sig;
Nodo *bor;
while (reco != raiz)
{
bor = reco;
reco = reco->sig;
delete bor;
}
delete raiz;
}
}
void ListaCircular::insertarPrimero(int x)
{
Nodo *nuevo = new Nodo();
nuevo->info = x;
if (raiz == NULL)
{
nuevo->sig = nuevo;
nuevo->ant = nuevo;
raiz = nuevo;
}
else
{
Nodo *ultimo = raiz->ant;
nuevo->sig = raiz;
nuevo->ant = ultimo;
raiz->ant = nuevo;
ultimo->sig = nuevo;
raiz = nuevo;
}
}
void ListaCircular::insertarUltimo(int x)
{
Nodo *nuevo = new Nodo();
nuevo->info = x;
if (raiz == NULL)
{
nuevo->sig = nuevo;
nuevo->ant = nuevo;
raiz = nuevo;
}
else
{
Nodo *ultimo = raiz->ant;
nuevo->sig = raiz;
nuevo->ant = ultimo;
raiz->ant = nuevo;
ultimo->sig = nuevo;
}
}
bool ListaCircular::vacia()
{
if (raiz == NULL)
return true;
else
return false;
}
void ListaCircular::imprimir()
{
if (!vacia()) {
Nodo *reco = raiz;
do {
cout<<reco->info <<"-";
reco = reco->sig;
} while (reco != raiz);
cout << "\n";
}
}
int ListaCircular::cantidad()
{
int cant = 0;
if (!vacia())
{
Nodo *reco = raiz;
do {
cant++;
reco = reco->sig;
} while (reco != raiz);
}
return cant;
}
void ListaCircular::borrar(int pos)
{
if (pos <= cantidad())
{
if (pos == 1)
{
if (cantidad() == 1)
{
delete raiz;
raiz = NULL;
}
else
{
Nodo *bor = raiz;
Nodo *ultimo = raiz->ant;
raiz = raiz->sig;
ultimo->sig = raiz;
raiz->ant = ultimo;
delete bor;
}
}
else {
Nodo *reco = raiz;
for (int f = 1; f <= pos - 1; f++)
reco = reco->sig;
Nodo *bor = reco;
Nodo *anterior = reco->ant;
reco = reco->sig;
anterior->sig = reco;
reco->ant = anterior;
delete bor;
}
}
}
void main()
{
ListaCircular *lc = new ListaCircular();
lc->insertarPrimero(100);
lc->insertarPrimero(45);
lc->insertarPrimero(12);
lc->insertarPrimero(4);
cout <<"Luego de insertar 4 nodos al principio\n";
lc->imprimir();
lc->insertarUltimo(250);
lc->insertarUltimo(7);
cout<<"Luego de insertar 2 nodos al final\n";
lc->imprimir();
cout<<"Cantidad de nodos:" <<lc->cantidad() <<"\n";
cout <<"Luego de borrar el de la primer posición:\n";
lc->borrar(1);
lc->imprimir();
cout << "Luego de borrar el de la cuarta posición:\n";
lc->borrar(4);
lc->imprimir();
delete lc;
cin.get();
}
Este proyecto lo puede descargar en un zip desde este enlace : ListaCircular.zip
Para insertar al principio de una lista circular doblemente encadenada:
void insertarPrimero(int x) {
Creamos un nodo y guardamos la información:
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
{
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;
raiz = 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 ListaCircular::insertarUltimo(int x)
{
Nodo *nuevo = new Nodo();
nuevo->info = x;
if (raiz == NULL)
{
nuevo->sig = nuevo;
nuevo->ant = nuevo;
raiz = nuevo;
}
else
{
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 ListaCircular::imprimir()
{
if (!vacia()) {
Nodo *reco = raiz;
do {
cout<<reco->info <<"-";
reco = reco->sig;
} while (reco != raiz);
cout << "\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)
{
delete raiz;
raiz = NULL;
}
Si no disponemos un puntero al final de la lista, avanzamos raiz y enlazamos el último nodo con el segundo de la lista:
Nodo *bor = raiz;
Nodo *ultimo = raiz->ant;
raiz = raiz->sig;
ultimo->sig = raiz;
raiz->ant = ultimo;
delete 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:
Nodo *reco = raiz;
for (int f = 1; f <= pos - 1; f++)
reco = reco->sig;
Nodo *bor = reco;
Nodo *anterior = reco->ant;
reco = reco->sig;
anterior->sig = reco;
reco->ant = anterior;
delete bor;
ListaCircular::~ListaCircular()
Para borrar todos los nodos de la lista en el destructor 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:
Nodo *reco = raiz->sig;
Nodo *bor;
while (reco != raiz)
{
bor = reco;
reco = reco->sig;
delete bor;
}
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:
delete raiz;
}