ESTRUCTURAS DINAMICAS

 Son estructuras dinámicas: porque  se asigna memoria para los elementos de la lista en la medida que es necesario.
Cada elemento se almacena en una variable dinámica denominada nodo.
En la lista simplemente enlazada, cada nodo apunta al nodo que contiene el elemento siguiente. Las listas enlazadas permiten inserciones y eliminación de nodos en cualquier punto de la lista en tiempo constante (suponiendo que dicho punto está previamente identificado o localizado), pero no permiten un acceso aleatorio. Existen diferentes tipos de listas enlazadas: Lista Enlazadas  Simples, Listas Doblemente Enlazadas, Listas Enlazadas Circulares y Listas Enlazadas Doblemente Circulares.
La lista enlazada básica es la lista enlazada simple la cual tiene un enlace por Nodo. Este enlace apunta al siguiente nodo en la lista, o al valor NULL o a la lista vacía, si es el último nodo.
Una lista enlazada simple contiene dos valores: el valor actual del nodo y un enlace al siguiente nodo.
Listas Simples Enlazadas
Nuestra estructura de datos tendrá dos campos. Vamos a mantener las variables PrimerNodos que siempre apunta al primer nodo de tal lista, o nulo para la lista vacía.

registro Nodo {

dato    // El dato almacenadoenel nodo.                                                                                 

next     // Una referencia al nodo siguiente, nulo para el último nodo
  }
registro Lista {
Nodo PrimerNodo // Apunta al primer nodo de la lista; nulo para lalista vacía
  }
El recorrido en una lista enlazada es simple, empezamos por el primer nodo y pasamos al siguiente hasta que la lista llegue al final.
nodo := list.PrimerNodo
while nodo not null {
nodo:= nodo.next
  }
El siguiente código inserta un elemento a continuación de otro en una lista simple.

función  insertDespues(Nodo nodo, Nodo newNodo) {
newNode.next := nodo.next
nodo.next := newNodo
 }

Insertar al principio de una lista requiere una función por separado. Se necesita actualizar PrimerNodo.

 función remueveComienzo (List list, Nodo newNodo) {
newNodo.next := list.firstNodo
list.firstNodo := newNodo
}
De forma similar, también tenemos funciones para borrar un nodo dado o para borrar un nodo del principio de la lista.

funcion cambieDespues(Nodo nodo) {
obsoleteNodo := nodo.next
nodo.next := nodo.next.next
destroy obsoleteNodo
  }
 función remueveComienzo (List list) {
obsoleteNodo := list.firstNodo
list.firstNodo := list.firstNodo.next
destroy obsoletoNodo
}
Advertimos que “Borrar Principio pone Primer Nodo” a nulo cuando se borra el último elemento de la lista.

LISTAS ENLAZADAS

Es  una secuencia de elementos a una temática que pueden estar ordenados  o no ordenados. Es un vector dinámico.
Las listas ordenadas no son estructuras infinitas.
¿Qué es una lista enlazada?
Es una estructura  de datos dinámicos formado por un conjunto de nodos conectados a través de un enlace (sig).
Algo que siempre debe hacerse al realizar una lista o  crear códigos es:
ESTRUCTURAS DINAMICAS

Seguir  tres pasos importantes 1.- análisis. 2.- diseño. 3.- implementación


Lista Simple

package listassimples;
public class ListaSimple {
    private Nodo prim;
    private Nodo ult;
    private String Nombre;
public  ListaSimple(){
    prim=ult=null;
    Nombre="";
  }
public  ListaSimple(String n){
    prim=ult=null;
    Nombre=n;
   }
public boolean ListaVacia(){
    return prim==null;
  }
}

Eliminar

1.- análisis.

Dato=DatoAremover.
Primero es sustituido por el siguiente= prim.sig;
Retornar = return DatoAremover.

2.- Algoritmo.
DatoAremover=primero.datos;
Actual=pri;
Prim=prim.sig;
Actual.sig=null;
return DatoAremover;
}

3.- Implementación.
public Object DelFrente(){
    if(ListaVacia())
        Object DatoAremover=prim.datos;
    if(prim.equals(ult))
        prim=ult==null;
    else {
        Nodoactual=prim;
        prim=prim.sig;
        actual.sig=null;
    }
    return  DatoAremover;
    }


Inserciones

OPERACIONES:

 
INSERTAR, ELIMINAR, BUSCAR, ORDENAR.
•    Insertar al frente:
public lista (String n){
Nobre=n;
Prim=ult=null;
public boolean Listavacia(){
return (prim==null);

1.- análisis.
Lista vacía.
Lista_n null == prim,ult;

2 Algoritmo.
Crear Nodo  lista.
3 Implementación.
public void insertFrente(Objet obj){
if(Lvacia())
primero=ultimo=new Nodo(obj);
else
primero=new Nodo(obj,primero);// Recorre un puesto
}

•    Insertar atrás:
public void InsertarAtraz(Objet obj){
If(Lvacia())
Primero=ultimo=new Nodo(obj);
else
       ultimo=ultimo.sgte=new Nodo(obj){
}

Eliminar
•    Eliminar frente
public Object eliminarfrente(){
     Object  DatoRemovido=null;
      if(Listavacia())
         DatoRemovido=Primero.datos;
        if(Primero.Equals(ultimo))
           Primero=Ultimo=null;
else
            primero =primero.sgte;
 return  DatoRemovido;
} 

•    Eliminar atraz

public Object eliminarAtraz(){
     Object  DatoRemovido=null;
      if(Listavacia()){
         DatoRemovido=Ultimo.datos;
        if(Primero.Equals(ultimo))
           Primero=Ultimo=null;
}
else{
     Nodo Actual=Primero;
     while (Actual.sigte ¡=Ultimo)
          Actual= Actual.sigte;
Ultimo=Actual;
Actual.sigte=null;
}
return DatoRemovido;
}

Para eliminar en una posición cualquiera

public Objet eliminarPosicion(int  pos){
if(Listavacia())
return vacio;
if(pos==1)
If(pos=NroElementos)

else{
        Objet DatoAremover;
      if(pPrimero.equals(Ultimo))
        Pimero=Ultimo=null;
return  DatoAremover
}
else{
     Nodo Actual=Primero;
for(int i=1;i<pos;i++)
   Actual =Actual.sigte;
Nodo Aborrar=Actual.sigte;
DatoAremover=(Actual.sigte).dato;

Actual.sigte=(Actual.sigte).sigte;
  Aborrar.sigte;
Aborrar.sigte=null;
return DatoAborrar;
}
}
}
Modificaciones

1   analisis         2  diseño del algoritmo       3   implementacion

Modificaciones en una posición.
•    Modificación al frente:
public void  Update Frente(Object Objnew){
if(ListaVacia())

else
Primero.dato=objnew;
•    Modificar último
public void updatepost(Object ob){
if(ListaVacia())
else
Ultimo.dato=ob;
 
•    Modificar la posición  n

Public void  updatepos(Object obnew int pos){
       if(ListaVacia())
      if(pos==1)   Updatefrente(obnew);
if (pos==nroelent)
updatepost(obnew);
else{
      Nodo Actual=Primero;
for(int i=1;i<pos;i++)
      Actual=Actual.sig;
Actual=Actual.sig;
Actual.datpo=obnew;
  }
}
public void MostrarLista(){
Nodo Actual=Primero;
while (Actual ¡=null)
JOptionPane………(ActualDato);
Actual=Actual.sig;
}
}


EJEMPLO SIMPLE:    (Ordenar)

 Un  programa  donde pueda ordenar de menor a mayor o de mayor a menores claves.

package nuevonodo;

public class Nodo2 {
    public int clave;
    public String nombre;
    public Nodo2 sig;

    public Nodo2(int cl, String n){
        clave =cl;
        nombre=n;
        sig=null;
       }
    public void mostrarNodo(){
        System.out.println("   clave  :    "+clave+"   Nombre  :  "+nombre);
     }

}
public class ListaOrdenada {
    private Nodo2 inicio;
    ListaOrdenada(){
        inicio=null;
        }
    public boolean vacia(){
        return (inicio==null);
   }
    public void insertar(int clave,String nombre){
        Nodo2 nuevoNodo=new Nodo2(clave,nombre);
        Nodo2 anterior=null;
        Nodo2 actual = inicio;
        boolean pasado=false;
        while (actual !=null && !pasado){
            if(clave>actual.clave){
            anterior=actual;
            actual=actual.sig;
      }
        else
            pasado=true;
    }
        if(anterior==null){
            inicio=nuevoNodo;
        } else
                anterior.sig=nuevoNodo;
                nuevoNodo.sig=actual;
        }
    public Nodo2 borrar(int clave){
        Nodo2 anterior =null;
        Nodo2 actual=inicio;
        boolean encontrado=false;
        while (actual !=null && !encontrado){
            if(clave==actual.clave)
                encontrado = true;
             else
            {
                anterior=actual;
                actual=actual.sig;
        }
}
    if(encontrado)
        if(anterior==null)
            inicio=actual.sig;
            else
  {
           anterior.sig=actual.sig;
           return (actual);
            }
        return null;
  }
    public void buscar(int clave){
        Nodo2 anterior=null;
        Nodo2 actual=inicio;
        boolean encontrado=false;
        while(actual !=null&&!encontrado){
            if (clave==actual.clave)
                encontrado =true;
            else
                anterior=actual;
                actual=actual.sig;
            }
            if(encontrado)
                actual.mostrarNodo();
            else
                System.out.println("no está");
        }
    public void MostrarLista(){
        Nodo2 actual=inicio;
        while (actual != null){
            actual.mostrarNodo();
            actual=actual.sig;
        }
    }
 }
public class Prueba2 {
    public static void main(String [] args){
       ListaOrdenada unaLista = new ListaOrdenada();
        unaLista.insertar(  4, "   Pablo");
        unaLista.insertar(  1, "   Julio");
        unaLista.insertar(  8, "   Ramón");                claves  desordenados
        unaLista.insertar( 10, "  Ramiro");
        unaLista.insertar(  2, "   Pedro");
        unaLista.MostrarLista();

    }
}
Visualizamos:
   Clave:    1     Nombre:     Julio
   Clave:    2     Nombre:     Pedro
   Clave:    4     Nombre:     Pablo              Claves  ordenados
   Clave:    8     Nombre:     Ramón
   Clave:    10   Nombre:    Ramiro

////////////////////////////////////////////////////////////////////////////////////////////////////