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.
RESOLVEMOS LAS LISTAS DOBLEMENTE ENLAZADAS
Programa:
public class ListaCircular {
class Nodo {
int info;
Nodo ant,sig;
}
private Nodo raiz;
public ListaCircular () {
raiz=null;
}
public void 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;
}
}
public void 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;
}
}
public boolean vacia ()
{
if (raiz == null)
return true;
else
return false;
}
public void imprimir ()
{
if (!vacia()) {
Nodo reco=raiz;
do {
System.out.print (reco.info + "-");
reco = reco.sig;
} while (reco!=raiz);
System.out.println();
}
}
/* Reco se usa para el recorrido*/
public int cantidad ()
{
int cant = 0;
if (!vacia()) {
Nodo reco=raiz;
do {
cant++;
reco = reco.sig;
} while (reco!=raiz);
}
return cant;
}
public void borrar (int pos)
{
if (pos <= cantidad ()) {
if (pos == 1) {
if (cantidad()==1) {
raiz=null;
} else {
Nodo ultimo=raiz.ant;
raiz = raiz.sig;
ultimo.sig=raiz;
raiz.ant=ultimo;
}
} else {
Nodo reco = raiz;
for (int f = 1 ; f <= pos - 1 ; f++)
reco = reco.sig;
Nodo anterior = reco.ant;
reco=reco.sig;
anterior.sig=reco;
reco.ant=anterior;
}
}
}
public static void main(String[] ar) {
ListaCircular lc=new ListaCircular();
lc.insertarPrimero(100);
lc.insertarPrimero(45);
lc.insertarPrimero(12);
lc.insertarPrimero(4);
System.out.println("Luego de insertar 4 nodos al principio");
lc.imprimir();
lc.insertarUltimo(250);
lc.insertarUltimo(7);
System.out.println("Luego de insertar 2 nodos al final");
lc.imprimir();
System.out.println("Cantidad de nodos:"+lc.cantidad());
System.out.println("Luego de borrar el de la primer posición:");
lc.borrar(1);
lc.imprimir();
System.out.println("Luego de borrar el de la cuarta posición:");
lc.borrar(4);
lc.imprimir();
}
}
Para insertar al principio de una lista circular doblemente encadenada:
public void insertarPrimero(int x) {
Creamos un nodo y guardamos la información:
Nodo nuevo=new 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 {
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:
public 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):
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.
public 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):
if (!vacia()) {
Nodo reco=raiz;
do {
System.out.print (reco.info + "-");
reco = reco.sig;
} while (reco!=raiz);
System.out.println();
}
}
Para borrar el nodo de una determinada posición:
public 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:
if (cantidad()==1) {
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:
} else {
Nodo ultimo=raiz.ant;
raiz = raiz.sig;
ultimo.sig=raiz;
raiz.ant=ultimo;
}
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 anterior = reco.ant;
reco=reco.sig;
anterior.sig=reco;
reco.ant=anterior;