Ordenar Listas enlazadas.

Ordenar Listas enlazadas.

Figura numero 6

Para ordenar una lista enlazada se debe tener en cuenta tres variables aparte de la que apunta al primer nodo de la lista,  variables de tipo nodo una llamada actual que inicialmente apunta al primer nodo de la lista, otra anterior que estará apuntando al nodo  anterior al cual apunta actual, y otro nodo llamado fin que estará apuntando al ultimo nodo de la lista. Para realizar el ordenamiento como aparece en la Figura  numero 5 se bebe realizar mediante el siguiente algoritmo de ordenamiento.

If(p!=null){                                                                                                                                                  Nodo r =p;                                                                                                                                             Nodo s = null; 

while(r!null && r.getDato()<x){ 

s=r; r = r.getSig(); }                                                                                                                            if(r!=null){

if(r==p){ 

 p= new Nodo(x,p); } else {                                                                                                               s.setSig(new Nodo(x,r)); }  

} else {                                                                                                                                                    q.setSig(new Nodo(x,null));                                                                                                              q=q.getSig();  }   

}else {                                                                                                                                                 p=q=new Nodo (x,null); }

Explicando un poco el algoritmo primero se debe asegurar que la lista no este vacía. Luego se le asigna a cada variable su función en el algoritmo la variable actual es r, la variable anterior es s, y la variable fin es q. se realiza un while buscando que dato que esta almacenados en los nodos es menor del que se quiere insertar.  luego se va preguntando en que parte quedo actual osea la variable r para si realizar el ordenamiento.

En la figura numero 5 se muestra primero una variable de referencia p apuntando al primer nodo de la lista, y se encuentran los datos no ordenados, en la segunda lista es misma de la primero siendo que esta ya se encuentra ordenada.

Logre aprender en esta clase la forma mas adecuada y fácil de ordenar una lista enlazada, y lo importante que son ahora en adelante las otras variables declaradas.