// Listas.java
// Programa de Listas encadenadas representadas con arreglos
// Compilar: javac Listas.java
// Ejecutar:  java Listas
// =====================================================
import java.io.*;

public class Listas {
 public static class ClaseListas { // Declaracion de la clase de Listas
  static char dato[]=new char[100]; //Declaracion del arreglo para los datos de tipo char

  static int sn[]=new int[100]; //Declaracion del arreglo para el indicador del siguiente nodo
  static int apui, top;  // Apuntador inicial y cantidad de datos en la lista
  
  ClaseListas() { // Constructor de la ClaseListas
   apui=-1;
   top=0;
   System.out.println("Lista enlazada inicializada !!!");
   System.out.println("apui="+apui);
   System.out.println("top  ="+top);
  }

  public static void Mostrar() {
   int i=0;
   System.out.println("\n\n<<< MOSTRAR ESTRUCTURA >>>");
   if(apui==-1) System.out.println("\nLista enlazada vacia !!!\n");
   System.out.println("posicion  dato       sn");
   System.out.println("---------------------------");
   for(i=0;i<top;i++) {
    System.out.println(i+"       |   "+dato[i]+"      |   "+sn[i]);
   }
   System.out.println("\napui="+apui);
   System.out.println("top="+top);
  } 
  public static void Insertar(char elemento) {
   int i=0, ant=0;
   if(apui==-1) { //Alta en Lista vacia
    System.out.println("Insertar dato en lista vacia ...");
    apui=top;
    dato[top]=elemento;
    sn[top]=-1;
    top++;
    return;
   }
   i=apui;
   do {
        if(dato[i]==elemento) {
         System.out.println("Duplicado !!!");
         return;
        }
        if(elemento<dato[i]) {
         if(i==apui) { //Alta al principio
           System.out.println("Insertando el dato menor de todos ...");
          dato[top]=elemento;
          sn[top]=apui;
          apui=top;
          top++;
          return;
         } else {
          System.out.println("Alta intermedia ...");
          dato[top]=elemento;
          sn[top]=sn[ant];
          sn[ant]=top;
          top++;
          return;
         }
        }
        ant=i;
        i=sn[i];
   }while(i!=-1);
   System.out.println("Alta al final ...");
   dato[top]=elemento;
   sn[top]=-1;
   sn[ant]=top;
   top++;
   return;
  }
 }
 
 
 static ClaseListas Lista=new ClaseListas(); // Declaracion del objeto Lista

 
 public static void main(String args[]) throws IOException { //Funcion principal

  int op=0;
  do {
       System.out.println("\n\n<<< LISTAS ENLAZADAS >>>");
       System.out.println("1.- Altas");
       System.out.println("2.- Mostrar estructura");
       System.out.print("Opcion? ---> ");
       op=getInt();
       switch(op) {
        case 1 : Altas(); break;
        case 2 : Lista.Mostrar();  break;
       }
  }while(op!=0);
 }
 
 public static void Altas() throws IOException {
  char dato;
  System.out.println("\n\n<<< ALTAS >>>");
  System.out.print("Dato a insertar ---> ");
  dato=getChar();
  Lista.Insertar(dato); //Invocar el metodo Insertar del objeto Lista
 }
 
      public static String getString() throws IOException { //Funcion para capturar una cadena con el teclado

            InputStreamReader isr = new InputStreamReader(System.in);
            BufferedReader br = new BufferedReader(isr);
            String s = br.readLine();
            return s;
        }    
        
        public static int getInt() throws IOException { // Funcion para capturar un entero con el teclado

            String s = getString();
            return Integer.parseInt(s);
        }    
 
        public static char getChar() throws IOException { //Funcion para capturar un caracter con el teclado

         String s=getString();
         return s.charAt(0);
        }
}