UNB/ CS/ David Bremner/ teaching/ cs1083/ java/ InsertionSort2.java
import java.util.LinkedList;
import java.util.ListIterator;
import java.util.Scanner;

public class InsertionSort2{

  public static void  main(String[] args){

    LinkedList<String> list=new LinkedList<>();
    Scanner sc=new Scanner(System.in);

    while ( sc.hasNext() ){
        sortedInsert(sc.next() ,list);
    }

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

    for (String element : list) {
        System.out.println(element);
    }
  }

  static void sortedInsert(String input, LinkedList<String> list){
    ListIterator<String> 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);
  }

}


//@keywords: insertion sort, sort, linked list, week 10