public class RecursionLinkedList
{
	private Node firstNode;
	private int numberOfEntries;
	
	public RecursionLinkedList()
	{
		firstNode = null;
		numberOfEntries = 0;
	}
	
	public void add(int aData)
	{
		if(numberOfEntries == 0)
		{
			firstNode = new Node(aData);
		}
		else
		{
			firstNode = new Node(aData, firstNode);
		}
		
		numberOfEntries++;
	}
	
	/**
	 * boolean contains(int aData)
	 * 
	 * See whether this RecursionLinkedList contains aData
	 * @param aData  a data to be located
	 * @return true if this RecursionLinkedList contains aData,
	 *         or false otherwise.
	 */
	public boolean contains(int aData)
	{
		return containsHelper(firstNode,aData);
	}
	private boolean containsHelper(Node thisnode, int aData)
	{
		if(thisnode == null)
		{
			return false;
		}
		else if(thisnode.data == aData)
		{
			return true;
		}
		else
		{
			return containsHelper(thisnode.next, aData);
		}
	}
	
	/**
	 * int getFrequencyOf(int aData)
	 * 
	 * Counts the number of times a given data appears in this
	 * RecursionLinkedList.
	 * 
	 * @param aData  the data to be counted
	 * @return the number of times aData appears in this RecursionLinkedList
	 */
	public int getFrequencyOf(int aData)
	{
		return getFrequencyOfHelper(firstNode,aData);
	}
	private int getFrequencyOfHelper(Node thisnode, int aData)
	{
		if(thisnode == null)
		{
			return 0;
		}
		else if(thisnode.data == aData)
		{
			return getFrequencyOfHelper(thisnode.next, aData) + 1;
		}
		else
		{
			return getFrequencyOfHelper(thisnode.next, aData);
		}
	}
	
	/**
	 * String toString()
	 * 
	 * Return a string representation of this RecursionLinkedList. For example,
	 * if this RecursionLinkedList contains 1, 2, 3, 5, 2 and 3 from the first
	 * index to the last index, the returned string should be
	 * "[1,2,3,5,2,3]"
	 * @return the string representation of this RecursionLinkedList.
	 */
	public String toString()
	{
		return "[" + firstNode.data + toStringHelper(firstNode.next) + "]";
	}
	private String toStringHelper(Node thisnode)
	{
		if(thisnode == null)
		{
			return "";
		}
		else
		{
			return "," + thisnode.data + toStringHelper(thisnode.next);
		}
	}
	/**
	 * int getIndexOf(int aData)
	 * 
	 * Return the index of the first aData where the first index of
	 * the first item in this RecursionLinkedList is 0.
	 * 
	 * @param aData  the data to be located
	 * @return the index of the first aData.
	 */
	public int getIndexOf(int aData)
	{
		int p = getIndexOfHelper(firstNode,aData);
		/*
		if(p==numberOfEntries+1)
		{
			return -1;
		}
		else
		{
			return p;
		}
		*/
		return p==numberOfEntries+1?-1:p;
	}
	private int getIndexOfHelper(Node thisnode, int aData)
	{
		if(thisnode == null)
		{
			return 1;
		}
		else if(thisnode.data == aData)
		{
			return 0;
		}
		else
		{
			return getIndexOfHelper(thisnode.next,aData) + 1;
		}
	}
		
	private class Node
	{
		private int data;
		private Node next;
		
		private Node(int aData, Node nextNode)
		{
			data = aData;
			next = nextNode;
		}
		
		private Node(int aData)
		{
			this(aData, null);
		}
	}
}