Intrusive list implementation for Java?

Question

Is there any (well implemented) intrusive double linked list class(es) available for Java? Or should I do my own? Boost has it for C++: http://beta.boost.org/doc/libs/1_40_0/doc/html/boost/intrusive/list.html.

Intrusive list is a container having (in this case) next and prev pointers within element, so typical list operations like replace and remove can be directly targeted into elementary class instead of container class. There are some certain situations, where intrusive list are the best solution.

I try to give an appropriate example. Let's assume I have linked lists L list1 and L list2 owned by different type of classes X1 and Y2.

class Q (which has nothing to do or doesn't easily get access the interfaces of x1 and Y2 otherwise) needs to do i) replace, ii) remove operation for element e, which exists always in somewhere, in list1 xor list2 depending on run-time state, but that information is not stored directly anywhere.

With intrussive list Q can just store reference to an element to member element e and it always points the right place.

Otherwise you have to choose from several clearly more complex workarounds one or the other. - Wrapper class for element e and and additional methods for completing operations i and ii. No.

Basically, the question is still not about the performance but architectural complexity. This can also be understood as one kind of shared object situation where solution IL avoids the update need for every client Lx and Q.

Please notice I do NOT necessary need compatibility to other standard containers. Just an generic intrusive lsit implementation with an iterating, add, remove and find operations used with unknown element class.

Thanks.

Answer 1

I'm not aware of any existing implementations (and no, I don't consider the normal Java collections to be intrusive).

That's probably because the only major advantage such a list would have in Java would be the fast remove() call when you already have the Element to be removed at hand (and don't have an Iterator at that position). The not-copying-the-element is not a valid argument in Java, since Java List implementations handle only references anyway (and never copy the whole object).

But you can easily write a general-purpose List implementation that is intrusive by creating the necessary interface:

public interface IntrusiveListElement<E extends<IntrusiveListElement<E>> {
  public void setNext(E next);
  public E getNext();
  public void setPrev(E prev);
  public E getPrev();
}

public class IntrusiveList<E extends IntrusiveListElement<E>> implements List<E> {
  // implement your run-of-the-mill double-linked list here
}

Your element class could look like this:

public class MyBusinessElement implements IntrusiveListElement<MyBusinessElement> {
  private MyBusinessElement prev;
  private MyBusinessElement next;

  public void setNext(MyBusinessElement next) {
    this.next = next;
  }

      public MyBusinessElement getNext() {
    return next;
  }

  public void setPrev(MyBusinessElement prev) {
    this.prev = prev;
  }

  public MyBusinessElement getPrev() {
    return prev;
  }
}