betweenGo

public interface Link<E> {
	public Link<E> getNext();
	public void setNext(Link<E> link);

	public Link<E> getPrev();
	public void setPrev(Link<E> link);

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

public class SingleLink<E> implements Link<E> {

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

	private Link<E> next;
	private E value;

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

	public Link<E> getPrev() { throw new UnsupportedOperationException(); }
	public void setPrev(Link<E> 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<E> {

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

	public void insert(E value) {

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

		Link<E> 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<E> head;
}

public class SinglyLinkedList<E> extends LinkedList<E> {

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

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

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

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

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

	@Override
	protected void deleteAfterHead(E value) {

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

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

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

public class DoubleLink<E> extends SingleLink<E> {

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

	private Link<E> prev;

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

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

public class DoublyLinkedList<E> extends SinglyLinkedList<E> {

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

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

		return head;
	}

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

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

	@Override
	protected void deleteAfterHead(E value) {

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

public class SortedLinkedList<E> extends SinglyLinkedList<E> {

	@Override
	public void insert(E value) {

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

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

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

public class CircularLinkedList<E> extends DoublyLinkedList<E> {

	@Override
	protected Link<E> createHead(E value) {
		head = super.createHead(value);
		if (head != null) {
			head.setNext(head);
			head.setPrev(head);
		}
		return head;
	}

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

		Link<E> prev = head.getPrev();
		head = head.getNext();
		head.setPrev(prev);
		prev.setNext(head);
		return head;
	}		

	@Override
	protected Link<E> append(Link<E> tail, E value) {
		Link<E> link = new DoubleLink<E>(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;
	}
}