public class LinkedList
{
	int size = 0;
	Node head = null;
	Node tail = null;
	
	//default constructor
	public LinkedList()
	{
		
	}
	
	//add at the tail
	public void add(int num)
	{
		//if there are no nodes yet
		if (head == null && tail == null)
		{
			Node newNode = new Node();
			newNode.num = num;
			head = newNode;
			tail = newNode;
		}
		else	//if there is at least one node in the list (not empty)
		{
			//add to the tail
			Node newNode = new Node();
			newNode.num = num;
			tail.next = newNode;
			tail = newNode;
		}
		size++;
	}
	
	//remove node at index
	public int remove(int index)
	{
		//5 scenarios for removal
		//0) removing from empty list returns -1
		//1) removing the head
		//2) removing something in the 'middle' of the list
		//3) removing the tail
		//4) removing the last thing in the list
		
		if (isEmpty())
			return -1;
		
		if (index == 0 && size != 1)
		{
			int num = head.num;
			head = head.next;	//make head point to the next thing
			size--;
			return num;
		}
		
		if (index == 0 && size == 1)	//accomodate for scenario when removing last element
		{
			int num = head.num;
			head = null;
			tail = null;
			size--;
			return num;
		}
		
		int i = 0;
		Node nodeBefore = head;
		int num = -1;
		for (Node currentNode = head; currentNode != null; currentNode = currentNode.next)
		{
			if (i == index) //got to my node's index
			{
				if (currentNode == tail) //removing tail
				{
					num = currentNode.num;
					tail = nodeBefore;
					tail.next = null;
				}
				else	//removing any element in the middle
				{
					num = currentNode.num;
					nodeBefore.next = currentNode.next; 
				}
			}
			
			i++;
			nodeBefore = currentNode;
		}
		size--;
		return num;
	}	
	
	public boolean isEmpty()
	{
		if (size == 0)
			return true;
		else
			return false;
		
		//return size == 0;
		
		//return head == null;
	}
	
	public void insertInOrder(int newNum)
	{
		//inserting in an empty list
		if (isEmpty())
		{
			head = new Node();
			head.num = newNum;
			head.next = null;
			size++;
			tail = head;
			return;
		}
		//inserting at the end
		if (newNum > tail.num)
		{
			tail.next = new Node();
			tail = tail.next;
			tail.num = newNum;
			size++;
			return;
		}
		
		//inserting at the front
		if (newNum < head.num)
		{
			Node oldHead = head;
			head = new Node();
			head.num = newNum;
			head.next = oldHead;
			size++;
			return;
		}
		
		//inserting in the middle
		if (newNum > head.num && newNum < tail.num)
		{
			Node previous = head;
			for (Node current = head; current != null; current = current.next)
			{
				if (current.num > newNum)
				{
					//insert before current node
					Node newNode = new Node();
					previous.next = newNode;
					newNode.num = newNum;
					newNode.next = current;
					size++;
					return;
				}
				
				previous = current;
			}
		}
	}
	
	//traverses the LinkedList and prints out each node
	public void print()
	{
		for (Node current = head; current != null; current = current.next)
		{
			System.out.print(current.num + " ");
		}
		System.out.println();
	}
}