import java.util.*;
import java.lang.*;
import java.io.*;
import java.util.Enumeration; 
 
class Nodo{ 
	public int dato; 
	public Nodo siguiente; 
	public Nodo(int n){ 
	dato=n; 
	siguiente=null; } 
 
} 
 
class Listas
	{
	private Nodo primero;
	private Nodo ultimo;
	public int contador; 
 
	public Listas(){
		this.primero=null;
		this.ultimo=null;}
 
	public boolean siVacia()
	{return(this.primero==null);}
 
	public Listas addFirst(int dato)
	{
	Nodo nuevo= new Nodo(dato);
	if(siVacia())	{
		primero=nuevo;
		ultimo=nuevo;
		nuevo.siguiente=null;	}
	else
	{	primero.siguiente=nuevo;
		primero=nuevo;}
	return this;}
 
	 public Listas addLast(int dato)
	{
	Nodo nuevo= new Nodo(dato);
	if(siVacia()){
		primero=nuevo;
		ultimo=nuevo;
		nuevo.siguiente=null;}
	else
	{ ultimo.siguiente=nuevo;
	ultimo=nuevo; }
	return this;
	}
 
 
	public Nodo deleteFirst()
	{
	Nodo eliminar=null;
	if(siVacia())
		{ System.out.println("\n\nLa lista esta vacia ");
		return null; }
	if(primero==ultimo)
		{primero=null;
		ultimo=null; }
	else
	{
		Nodo actual=ultimo;
		while(actual.siguiente!=ultimo)
		actual=actual.siguiente;
		eliminar=actual.siguiente;
		actual.siguiente=null;
		primero=actual;}
	return eliminar;}
 
	public Nodo deleteLast()
	{
	Nodo eliminar=null;
	if(siVacia())
		{System.out.println("\n\nLa lista esta vacia ");
		return null;}
	if(primero==ultimo)
	{
		primero=null;
		ultimo=null;}
	else
	{
		Nodo actual=primero;
		while(actual.siguiente!=ultimo)
		actual=actual.siguiente;
		eliminar=actual.siguiente;
		actual.siguiente=null;
		ultimo=actual;}
	return eliminar;
	}	 
 
	public void Llenar_arr(int a[])
	{
		int i=0;
		Nodo temp=primero;
		while(temp!=null)
		{a[i] = temp.dato;
		temp=temp.siguiente;i++; }
 
	}
	public void menu()
	{
    System.out.println("BIENVENIDO METODO DE ORDENAMIENTO RADIXSORT CON LISTA ENLAZADA	");
	System.out.println("Introduzca la opcion deseada \n1.-Agregar datos a lista \n2.-Borrar dato\n3.-Acomodar con Radix Sort\n4.-Salir");
	}
 
 
 }
 
 class RadixSort{
 
    public static void radixSort(int[] arr){
        if(arr.length == 0)
            return;
        int[][] np = new int[arr.length][2];
        int[] q = new int[0x100];
        int i,j,k,l,f = 0;
        for(k=0;k<4;k++){
            for(i=0;i<(np.length-1);i++)
                np[i][1] = i+1;
            np[i][1] = -1;
            for(i=0;i<q.length;i++)
                q[i] = -1;
            for(f=i=0;i<arr.length;i++){
                j = ((0xFF<<(k<<3))&arr[i])>>(k<<3);
                if(q[j] == -1)
                    l = q[j] = f;
                else{
                    l = q[j];
                    while(np[l][1] != -1)
                        l = np[l][1];
                    np[l][1] = f;
                    l = np[l][1];
                }
                f = np[f][1];
                np[l][0] = arr[i];
                np[l][1] = -1;
            }
            for(l=q[i=j=0];i<0x100;i++)
                for(l=q[i];l!=-1;l=np[l][1])
                        arr[j++] = np[l][0];
        }
    }
}
 
class Radixsort_Lista{
 public static void main(String [] args )
 {
	int i,aux=1,resp,num,contador=0,resp_case;
	Listas Objetox = new Listas();
	RadixSort Objetoy = new RadixSort();
	Scanner Memoria = new Scanner(System.in);
 
	while(aux == 1){
	Objetox.menu();
	resp_case = Memoria.nextInt();
	switch (resp_case)
	{
	case 1:contador++;
			System.out.println("Donde desea ingresar 1.-Primero/2.-Ultimo");
			resp = Memoria.nextInt();
			System.out.println("Ingrese el numero");
			num =Memoria.nextInt();
			if (resp == 1)
			Objetox.addFirst(num);
			else
			Objetox.addLast(num);
			break;
	case 2:System.out.println("Donde desea borrar 1.-Primero/2.-Ultimo");
			resp = Memoria.nextInt();
			if (resp == 1)
			{Objetox.deleteFirst();
			contador--;}
			else
			{Objetox.deleteLast();
			contador--;}
			break;
	case 3:int[] arr = new int[contador];
			Objetox.Llenar_arr(arr);
			Objetoy.radixSort(arr);
			System.out.print("\nOrdenados: ");
			for(i=0;i<arr.length;i++)
            System.out.print(arr[i] + "->");
			System.out.print("\n");break;
    case 4:aux = 2;break;
	default: System.out.println("Error en la digitacion"); break;
 }
 }
 }
}