//Tina Ostrander
//CSCI 143 -- Singly Linked Lists


//Node class definition
//Represents a single node in a list,
//consisting of an int and a reference
//to the next node.

class Node
{
	int data;
	Node nextNode;

	//Create a Node with data only
	public Node (int dat)
	{
		this (dat, null);
	}

	//Create a Node with data and a reference to next
	public Node (int dat, Node next)
	{
		data = dat;
		nextNode = next;
	}

	//Set the data value of the Node
	public void setData (int dat)
	{
		data = dat;
	}

	//Retrieve the data value of the Node
	public int getData ()
	{
		return data;
	}

	//Set the reference to the next Node
	public void setNext (Node next)
	{
		nextNode = next;
	}

	//Retrieve the reference of the next Node
	public Node getNext ()
	{
		return nextNode;
	}
}


//Define List class
//Represents a list of linked Nodes

public class List
{
	//Define first and last Node in the list
	private Node firstNode;
	private Node lastNode;

	//Add a new node at the beginning of the list
	public void insertAtFront (int insertNum)
	{
		//If list is empty, the new Node is both first and last
		if (isEmpty())
		{
			//The new node has no reference
			firstNode = lastNode = new Node (insertNum);
		}
		//Otherwise, the new Node is added to the front of the List
		else
		{
			//The new node points to the Node that was first
			firstNode = new Node (insertNum, firstNode);
		}
	}

	//Add a new node at the end of the list
	public void insertAtBack (int insertNum)
	{
		//If the List is empty, the new Node is both first and last
		if (isEmpty())
		{
			//The new node has no reference
			firstNode = lastNode = new Node (insertNum);
		}
		//Otherwise, the new Node is added to the end of the List
		else
		{
			//Last Node becomes the new Node
			lastNode = lastNode.nextNode = new Node (insertNum);
		}
	}

	public int removeFromFront()
	{
		//Test to see if List is empty
		if (isEmpty())
		{
			System.out.println ("The list is empty!");
		}

		//Tag first Node for removal
		int removedItem = firstNode.data;

		//Is there only one Node in the list?
		if (firstNode == lastNode)
		{
			//Remove that Node
			firstNode = lastNode = null;
		}
		else
		{
			//The second Node becomes first
			firstNode = firstNode.nextNode;
		}

		return removedItem;
	}

	//Remove Node from end of list
	public int removeFromBack()
	{
		//Is list empty?
		if (isEmpty())
		{
			System.out.println ("The list is empty!");
		}

		//Retrieve data being removed
		int removedItem = lastNode.data;

		//Is there only one Node in the list?
		if (firstNode == lastNode)
		{
			//Remove that Node
			firstNode = lastNode = null;
		}
		else
		{
			//Traverse the list until second to last Node is found
			Node current = firstNode;
			while (current.nextNode != lastNode)
			{
				current = current.nextNode;
			}

			//Second to last Node becomes last
			lastNode = current;
			current.nextNode = null;
		}

		return removedItem;
	}

	//Determine whether list is empty (no first node)
	public boolean isEmpty()
	{
		return firstNode == null;
	}

	//Print the contents of the List
	public void print()
	{
		if (isEmpty())
		{
			System.out.println ("The list is empty!");
			return;
		}

		System.out.print ("The list contains: ");

		//Traverse the List, printing each item
		Node current = firstNode;
		while (current != null)
		{
			System.out.print (current.data + " ");
			current = current.nextNode;
		}

		System.out.println ("\n");
	}
}