import java.util.LinkedList;
import java.util.Comparator;
import java.util.ListIterator;

public class SortedLinkedList<T extends Comparable<T>> extends LinkedList<T> {
    private Comparator<T> theComparator;
    
    /**
     * Default constructor with natural comparator
     */
    public SortedLinkedList() {
        theComparator = null;
    }
    
    /**
     * Default constructor with comparator parameter
     */
    public SortedLinkedList(Comparator<T> aComparator) {
        theComparator = aComparator;
    }
    
    /**
     * Inserts the specified into this list in it's sorted position
     * @param x is the element inserted
     * @returns true if the list changes
     */
    public boolean add(T x) {
        ListIterator<T> itr = listIterator();
        while( itr.hasNext() ) {
            T save = itr.next();
            // if equal do not add.
            if( compare(x,save) == 0 ) return false;
            // if found the spot back up, add and return
            if( compare(x, save) < 0 ) {
                itr.previous();
                itr.add(x);
                return true;
            } // end if
        } // end while
        // add at end
        itr.add(x);
        return true;
    } // end add
    /**
     * Returns the comparator associated with this sorted list,
     * or null if it uses its elements' natural ordering.
     * @return the comparator associated with this sorted list,
     * or null if it uses its elements' natural ordering.
     */
    public Comparator<T> comparator() {
        return theComparator;
    } // end comparator
    
    private int compare(T left, T right) {
        if( theComparator == null ) {
            return left.compareTo(right);
        } else {
            return theComparator.compare(left,right);
        } // end if
    } // end compare
    
} // end SortedLinkedList