public class FrequencyBag<T>
{
    // TO DO: Instance Variables
    private Node firstNode;
        private int numberOfEntries;
    /**
     * Constructor
     * Constructs an empty frequency bag.
     */
    public FrequencyBag()
    {
        firstNode = null;
                numberOfEntries = 0;

    }

    /**
     * Adds new entry into this frequency bag.
     * @param aData the data to be added into this frequency bag.
     */
    public void add(T aData)
    {
        if(numberOfEntries != 0){
                    Node newNode = new Node(aData);
                    newNode.next = firstNode;
                    firstNode = newNode;
                    numberOfEntries++;
                }
                else{
                    Node newNode = new Node(aData);
                    firstNode = newNode;
                    numberOfEntries++;
                }
    }

    /**
     * Gets the number of occurrences of aData in this frequency bag.
     * @param aData the data to be checked for its number of occurrences.
     * @return the number of occurrences of aData in this frequency bag.
     */
    public int getFrequencyOf(T aData)
    {
            int counter  = 0;
            Node currentNode = firstNode;
            for(int i = 1; i <=numberOfEntries; i++) {
                if(currentNode.data.equals(aData))
                {
                    counter ++;

                }
                currentNode = currentNode.next;

                }
            return counter;
            }



    /**
     * Gets the maximum number of occurrences in this frequency bag.
     * @return the maximum number of occurrences of an entry in this
     * frequency bag.
     */
    public int getMaxFrequency()
    {
        // TO DO
            Node currentNode = firstNode;
            int currentFrequency = 0;
            int maxFrequency = currentFrequency;

            for(int i = 1; i <= numberOfEntries; i++)
        {
            currentFrequency = getFrequencyOf(currentNode.data);
            if(currentFrequency > maxFrequency)
            {
                maxFrequency = currentFrequency;
            }
            currentNode = currentNode.next;
        }
        return maxFrequency;
    }

    /**
     * Gets the probability of aData
     * @param aData the specific data to get its probability.
     * @return the probability of aData
     */
    public double getProbabilityOf(T aData)
    {
        double num = getFrequencyOf(aData);
                double probability = num / numberOfEntries;
                return probability;
    }

    /**
     * Empty this bag.
     */
    public void clear()
        {
            Node tempNode = null;

            for(int i = 1; i <= numberOfEntries; i++){
            tempNode = firstNode.next;
            firstNode = null;
            firstNode = tempNode;

            }
            numberOfEntries = 0;

    }

    /**
     * Gets the number of entries in this bag.
     * @return the number of entries in this bag.
     */
    public int size()
    {
        return numberOfEntries;
    }

   private class Node {

       private T data;
       private Node next;

       private Node(T aData){
           data = aData;
           next = null;
       }

   }
}