An intrusive list class for Java

IntrusiveList.java

public final class IntrusiveList<T> {
	
	/** private constructor used by makeList() */
	private IntrusiveList() {
		t = null; // is null so we know this must be the head/tail
		prev = next = this; // cyclic
	}

	/** returns a new head/tail pointer */
	public static <T> IntrusiveList<T> makeList() {
		return new IntrusiveList<T>();
	}
	
	/** create a list node associated with an object */
	public IntrusiveList(T t) {
		assert t != null;
		this.t = t;
	}
	
	/** removes it from a list if its in one, and add it to the list after the specified node */
	public void link(IntrusiveList<T> after) {
		assert after != null;
		unlink();
		prev = after;
		next = after.next;
		if(next.prev != null)
			next.prev = this;
		after.next = this;
	}
	
	/** removes this from the list its in, if there is one.
	 * @return the item that was next in the list after this one (or null) */
	public T unlink() {
		assert t != null; // can't unlink a head/tail node
		if(prev!=null) {
			assert next!=null;
			assert prev.next == this;
			prev.next = next;
		}
		if(next!=null) {
			assert prev!=null;
			assert next.prev == this;
			next.prev = prev;
		}
		T ret = next!=null? next.t: null;
		prev = next = null;
		return ret;
	}
	
	private final T t;
	
	private IntrusiveList<T> prev, next;
	
	/** returns the previous item in this list, or null if this is the first.
	 * if this is the head/tail list node, returns the tail of the list */
	public T getPrev() {
		return prev!=null? prev.t: null;
	}
	
	/** returns the next item in this list, or null if this is the last.
	 * if this is the head/tail list node, returns the head of the list */
	public T getNext() {
		return next!=null? next.t: null;
	}
	
	/** <b>WARNING!</b> O(n), avoid calling
	 * @return the number of items in this list */
	public int size() {
		int len = 0;
		for(IntrusiveList<T> p=prev; !p.isList(); p=p.prev)
			len++;
		if(t!=null) // not head/tail
			for(IntrusiveList<T> n=this; !n.isList(); n=n.next)
				len++;
		return len;
	}
	
	/** <b>WARNING!</b> O(n), avoid calling
	 * @return the head/tail element of this list */
	public IntrusiveList<T> geList() {
		if(isList())
			return this;
		if(isUnlinked())
			return null;
		for(IntrusiveList<T> p=prev; ; p=p.prev)
			if(p.isList())
				return p;
	}
	
	public boolean isLinked() {
		return prev!=null || next!=null;
	}

	public boolean isUnlinked() {
		return prev==null && next==null;
	}
	
	public boolean isList() {
		return t==null;
	}

	public static void main(String[] args) {
		class Test {
			public Test(String id) { this.id = id; }
			public final String id;
			public IntrusiveList<Test> list = new IntrusiveList<Test>(this);
		};
		IntrusiveList<Test> list = IntrusiveList.makeList();
		System.out.println("(an empty list has "+list.size()+" items)");
		Test a = new Test("a"), b = new Test("b"), c = new Test("c"), d = new Test("d"), e = new Test("e");
		System.out.println("last in, first out");
		a.list.link(list);
		b.list.link(list);
		c.list.link(list);
		System.out.println("(list has "+list.size()+" items)");
		assert list.size() == b.list.size();
		for(Test i = list.getNext(); i!=null; i = i.list.getNext())
			System.out.println(i.id);
		System.out.println("reordering");
		b.list.link(list);
		a.list.link(list);
		System.out.println("(list has "+list.size()+" items)");
		assert list.size() == b.list.size();
		for(Test i = list.getNext(); i!=null; i = i.list.getNext())
			System.out.println(i.id);
		System.out.println("adding at end and middle");
		d.list.link(c.list); // c is at the end
		e.list.link(b.list); // b is near the middle
		System.out.println("(list has "+list.size()+" items)");
		assert list.size() == b.list.size();
		for(Test i = list.getNext(); i!=null; i = i.list.getNext())
			System.out.println(i.id);
		System.out.println("removing c");
		c.list.unlink();
		System.out.println("(list has "+list.size()+" items)");
		assert list.size() == b.list.size();
		for(Test i = list.getNext(); i!=null; i = i.list.getNext())
			System.out.println(i.id);
		System.out.println("list them backwards");
		for(Test i = list.getPrev(); i!=null; i = i.list.getPrev())
			System.out.println(i.id);
	}
	
}