public interface Link {
	public Link getNext();
	public void setNext(Link link);

	public Link getPrev();
	public void setPrev(Link link);

	public E getValue();
	public void setValue(E value);
}

public class SingleLink implements Link {

	public SingleLink(E value) { this.value = value; }

	private Link next;
	private E value;

	public Link getNext() { return next; }
	public void setNext(Link next) { this.next = next;}

	public Link getPrev() { throw new UnsupportedOperationException(); }
	public void setPrev(Link prev) { throw new UnsupportedOperationException(); }

	public E getValue() { return value; }
	public void setValue(E value) { this.value = value;}

	@Override
	public boolean equals(Object obj) { return this.value.equals(obj); }

	@Override
	public String toString() { return getValue().toString(); }
}

public abstract class LinkedList {

	protected abstract Link createHead(E value);
	protected abstract Link removeHead();
	protected abstract Link append(Link tail, E value);
	protected abstract void chain(Link from, Link to);
	protected abstract void deleteAfterHead(E value);
	protected abstract boolean isInsert(Link link);
	protected abstract boolean isEnd(Link link);

	public void insert(E value) {

		if (head == null) {
			createHead(value);
			return;
		}

		Link tmp = head;
		while (!isInsert(tmp))
			tmp = tmp.getNext();

		append(tmp, value);
	}

	public void delete(E value) {

		if (head == null)
			return;

		if (head.equals(value)) {
			removeHead();
			return;
		}

		deleteAfterHead(value);
	}

	Link head;
}

public class SinglyLinkedList extends LinkedList {

	@Override
	protected Link createHead(E value) {
		if (value != null) {
			head = new SingleLink(value);
		} else {
			head = null;
		}
		return head;
	}

	@Override
	protected Link removeHead() {
		if (isEnd(head.getNext())) {
			head = null;
			return null;
		}

		head = head.getNext();
		return head;
	}

	@Override
	protected Link append(Link tail, E value) {
		Link link = new SingleLink(value);
		tail.setNext(link);
		return link;
	}

	@Override
	protected void chain(Link from, Link to) {
		from.setNext(to);
	}

	@Override
	protected void deleteAfterHead(E value) {

		Link tmp = head.getNext();
		Link prev = head;
		while (!isEnd(tmp)) {
			if (tmp.equals(value)) {
				chain(prev, tmp.getNext());
				break;
			}
			prev = tmp;
			tmp = tmp.getNext();
		}
	}

	@Override
	protected boolean isInsert(Link link) {
		return isEnd(link.getNext());
	}

	@Override
	protected boolean isEnd(Link link) {
		return link == null;
	}
}

public class DoubleLink extends SingleLink {

	public DoubleLink(E value) { super(value); }

	private Link prev;

	@Override
	public Link getPrev() { return prev; }

	@Override
	public void setPrev(Link prev) { this.prev = prev; }
}

public class DoublyLinkedList extends SinglyLinkedList {

	@Override
	protected Link createHead(E value) {
		if (value != null) {
			head = new DoubleLink(value);
		} else {
			head = null;
		}
		return head;
	}

	@Override
	protected Link removeHead() {
		head = super.removeHead();
		if (head != null) {
			head.setPrev(null);
		}

		return head;
	}

	@Override
	protected Link append(Link tail, E value) {
		Link link = new DoubleLink(value);
		tail.setNext(link);
		link.setPrev(tail);
		return link;
	}

	@Override
	protected void chain(Link from, Link to) {
		from.setNext(to);
		if (to != null) {
			to.setPrev(from);
		}
	}

	@Override
	protected void deleteAfterHead(E value) {

		Link tmp = head.getNext();
		while (!isEnd(tmp)) {
			if (tmp.equals(value)) {
				chain(tmp.getPrev(), tmp.getNext());
				break;
			}
			tmp = tmp.getNext();
		}
	}
}

public class SortedLinkedList extends SinglyLinkedList {

	@Override
	public void insert(E value) {

		if (head == null) {
			createHead(value);
			return;
		}

		Link tmp = head;
		Link prev = null;
		// XXX: yuck, dynamic casting to Comparable
		while (!isEnd(tmp) &&
	Comparable) tmp.getValue()).compareTo(value) < 0) {
			prev = tmp;
			tmp = tmp.getNext();
		}

		Link link = new SingleLink(value);
		if (prev == null) {
			link.setNext(head);
			head = link;
		} else {
			prev.setNext(link);
			link.setNext(tmp);
		}
	}
}

public class CircularLinkedList extends DoublyLinkedList {

	@Override
	protected Link createHead(E value) {
		head = super.createHead(value);
		if (head != null) {
			head.setNext(head);
			head.setPrev(head);
		}
		return head;
	}
	
	@Override
	protected Link removeHead() {
		if (head.getNext() == head) {
			head = null;
			return null;
		}
		
		Link prev = head.getPrev();
		head = head.getNext();
		head.setPrev(prev);
		prev.setNext(head);
		return head;
	}		

	@Override
	protected Link append(Link tail, E value) {
		Link link = new DoubleLink(value);
		tail.setNext(link);
		link.setPrev(tail);
		link.setNext(head);
		head.setPrev(link);
		return link;
	}
	
	@Override
	protected boolean isEnd(Link link) {
		return link == head;
	}

	@Override
	protected boolean isInsert(Link link) {
		return link.getNext() == head;
	}
}