Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
An intrusive list class for 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);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.