import java.io.*;

class SortCharListsA1
{
// Shows sort of lists using destructive insert

 public static void main(String[] args) throws IOException
 {
  BufferedReader in = new BufferedReader(
                        new InputStreamReader(System.in));
  CharListA L1=null,L2=null;
  char ch1,ch2;
  try {
       System.out.print("Enter list of characters: ");
       L1 = CharListAIO.read(in);
      }
  catch(ListFormatException e)
      {
       System.out.println("Error: "+e.getMessage());
      }
  System.out.print("The list is: ");
  CharListAIO.print(L1);
  System.out.println();
  L2=sort(L1);
  System.out.print("The list after sorting is: ");
  CharListAIO.print(L2);
  System.out.println(); 
 }

 public static CharListA sort(CharListA L)
 {
  CharListA S = new CharListA('\0',null);
  for(CharListA ptr=L; ptr!=null; ptr=ptr.tail)
     insert(ptr.head,S);
  return S.tail;
 }

 public static void insert(char ch,CharListA L)
 {
  CharListA ptr;
  for(ptr=L;ptr.tail!=null&&ptr.tail.head<ch;ptr=ptr.tail);
  ptr.tail = new CharListA(ch,ptr.tail);
 }

}