public class LinkedList3<T extends Comparable<T>>
{
    private class Node<T>
    {
        private T data;
        private Node<T> link;

        public Node( )
        {
             data = null;
             link = null;
        }

        public Node(T newData, Node<T> linkValue)
        {
            data = newData;
            link = linkValue;
        }
     }//End of Node<T> inner class

    private Node<T> head;

    public LinkedList3( )
    {
        head = null;
    }

//***********ADDSORTED METHOD**********************/

    public void addSorted(T itemData){    

        if(head == null){//If there is no head 
            head = new Node<T>(itemData, null);//Then Create a head
        }else{
            if (head.data.compareTo(itemData) >=0){//If the parameter number is smaller than the head data
                head = new Node<T>(itemData, head);//Then just create a Node with that data and make it the new head
            }else{
                Node<T> current = head;//Sets the current pointer to the head node
                Node<T> previous = null;

                while (current.link !=null && current.data.compareTo(itemData) <= 0){//As long as the pointer does not fall off the end of the list AND the next pointer data is larger than the new data
                    previous = current;//get a copy of the current pointer to be used later
                    current = current.link;//keeps pointer moving down the list
                }

                if(current.data.compareTo(itemData) >= 0){
                    previous.link = new Node<T>(itemData,current);//Inserts a Node before the next largest number compared to itemData
                }else{
                    current.link = new Node<T>(itemData, null);//Adds a Node at the very end if it is the largest
                }
            }
        }
        
    }

    /**
     Adds a node at the start of the list with the specified data.
     The added node will be the first node in the list.
    */
    public void addToStart(T itemData)
    {
        head = new Node<T>(itemData, head);
    }

    /**
     Removes the head node and returns true if the list contains at least
     one node. Returns false if the list is empty.
    */
    public boolean deleteHeadNode( )
    {
        if (head != null)
        {
            head = head.link;
            return true;
        }
        else
            return false;
    }

    /**
     Returns the number of nodes in the list.
    */
    public int size( )
    {
        int count = 0;
        Node<T> position = head;
        while (position != null)
        {
            count++;
            position = position.link;
        }
        return count;
    }

    public boolean contains(T item)
    {
        return (find(item) != null);
    }

    /**
     Finds the first node containing the target item, and returns a
     reference to that node. If target is not in the list, null is returned.
    */
    private Node<T> find(T target)
    {
        Node<T> position = head;
        T itemAtPosition;
        while (position != null)
        {
            itemAtPosition = position.data;
            if (itemAtPosition.equals(target))
                return position;
            position = position.link;
        }
        return null; //target was not found
    }

    /**
     Finds the first node containing the target and returns a reference
      to the data in that node. If target is not in the list, null is returned.
    */
    public T findData(T target)
    {
        return find(target).data;
    }

    public void outputList( )
    {
        Node<T> position = head;
        while (position != null)
        {
            System.out.print(position.data + " ");
            position = position.link;
        }
        System.out.println("");
    }

    public boolean isEmpty( )
    {
        return (head == null);
    }

    public void clear( )
    {
        head = null;
    }

   /*
    For two lists to be equal they must contain the same data items in
    the same order. The equals method of T is used to compare data items.
   */
   public boolean equals(Object otherObject)
    {
        if (otherObject == null)
            return false;
        else if (getClass( ) != otherObject.getClass( ))
            return false;
        else
        {
            @SuppressWarnings("unchecked")
            LinkedList3<T> otherList = (LinkedList3<T>)otherObject;
            if (size( ) != otherList.size( ))
                return false;
            Node<T> position = head;
            Node<T> otherPosition = otherList.head;
            while (position != null)
            {
                if (!(position.data.equals(otherPosition.data)))
                    return false;
                position = position.link;
                otherPosition = otherPosition.link;
            }
            return true; //no mismatch was not found
        }
    }

}

import java.util.Random;

public class Main_SortedList{

    public static void main(String args[]) {
        
        LinkedList3 unsortedList = new LinkedList3<Integer>();
        LinkedList3 sortedList = new LinkedList3<Integer>();
        LinkedList3 sortedFruit = new LinkedList3<String>();
        LinkedList3 unsortedFruit = new LinkedList3<String>();
        Random rand = new Random();

        int number;

        int [] numbers = new int [15];
        String[] fruits = {"bannana", "apple", "pinapple", "grape", "avocado", "stawberry", "watermellon", "peach", "pear", "papaya", "apricot"};
        
        //create 15 random numbers and add them to a linked list
        for(int x = 0; x < 15; x++){
            number = rand.nextInt(100);
            numbers[x] = number;
            unsortedList.addToStart(number);
        }
        System.out.println("Add to list unsorted: " );
        unsortedList.outputList();

        for(int data : numbers){
            sortedList.addSorted(data);
        }
        System.out.println("Add to sorted List: ");
        sortedList.outputList();

        for(String fruit : fruits){
            unsortedFruit.addToStart(fruit);
        }
        System.out.println("Add to unsorted List: ");
        unsortedFruit.outputList();

        for(String fruit : fruits){
            sortedFruit.addSorted(fruit);
        }
        System.out.println("Add to sorted List: ");
        sortedFruit.outputList();

    }
}