How can I sort a simple Linked List?

Question

How can I sort a simple Linked List?

I would like to know how I could sort my linked simple list whose elements are just numbers, I would like to put an option that sorts me all the elements in my list.

The classes I work with

My Node class

public class Nodo {
    public int dato;
    public Nodo sig;

    public Nodo(int d){
        this.dato=d;
        this.sig=null;
    }
    public Nodo(int d, Nodo n){
        dato=d;
        sig=n;
    }

    public void Enlace(Nodo g)
    {
        sig = g;
    }
}

My class List

public class LISTA {

protected Nodo inicio, fin;
protected Nodo pFound;

public LISTA() {
    inicio = null;
    fin = null;
}

public void AgregInicio(int elem) {
    inicio = new Nodo(elem, inicio);
    if (fin == null) {
        fin = inicio;
    }
}

public void MostrarLista() {
    Nodo recorrer = inicio;
    System.out.println();
    while (recorrer != null) {
        System.out.print("[" + recorrer.dato + "]--->");
        recorrer = recorrer.sig;
    }
}

1

Author: Angel Angel, 2016-05-22

Source

4 answers

score 2 · Answer 1

I think you would be more efficient than using an enhanced bubble, to avoid unnecessary cycles.

The key point is is not just to change the pointers to move through the list, but to change the leagues between the different nodes and identify the previous node.

Assuming this is my LinkedList class.

public class LinkedList {

Materia first, last;
int length;

static LinkedList ll;

And this is the method, note that we have two scenarios for exchanging the nodes and storing the previous node. Here I order it in base to the name attribute.

 public void bubbleSort() {
    if (length > 1) {
        boolean cambio;
        do {
            Materia actual = first;
            Materia anterior = null;
            Materia siguiente = first.siguiente;
            cambio = false;
            while ( siguiente != null ) {
                if (actual.getNombre().compareTo(siguiente.getNombre())>0) {
                    cambio = true;
                    if ( anterior != null ) {
                        Materia sig = siguiente.siguiente;
                        anterior.siguiente = siguiente;
                        siguiente.siguiente = actual;
                        actual.siguiente = sig;
                    } else {
                        Materia sig = siguiente.siguiente;
                        first = siguiente;
                        siguiente.siguiente = actual;
                        actual.siguiente = sig;
                    }
                    anterior = siguiente;
                    siguiente = actual.siguiente;
                } else { 
                    anterior = actual;
                    actual = siguiente;
                    siguiente = siguiente.siguiente;
                }
            } 
        } while( cambio );
    }
}

I hope it will be useful.

score 1 · Answer 2

Move data from LLS GIF] [1

Using this image that I post @Federico, the image explains very well what should be done this great!.

I leave you the code that I implement in my LLS:

public void ordenar()
{
            int t=1,c=1;
            Nodo act = nodo_inicial;/*definimos que el apuntador act esta en el primer nodo*/
            while(act.ap_sig !=null)//Este while cuenta el total de nodos.
            {
                act = act.ap_sig;
                c++;
            }
            /* estas 2 variebles solo son variables que guardaran el valor temporalmente*/
            int tem=0;
            String tem1 ="";
            //aqui se hace el ordenamiento
            do{
                act = nodo_inicial;//aux esta en el primer nodo
                Nodo sig = act.ap_sig;//esta en el siguiente nodo 
                while(act.ap_sig != null)
                {
                    if(act.dato > sig.dato)
                    {
                        tem = act.dato;
                        tem1 = act.palabra;
                        act.dato = sig.dato;
                        act.palabra = sig.palabra;
                        sig.dato = tem;
                        sig.palabra = tem1;
                        //imprimir();
                        act = act.ap_sig;
                        sig = sig.ap_sig;
                    }
                    else
                    {
                        //[1] [3] [2]
                        //    act sig 
                        act = act.ap_sig;
                        sig = sig.ap_sig;
                        //imprimir();
                    }
                }
                t++;
            }while(t<=c);//act.ap_sig != null);
}

score -1 · Answer 3

In your case, that you try to sort your class List (LinkedList) by Number (data that stores each list object, apart from the reference to the next node), the most advisable thing from my point of view and as you have left in a comment @Luigi Mendoza is to use the insertion algorithm.

Insertion algorithm (eye, it's the typical 'generic' example) .

private void insertSort(int[] array)  {
        int i, temp, j;
        for (i = 1; i < array.length; i++) {
            temp = array[i];
            j = i - 1;
            while ( (array[j] > temp) && (j >= 0) ) {
                array[j + 1] = array[j];
                j--;
            }
            array[j + 1] = temp;
        }
    }

In your case, you could always pass as parameter the node of start, and from there, apply the substitution according to the number (node Data) and then change each node you travel from from the start your reference to the next and the previous one (it would be to modify your 'simple linked' list to a 'Doubly Linked'one.

Link to InsertionSort-Wikipedia source (English)

score -3 · Answer 4

There are several types of sorting, one of the most effective for your case I think would be the BubbleSort.

The idea is to leave the larger numbers at the end of the list and it is very easy to implement. I leave you an explanatory image