import java.util.Iterator;

public class SinglyLinkedList<Type> {
	private ListNode<Type> head;
	
	public SinglyLinkedList(Type element) {
		head = new ListNode<Type>(element);
	}
	
	public ListNode<Type> getFirst() {
		return head;
	}
	
	public static void main(String[] args) {
		// Using the most basic implementation.
		SinglyLinkedList<String> list = new SinglyLinkedList<String>("A");
		
		ListNode<String> node = list.getFirst();
		node.setNext(new ListNode<String>("B"));
		node.getNext().setNext(new ListNode<String>("C"));
		node.getNext().getNext().setNext(new ListNode<String>("D"));
		
		while (node != null) {
			System.out.println(node);
			node = node.getNext();
		}
		
		// Using add methods and iterator.
		list = new SinglyLinkedList<String>("1");
		list.add("2", 1);
		list.add("3", 2);
		list.add("4", 3);
		
		list.remove(2);
		
		Iterator<String> iter = list.iterator();
		while (iter.hasNext()) {
			System.out.println(iter.next());
		}
		
		// Add 3 again, reverse list, and print out.
		list.add("3", 2);
		list.reverse();
		iter = list.iterator();
		System.out.println("Reversed list:");
		while (iter.hasNext()) {
			System.out.println(iter.next());
		}
	}
	
	// Extra methods
	
	// Insert after current element.
	public void addToFront(Type element) {
		ListNode<Type> newHead = new ListNode<Type>(element);
		newHead.setNext(head);
		head = newHead;
	}
	
	public void add(Type element, int index) {
		if (index == 0) {
			ListNode<Type> newHead = new ListNode<Type>(element);
			newHead.setNext(head);
			head = newHead;
		} else {
			int count = 1;
			ListNode<Type> next = head;
			while (count < index && next.getNext() != null) {
				next = next.getNext();
				count++;
			}
			ListNode<Type> newNode = new ListNode<Type>(element);
			newNode.setNext(next.getNext());
			next.setNext(newNode);
		}
	}
	
	public Type remove(int index) {
		int count = 0;
		ListNode<Type> current = head;
		ListNode<Type> previous = null;
		while (count < index && current != null) {
			if (count == index - 1) {
				previous = current;
			}
			current = current.getNext();
			count++;
		}
		
		if (current == null) {
			return null;
		} else {
			Type element = current.getElement();
			previous.setNext(current.getNext());
			return element;
		}
	}
	
	public void reverse() {
		ListNode<Type> current = head, next = head.getNext();
		current.setNext(null);
		
		while (next != null) {
			ListNode<Type> temp = next;
			next = next.getNext();
			temp.setNext(current);
			current = temp;
		}
		head = current;
	}
	
	public Iterator<Type> iterator() {
		return new SLLIterator<Type>(head);
	}
	
	class SLLIterator<IteratorType> implements Iterator<IteratorType> {
		private ListNode<IteratorType> current;
		
		public SLLIterator(ListNode<IteratorType> head) {
			current = head;
		}
		
		public boolean hasNext() {
			return current != null;
		}
		
		public IteratorType next() {
			if (current == null) {
				return null;
			} else {
				IteratorType next = current.getElement();
				current = current.getNext();
				return next;
			}
		}
		
		public void remove() {
		}
	}
}

class ListNode<NodeType> {
	private NodeType element;
	private ListNode<NodeType> next;
	
	public ListNode(NodeType element) {
		this.element = element;
	}
	
	public void setNext(ListNode<NodeType> next) {
		this.next = next;
	}
	
	public ListNode<NodeType> getNext() {
		return next;
	}
	
	public NodeType getElement() {
		return element;
	}
	
	public String toString() {
		return element.toString();
	}
}