import java.util.Iterator;

public class DoublyLinkedList<Type> {
	private DoubleListNode<Type> head, tail;
	
	public DoublyLinkedList(Type element) {
		head = tail = new DoubleListNode<Type>(element);
	}
	
	public DoubleListNode<Type> getFirst() {
		return head;
	}
	
	public DoubleListNode<Type> getLast() {
		return tail;
	}
	
	public static void main(String[] args) {
		// Using the most basic implementation.
		DoublyLinkedList<String> list = new DoublyLinkedList<String>("A");
		
		DoubleListNode<String> node = list.getFirst();
		node.setNext(new DoubleListNode<String>("B"));
		node.getNext().setNext(new DoubleListNode<String>("C"));
		node.getNext().getNext().setNext(new DoubleListNode<String>("D"));
		
		while (node != null) {
			System.out.println(node);
			node = node.getNext();
		}
		
		// Using add methods and iterator.
		list = new DoublyLinkedList<String>("1");
		list.add("2", 1);
		list.add("3", 2);
		list.add("4", 3);
		
		list.remove(2);
		
		Iterator<String> iter = list.iterator(false);
		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(true);
		System.out.println("Reversed list:");
		while (iter.hasNext()) {
			System.out.println(iter.next());
		}
	}
	
	// Extra methods
	
	// Insert after current element.
	public void addToFront(Type element) {
		DoubleListNode<Type> newHead = new DoubleListNode<Type>(element);
		newHead.setNext(head);
		head.setPrevious(newHead);
		head = newHead;
	}
	
	public void addToBack(Type element) {
		DoubleListNode<Type> newTail = new DoubleListNode<Type>(element);
		newTail.setPrevious(tail);
		tail.setNext(newTail);
		tail = newTail;
	}
	
	public void add(Type element, int index) {
		if (index == 0) {
			DoubleListNode<Type> newHead = new DoubleListNode<Type>(element);
			newHead.setNext(head);
			head = newHead;
		} else {
			int count = 1;
			DoubleListNode<Type> next = head;
			while (count < index && next.getNext() != null) {
				next = next.getNext();
				count++;
			}
			DoubleListNode<Type> newNode = new DoubleListNode<Type>(element);
			newNode.setNext(next.getNext());
			newNode.setPrevious(next);
			next.setNext(newNode);
		}
	}
	
	public Type remove(int index) {
		int count = 0;
		DoubleListNode<Type> current = head;
		
		while (count < index && current != null) {
			current = current.getNext();
			count++;
		}
		
		if (current == null) {
			return null;
		} else {
			Type element = current.getElement();
			if (current.getPrevious() != null) {
				current.getPrevious().setNext(current.getNext());
			}
			if (current.getNext() != null) {
				current.getNext().setPrevious(current.getPrevious());
			}
			return element;
		}
	}
	
	public void reverse() {
		DoubleListNode<Type> current = head, next = head.getNext();
		current.setNext(null);
		
		while (next != null) {
			DoubleListNode<Type> temp = next;
			next = next.getNext();
			temp.setNext(current);
			current.setPrevious(temp);
			current = temp;
		}
		current.setPrevious(null);
		tail = head;
		head = current;
	}
	
	public Iterator<Type> iterator(boolean backwards) {
		if (backwards) {
			return new SLLIterator<Type>(tail, true);
		} else {
			return new SLLIterator<Type>(head, false);
		}
	}
	
	class SLLIterator<IteratorType> implements Iterator<IteratorType> {
		private DoubleListNode<IteratorType> current;
		private boolean backwards;
		
		public SLLIterator(DoubleListNode<IteratorType> head, boolean backwards) {
			current = head;
			this.backwards = backwards;
		}
		
		public boolean hasNext() {
			return current != null;
		}
		
		public IteratorType next() {
			if (current == null) {
				return null;
			} else {
				IteratorType next = current.getElement();
				if (backwards) {
					current = current.getPrevious();
				} else {
					current = current.getNext();
				}
				return next;
			}
		}
		
		public void remove() {
		}
	}
}

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