LISTAS DOBLES
En algunas aplicaciones podemos desear recorrer la lista hacia adelante y hacia atrás, o dado un elemento, podemos desear conocer rápidamente los elementos anterior y siguiente. En tales situaciones podríamos desear darle a cada celda sobre una lista un puntero a las celdas siguiente y anterior en la lista tal y como se muestra en la figura.
Comenzaremos creando la clase Nodo con sus dos enlaces.
/**
*
* @author Jhon
*/
public class Nodo {public int info;
public Nodo sgte;
public Nodo ante;
public Nodo(){
}
public Nodo (int x){
this.info = x;
this.sgte = null;
this.ante = null;
}
}
Como podemos apreciar la clase nodo tiene dos punteros los cuales están inicializados con nullsgte que apunta al ultimo nodo, y ante que apunta a primer nodo.
Operaciones con listas enlazadas:
Se pueden realizar muchas operaciones con estas listas, según sea el caso que se lo requiera aqui les presentamos las mas importantes:
Insertar un elemento al inicio de la lista.
Insertar un elemento al final de la lista.
Insertar después.
Visualizar los elementos de la lista.
Buscar.
Eliminar.
Insertar Inicio: Declaramos el nodo cab(cabezera) y Nodo ptr(puntero), luego los inicializamos a null.
private Nodo cab;
private Nodo ptr;
public ListaDoblementeEnlazada()
{
cab=ptr=null;
}
}
Declaramos un método para conocer si la lista esta vacía;
boolean estaVacia() {
boolean vacia = false;
if (cab == null)
{
vacia = true;
}
return vacia;
}
Método para insertar al inicio.
public ListaDoblementeEnlazada InsertarInicio(int x)
{
Nodo nuevo = new Nodo(x);
if (estaVacia()) {
cab = ptr = nuevo;
} else {
nuevo.sgte =cab;
cab.ante = nuevo;
cab = nuevo;
}
return this;
}
Insertar fin:
public ListaDoblementeEnlazada InsertarFin(int x)
{
Nodo nuevo = new Nodo(x);
if (estaVacia()) {
cab = ptr = nuevo;
} else {
ptr.sgte = nuevo;
nuevo.ante = ptr;
ptr = nuevo;
}
return this;
}
Insertar Después:
public ListaDoblementeEnlazada InsertarDespues(Nodo anterior ,int x)
{
Nodo nuevo = new Nodo(x);
nuevo.sgte = anterior.sgte;
if (anterior.sgte != null)
{
anterior.sgte.ante = nuevo;
}
anterior.sgte = nuevo;
nuevo.ante = anterior;
return this;
}
Imprimir la lista: Se declara un nodo n al cual se le asigna la cabecera de la lista, con la estructura de control while se va imprimiendo todos los nodos asta que la cabecera sea nula.
public void Visualizar()
{
Nodo n;
n = cab;
while (n != null)
{
System.out.print("<- n.info="">");
n = n.sgte;
}
}
Eliminar Nodo:
public void Eliminar(int entrada)
{
Nodo actual;
boolean encontrado = false;
actual = cab;
while ((actual != null) && (!encontrado))
{
encontrado = (actual.info == entrada);
if (!encontrado)
{
actual = actual.sgte;
}
}
if (actual != null){//distingue entre nodo cabecera o resto de la lista
if (actual == cab)
{
cab = actual.sgte;
if (actual.sgte != null)
{
actual.sgte.ante = null;
}
}
else if (actual.sgte != null) // No es el último nodo
{
actual.ante.sgte = actual.sgte;
actual.sgte.ante = actual.ante;
}
else // último nodo
{
actual.ante.sgte = null;
}
if (actual == ptr)
{
ptr = actual.ante;
}
actual = null;
}
}
Buscar Nodo: Se recorre la lista comparando si el valor ingresado(dato), es igual a alguno valore de la lista, en caso de encontrarlo lo retorna.
public Nodo Buscar(int dato)
{
Nodo indice;
for (indice = cab; indice != null; indice = indice.sgte)
{
if (dato == indice.info)
{
return indice;
}
}
return null;
}
Referencia concepto : Leonel Belduma http://iccbeldumaleonel.blogspot.pe/
