lunes, 25 de julio de 2011

LISTAS

LISTAS



Una lista es un conjunto de elementos con un
orden concreto:
– Puede tener una longitud arbitraria.
– Ofrece la posibilidad de insertar o
eliminar un elemento en cualquier
ubicación.
– Ofrece la posibilidad de recorrer la lista de
forma ordenada, de elemento en elemento.



package estructurasdatosdinamicas;


creación de Nodo




/**
 *
 * @author Administrador
 */
public class Nodo {
    
    public Object Datos;
    public Nodo sgte;
    public Nodo anterior;
    public int CI;
    public int edad;
    
    
    
        public Nodo()
        {
            Datos = sgte = anterior = null;
            
        }
    public Nodo (Object obj)
    {
        Datos = obj;
        sgte = anterior = null;
    }
    public Nodo (Object obj, Nodo sig)
    {
        Datos = obj;
        sgte = sig;
    }
    public void GetDatos(Object cd)
    {
        Datos = cd;
    }
    public void SetAnterior(Nodo ant)
    {
        anterior = ant;
    }
    public void SetSgte(Nodo sg)
    {
        sgte = sg;
    }
    public Nodo SetSgte()
    {
        return sgte;
    }
    public Nodo GetAnteruior()
    {
        return anterior;
    }
}






Lista enlazada



• Las listas enlazadas son como trenes de mercancías.
• Cada elemento que que se va a poner en la lista está
contenido en una instancia de un nuevo tipo de
objeto, llamado enlace, que equivale a un vagón
del tren.
• En una lista enlazada sencilla, el enlace no sólo
contiene el elemento de la lista, sino que
también apunta al siguiente elemento de la
lista, al igual que un vagón de mercancías está
acoplado al siguiente.
• El último enlace de la lista no apunta a nada.


package estructurasdatosdinamicas;


/**
 *
 * @author Administrador
 */
public class ListaEnlazada {
    
    protected String Nombre;
    protected Nodo Primero;
    protected Nodo Ultimo;
    
    public ListaEnlazada(String n)
    {
        Nombre = n;
        Primero = Ultimo = null;
    }
    
    public ListaEnlazada()
    {
        this.Nombre = "Lista";
        
    }
    
    public Boolean Lvacia()
    {
        return Primero ==null;
    }
    
    public String getNombre(){
      
        return Nombre;
    }
    public Nodo getPrimero(){
        
        return Primero;
        
    }


    public Nodo getUltimo(){
    
        return Ultimo;
    }


    public void InsertFrente(Object obj){
           if(Lvacia())
         Primero=Ultimo= new Nodo(obj);
           else
         Primero=new Nodo (obj, Primero);
        
    }
        
    public void InsertAtras(Object obj){
           if(Lvacia())
         Primero=Ultimo= new Nodo(obj);
           else
         Ultimo=Ultimo.sgte=new Nodo (obj);
    
    }
    
    public Object DeleteFrente(){
    
           Object DatoRemovido = null;
           
           if(Lvacia())
               System.out.println("Vacia");
           DatoRemovido= Primero.Datos;
           if(Primero.equals(Ultimo)) 
                 Primero = Ultimo = null;
           else
               Primero = Primero.sgte;
           return DatoRemovido;
    }


    public  Object DeleteAtras(){
        
        Object DatoRemovido = null;
        if (Lvacia()){
            System.out.println("Vacia");
        }
        DatoRemovido = Ultimo.Datos;
        
           if(Primero.equals(Ultimo)){
        
               Primero = Ultimo = null;
        }
           else{
           Nodo Actual = Primero;
               while (Actual.sgte != Ultimo)
                     Actual = Actual.sgte;
               Ultimo = Actual;
               Actual.sgte= null;
           }
           
           return DatoRemovido;
    }
     
    public Object getElementoDeIndice(int Posicion){
        
        if(Lvacia()){
           return null;
        }
        else{
             Nodo actual = Primero;
                  int  cont = 1;
                    while((actual != null)&& (cont < Posicion)){
                      actual = actual.sgte;
                      cont++;
                    }
                    if((actual != null) && (cont == Posicion - 1)){
                           return actual.Datos;
                    }
                    else{
                      return null;
                    }
               }
          }
        
    public void InsertarElementoEnIndice(int Posicion, Object obj){
    Nodo nuevo;
    Nodo actual;
            
              if(Lvacia()){
                 return;
              }
              else{
                  actual = Primero;
                  int cont = 1;
                    
                     while((actual != null) && (cont == Posicion -1)){
                         actual = actual.sgte;
                         cont++;
                     }
                     if ((actual != null) && (cont == Posicion - 1)){
              
               nuevo = new Nodo(obj , actual.sgte);
                 actual.sgte= nuevo;
              
          }
       }
    }


    public Object DeleteElementoDeIndice (int Posicion){
        
        Object DatoRemovido;
        Nodo actual;
        
        if(Lvacia()==true){
         return null;
        }
        else{
            if(Posicion == 1){
                  DatoRemovido=Primero.Datos;
                  Primero=Primero.sgte;
                  return DatoRemovido;
            }
            else{
             actual=Primero;
             int cont=1;
             
             while((actual != null) && (cont<Posicion-1)){
              actual=actual.sgte;
              cont++;
             }
             if((actual !=null)&&(cont==Posicion-1)){
              DatoRemovido=actual.sgte.Datos;
              
              actual.sgte=actual.sgte.sgte;
              return DatoRemovido;
             }
            }
            return null;
        }
    }
    
}


lista doble circular
Las listas doblemente enlazadas son estructuras de datos semejantes a las listas enlazadas simples
La asignación de memoria es hecha al momento de la ejecución. 

En cambio, en relación a la  listas enlazadas simples el enlace entre los elementos se hace gracias a dos punteros.



public class ListaDobleCircular {
  
    private Nodo actual;
    private Nodo ultimo;
    private long numeroElemento;
    private long posicion;
  
    public ListaDobleCircular(){
        actual = ultimo = null;
        numeroElemento = 0;
        posicion = 0;
    }
    public long tamañoLista(){
         return numeroElemento;
    }
  
public void incertarlistadobleE(Object obj){
     Nodo q;
    
      if(ultimo == null){
          ultimo = new Nodo();
          ultimo.anterior = ultimo;
          ultimo.sgte = ultimo;
          ultimo.Datos = obj;
          actual = ultimo;
          posicion = 0;
 }
      else{
     q = new Nodo();
          actual.sgte.anterior = q;
          q.sgte = actual.sgte;
          actual.sgte = q;
          q.anterior = actual;
          q.Datos = obj;
          posicion++;
     if(actual == ultimo){
          ultimo = q;
     }
         actual = q;
        numeroElemento++;
     }
 }
 public Object BorrarListaDobleE(){

     Nodo q;
     Object obj;
    
     if(ultimo == null){
         return null;
     }
       if(actual == ultimo){
           if(numeroElemento == 1){
              obj = ultimo.Datos;
              ultimo = actual=null;
              numeroElemento = 0;
              posicion = 0;
      }
           else{
              actual = ultimo.anterior;
               ultimo.sgte.anterior = actual;
               actual.sgte = ultimo.sgte;
               obj = ultimo.Datos;
               ultimo = actual;
               posicion--;
               numeroElemento--;
             }
       }
          else {
                q = actual.sgte;
                actual.anterior.sgte = q;
                q.anterior = actual.anterior;
                obj = actual.Datos;
                actual = q;
                numeroElemento--;
       }
           return obj;
    }
 public void irSgte(){
     if(posicion < numeroElemento - 1){
         actual = actual.sgte;
         posicion++;
     }
 }
 public void irAnterior(){
     if(posicion > 0){
         actual = actual.anterior;
         posicion--;
     }
 }
 public void irPrincipio(){
     actual = ultimo.sgte;
     posicion = 0;
 }
 public void irFinal(){
     actual = ultimo;
     posicion = numeroElemento - 1;
 }
 public Boolean irAl(long i){
     if(i >= numeroElemento){
         return false;
     }
     irPrincipio();
     for(long n = 0 ; n < i;n++){
         irSgte();
     }
     return true;
 }
 public Object obtener(){
     if(ultimo == null){
         return null;
     }
     return actual.Datos;
 }
 public Object obtenerDe(long i){
     if(!irAl(i)){
         return null;
     }
     return obtener();
 }
 public void Modificar(Object NuevoDato){
     if(ultimo == null){
         return;
     }
     actual.Datos = NuevoDato;
 }
}

Listas enlazadas circulares

En una lista enlazada circular, el primer y el último nodo están unidos juntos. Esto se puede hacer tanto para listas enlazadas simples como para las doblemente enlazadas. Para recorrer una lista enlazada circular podemos empezar por cualquier nodo y seguir la lista en cualquier dirección hasta que se regrese hasta el nodo original. Desde otro punto de vista, las listas enlazadas circulares pueden ser vistas como listas sin comienzo ni fin. Este tipo de listas es el más usado para dirigir buffers para “ingerir” datos, y para visitar todos los nodos de una lista a partir de uno dado.










Artigos Relacionados

0 comentarios:

Publicar un comentario en la entrada