miércoles, 20 de julio de 2011

LISTAS DOBLEMENTE ENLAZADAS Y PILAS EN JAVA

Listas doblemente enlazadas
Una lista doblemente enlazada es una lista enlazada de nodos, donde cada nodo tiene un par de campos de enlace. Un campo de enlace permite atravesar la lista hacia adelante, mientras que el otro permite atravesar la lista haca atrás. Para la dirección hacia adelante, una variable de referencia contiene una referencia al primer nodo. Cada nodo se enlaza con el siguiente mediante el campo de enlace next, excepto el último nodo, cuyo campo de enlace nextcontiene null para indicar el final de la lista (en direccion hacia adelante). De forma similar, para la dirección contraria, una variable de referencia contiene una referencia al último nodo de la dirección normal (hacia adelante), lo que se interpreta como el primer nodo.

EJEMPLO:
CLASE NODO

public class Nodo {
  int dato;
Nodo adelante;
Nodo atras;
public Nodo(int entrada)
{
dato = entrada;
adelante = atras = null;
}
public int getDato()
{
return dato;
}public Nodo getEnlace()
{
return adelante;
}public void setEnlace(Nodo adelante)
{
this.adelante = adelante;
}
}

CLASE LISTA DOBLE

public class ListaDoble {
    Nodo cabeza;
public ListaDoble()
{
cabeza = null;
}public ListaDoble insertarCabezaLista(int entrada)
{
Nodo nuevo;
nuevo = new Nodo(entrada);
nuevo.adelante = cabeza;
if (cabeza != null )
cabeza.atras = nuevo;
cabeza = nuevo;
return this;
}public ListaDoble insertaDespues(Nodo anterior, int entrada)
{
Nodo nuevo;
nuevo = new Nodo(entrada);
nuevo.adelante = anterior.adelante;
if (anterior.adelante !=null)
anterior.adelante.atras = nuevo;
anterior.adelante = nuevo;
nuevo.atras = anterior;
return this;
}public void eliminar (int entrada)
{
Nodo actual;
boolean encontrado = false;
actual = cabeza;
// Bucle de búsqueda
while ((actual != null) && (!encontrado))
{
/* la comparación se realiza con el método equals()...,
depende del tipo Elemento */
encontrado = (actual.dato == entrada);
if (!encontrado)
actual = actual.adelante;
}// Enlace de nodo anterior con el siguiente
if (actual != null)
{
//distingue entre nodo cabecera o resto de la lista
if (actual == cabeza)
{
cabeza = actual.adelante;
if (actual.adelante != null)
actual.adelante.atras = null;
}else if (actual.adelante != null)
// No es el último nodo
{
actual.atras.adelante = actual.adelante;
actual.adelante.atras = actual.atras;
}else
// último nodo
actual.atras.adelante = null;
actual = null;
}
}public void visualizar()
{
Nodo n;
int k = 0;
n = cabeza;
while (n != null)
{
System.out.print(n.dato + "");
n = n.adelante;
k++;
System.out.print( (((k%10 != 0)&& (n!= null)) ? " " : "\n"));
}
}
}

MAIN PRINCIPAL

public class ListaDoble {
    Nodo cabeza;
public ListaDoble()
{
cabeza = null;
}public ListaDoble insertarCabezaLista(int entrada)
{
Nodo nuevo;
nuevo = new Nodo(entrada);
nuevo.adelante = cabeza;
if (cabeza != null )
cabeza.atras = nuevo;
cabeza = nuevo;
return this;
}public ListaDoble insertaDespues(Nodo anterior, int entrada)
{
Nodo nuevo;
nuevo = new Nodo(entrada);
nuevo.adelante = anterior.adelante;
if (anterior.adelante !=null)
anterior.adelante.atras = nuevo;
anterior.adelante = nuevo;
nuevo.atras = anterior;
return this;
}public void eliminar (int entrada)
{
Nodo actual;
boolean encontrado = false;
actual = cabeza;
// Bucle de búsqueda
while ((actual != null) && (!encontrado))
{
/* la comparación se realiza con el método equals()...,
depende del tipo Elemento */
encontrado = (actual.dato == entrada);
if (!encontrado)
actual = actual.adelante;
}// Enlace de nodo anterior con el siguiente
if (actual != null)
{
//distingue entre nodo cabecera o resto de la lista
if (actual == cabeza)
{
cabeza = actual.adelante;
if (actual.adelante != null)
actual.adelante.atras = null;
}else if (actual.adelante != null)
// No es el último nodo
{
actual.atras.adelante = actual.adelante;
actual.adelante.atras = actual.atras;
}else
// último nodo
actual.atras.adelante = null;
actual = null;
}
}public void visualizar()
{
Nodo n;
int k = 0;
n = cabeza;
while (n != null)
{
System.out.print(n.dato + "");
n = n.adelante;
k++;
System.out.print( (((k%10 != 0)&& (n!= null)) ? " " : "\n"));
}
}
}
//FIN 

PILAS.-  UNA PILA ES UNA ESTRUCTURADE DATOS QUE PERMITE ALMACENAR DATOS DEL MODO QUE EL ULTIMO DATO EN ENTRAR A LA PILA ES EL PRIMERO EN SALIR,COMO POR  EJEMPLO : UNA PILA DE PLATOS ,UNA PILA DE MONEDAS ETC. Y SE PUEDEN INSERTAR Y ELIMINAR SOLO POR UN EXTREMO(SUPERIOR) Y SOLO SE PUEDEN ELIMINAR EN UN ORDEN INVERSO AL QUE SE INSERTA EN LA PILA.



CLASE NODO

public class Nodo {

   //Atributos del la clase nodo
   Object Dato;
   Nodo Sig;
   //Constructor del nodo para crear un objeto
   public Nodo(Object Valor){
   Dato=Valor;
   Sig=null;
   }
   //Constructor del nodo para crear un objeto del siguiente nodo
   public Nodo(Object Valor,Nodo Sign){
   Dato=Valor;
   Sig=Sign;
   }

}

CLASE PILA

public class Pila extends Lista{
    //Atributo Nombre de la clase pila
    String Nombre;
    //Contructor con argumento de la clase pila
    public Pila(String n){
    Nombre=n;
    }
    //Ingresando nombre a la clase pila
    public Pila(){
    this("Pila");
    }
    //Metodo para insertar en la clase pila
    public void Pilar(Object Elem){
    Iposterio(Elem);
    }
    //Metodo de mostrar los datos de una pila
    public void MostrarP(){
    Nodo Actual=Pri;
    if(ListaVacia()){
    System.out.println("La "+Nombre+" esta vacia");
    }
    else{
    System.out.println("La "+Nombre+": ");
    while(Actual!=null){
    System.out.print("|"+Actual.Dato+"||");
    Actual=Actual.Sig;
    }
    System.out.println();
    }
    }
    //Metodo para eliminar un elemento de la pila
    public void DPilar(){
    Eposterior();
    }

}
//fin





3 comentarios:

  1. Hola man, mira pero me parece que tu main es lo mismo que tu metodo ListaDoble.

    ResponderEliminar
  2. primero que nada que buena aportacion gracia y tengo una pregunta ese es el main de la pila doblemente enlazada? porque creo que es la copia de la clase pila

    ResponderEliminar
  3. interesante, pero el verdadero reto de hacer estructura de datos, radica en que se debería hacer con generics(T) así el que utiliza la estructura de datos elije el tipo de dato que almacenara en la colección...

    ResponderEliminar