LISTAS DOBLES ENLAZADAS

Este tipo de listas son muy semejantes a las listas enlazadas simples con la diferencia, de que cada nodo posee dos enlaces, el primer puntero  apunta al nodo anterior o null si es el primero y otro al nodo siguiente, o null si es el ultimo nodo.
Creación de la clase Nodo
Comenzaremos creando la clase Nodo con sus dos enlaces.
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 null sgte 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;
    }
Ejercicio:
Realizar un programa que permita crear una lista doblemente enlazada para un tipo de dato entero, que guarde en un archivo y a continuación realice las siguientes actividades.

  1. Insertar un elemento entero al inicio de la lista.
  2. Insertar un elemento al final de la lista.
  3. Insertar después.
  4. Visualizar los elementos de la lista.
  5. Buscar.
  6. Eliminar.
  7. Obtener el mayor valor.
  8. Ordenar la lista doblemente enlazada.
  9. Contabilizar los elementos de la lista.
  10. Cantidad de números perfectos.
  11. Cantidad de números primos.
  12. Guardar en un archivo. 



Publicadas por

No hay comentarios.:

Publicar un comentario

Suscribirse a: Comentarios de la entrada (Atom)