package lab04_test;
import java.util.Iterator;

//The LinkedList Node class 
class Node<T>{
	
	private T nodeData;
	private Node<T> nextNode;
	
	public Node( T newData, Node<T> newNextNode ){
		nodeData = newData;
		nextNode = newNextNode;
	}
	public T getData(){
		return nodeData;
	}
	public Node<T> getNextNode(){
		return nextNode;
	}
	public void setData(T newData){
		nodeData = newData;
	}
	public void setNextNode( Node<T> newNextNode ){
		nextNode = newNextNode;
	}
}

//The LinkedList class 
public class LinkedList<T> implements Iterable<T> {	
	
	private Node<T> headNode;
	
	public LinkedList(){
		headNode = null;
	}
	
	// Add a new node to head of the list
	public void addToHead( T newNodeData ){
		headNode = new Node<T>( newNodeData, headNode );
	}
	
	// Delete the head node and return data in the deleted node
	public T deleteFromHead(){
		T headNodeData = headNode.getData(); 
		headNode = headNode.getNextNode();
		return headNodeData;
	}
	
	// Get an iterator for this list
	public ListIterator<T> iterator(){
		return new ListIterator<T>( headNode );
	}
	
	// The ListIterator class below implements an iterator for the 
	// LinkedList class 
	static class ListIterator<T> implements Iterator<T> {
		
		// Keeps track of the iterator's position in the list
		private Node<T> currentNode;
		
		// The iterator starts off at head of the linked list
		public ListIterator( Node<T> headNode ){
			currentNode = headNode;
		}
		// Are there more nodes ahead of us?
		public boolean hasNext(){
			return ( currentNode != null ); 
		}
		// Output current "node data" and walk to the next node
		public T next(){
			T currentData = currentNode.getData();
			currentNode = currentNode.getNextNode();
			return currentData;
		}
		// Output current "node" and walk to the next node
		public Node<T> nextNode(){
			Node<T> tempNode = currentNode;
			currentNode = currentNode.getNextNode();
			return tempNode;
		}
		// remove not implemented here but implemented in the 
		// LinkedList class above
		public void remove(){
		}
	}
	
	// Prints elements in the list using the list-iterator
	public void printList(){
		// Use the list-iterator to walk down the list
		ListIterator<T> listIterator = this.iterator();
		while(listIterator.hasNext()){
			System.out.print(listIterator.next()+", ");
		}
		System.out.println("\n");
	}
	
	// Add a new node to tail of the list
	public void addToTail( T newNodeData ){
		// Locate the last node in the list so that we can 
		// add newNode after it.
		Node<T> lastNode = null;
		
		// Use the listIterator to walk through the list to find last node
		ListIterator<T> listIterator = this.iterator();
		while(listIterator.hasNext()){
			lastNode = listIterator.nextNode();
		}
		// Create a new node with newNodeData and set it as next node for lastNode
		// *** check whether lastNode is null and do appropriately 
		Node<T> newNode = new Node<T>(newNodeData, null);
		if( lastNode != null )
			lastNode.setNextNode(newNode);
		else
			headNode = newNode; 
	}
	
	// Delete the tail node and returns data in the deleted node
	public T deleteFromTail(){
		// Find the last two nodes in the list so that we can   
		// delete the last node and update the forward reference to it.
		Node<T> lastNode = null;
		Node<T> previousToLastNode = null;
		
		// Use the list-iterator to walk through the list to find the 
		// last two nodes.
		ListIterator<T> listIterator = this.iterator();
		while(listIterator.hasNext()){
			previousToLastNode = lastNode;
			lastNode = listIterator.nextNode();
		}
		
		T tailNodeData;
		// (a) assign data from lastNode to tailNodeData
		// (b) change forward reference to nextNode in previousToLastNode
		// *** check whether any of lastNode or previousToLastNode 
		// *** is null and do appropriately 
		if( lastNode == null ){
			tailNodeData = null;
		} else if ( previousToLastNode == null ){
			tailNodeData = lastNode.getData();
			headNode = null;
		} else {
			tailNodeData = lastNode.getData();
			previousToLastNode.setNextNode(null);
		}
		// return data in the deleted node
		return tailNodeData;
	}
}