Ver Mensaje Individual
  #39 (permalink)  
Antiguo 25/06/2006, 09:53
juanpablomonte
 
Fecha de Ingreso: julio-2005
Ubicación: Córdoba
Mensajes: 254
Antigüedad: 19 años
Puntos: 0
Tema: Listas doblemente Enlazadas.
Pregunta: que son y como puedo construir una?
Repuesta:

Las listas doblemente enlazadas, son un tipo de estructura de datos, que se caracteriza por contener unidades compuestas de datos entrelazadas entre si llamadas nodo los cuales contienen dos apuntadores, uno hacia adelante, y el otro hacia atras.( Para entender esto, se debe tener una idea basica de estructuras de datos, punteros, y clases)

Estos Nodos, se enlazan entre ellos, formando una cadena de datos.( identica a las Listas enlazadas simples ya tratadas en estas FAQ's pero que se podra recorrer luego en dos direcciones: de atras hacia adelante y de adelante hacia atras. )


Ejemplo:


Este ejemplo, va a constar de 3 partes. En la primera, laimplementacion de la clase subnodo; en la segunda, la imp. de la clase ListaDoble; y en la ultima un pequeño programita que hace algunas operaciones para testearla.


Primera parte:


Código PHP:


       
public class subnodo {
    private 
int info;
    private 
subnodo prox;
    private 
subnodo ant;

    
subnodo()
    {
info=0;
     
prox=null
     
ant=null;
    }
    
    public 
void setInfo(int x)
    {
info=x;
    }
    public 
void setProx(subnodo p)
    {
prox=p;
    }
    public 
void setAnt(subnodo a)
    {
ant=a;
    }
    
    public 
int getInfo()
    {return 
info;
    }
    public 
subnodo getProx()
    { return 
prox;
        
    }
    public 
subnodo getAnt()
    { return 
ant;
        
    }
    
    public 
String  toString()
    { return (
"\t"+info);   
    }



Segunda Parte, La de la clase generica TDA ListaDoble.


Código PHP:
public class ListaDoble {
    
subnodo frente;

  public 
ListaDoble()
  {
frente=null;
  }
  
public 
void insertarDoble(int  x )
subnodo  p;
  
= new subnodo();
  if(
p!=null)
   { 
p.setInfo(x);
     
p.setProx(frente);
     
     if( 
frente != null)  frente.setAnt(p);
      
frente p;
   }
  else
    
System.out.println("\n Error falta memoria  ");
   
}
public 
void imprimirLista()
 {
   
subnodo p;
   
p=frente;
    
System.out.println(" Impresion de la lista doble de enteros ");
   while (
p!=null)
    { 
System.out.print(" "+p.toString());
      
p=p.getProx();
    }
 
System.out.println( ); 
 
 }
 
 public 
String toString()
 {
String aux=" ";
  
subnodo  p;
   
p=frente;
   while (
p!=null)
    { 
aux=aux+p.toString();
      
p=p.getProx();
    }
  return 
aux;
 
 }

 
public 
void buscar(int x)
{
subnodo  p;
 
p=frente;
 while(
p!=null && p.getInfo()!=x)
  {
p=p.getProx();
  }    
  if(
p!=null)
    {
        if(
p.getProx()!=null)
          
System.out.println("el elemento posterior es "+p.getProx().getInfo());
        else
          
System.out.println("No hay  elemento posterior "); 
          
        if(
p.getAnt()!=null)
          
System.out.println("el elemento anterior es "+p.getAnt().getInfo());
        else
          
System.out.println("No hay  elemento anterior ");  
          
    }
    
}


Tercera y Ultima Parte, la del main method para consumir la clase ListaDoble

Código PHP:
   
class TestListaDoble
   

      public static 
void main (String []arg)
      { 
ListaDoble a=new ListaDoble();  //creacion del objeto
         
int x;
         
int op;
      
         do{
            
System.out.println("1 Carga  ");
            
System.out.println("2 Imprimir  ");
            
System.out.println("3  buscar ");
            
System.out.println("4   ");
            
System.out.println("5   ");
            
System.out.println("6   ");
            
System.out.println("0 fin  ");
            
System.out.print("  Ingrse la opcion  : ");
         
            
op=Leer.datoInt();
         
            switch(
op)
            { 
               case 
1:System.out.println(" Ingreso de datos a la lista ");
                  
System.out.print(" Ingrese un numero entero [0 = FIN]"); 
                  
x=Leer.datoInt();
               
                  while(
x!=0)
                  { 
a.insertarDoble(x);
                     
System.out.print(" Ingrese un numero entero [0 = FIN]"); 
                     
x=Leer.datoInt();
                  }
                  break;
               case 
2:  a.imprimirLista();
                  break;
            
            
               case 
3    :System.out.print(" Ingrese un numero para buscar "); 
                  
x=Leer.datoInt();
                  
a.buscar(x);
               
               
                  break;
            
            }
         
                  
         }while(
op!=0);
      
      }
   } 

Espero que le sirva a alguien, cualquier duda escribanme.

Saludos !