UNB/ CS/ David Bremner/ teaching/ java/ InsertionSort.java
import java.util.*;


public class InsertionSort{

  public static void  main(String[] args){

    LinkedList list=new LinkedList();
    ConsoleReader console=new ConsoleReader(System.in);


    String input;
    while ( (input=console.readLine()) !=null){

      sortedInsert(input,list);
    }


    System.out.println("Sorted:");

    ListIterator iterator=list.listIterator();
    while (iterator.hasNext()){
      System.out.println(iterator.next());
    }
  
  
  }

  //
  static void sortedInsert(String input, LinkedList list){
    ListIterator iterator=list.listIterator();

    
    while (iterator.hasNext() ){

      String element=(String)iterator.next();
      
      if (element.compareTo(input) >0){
        iterator.previous();
        iterator.add(input);
        return;
      }
    }
    list.addLast(input);
  }

}


//