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

Have you taken a look at the Deque class? Per the javadoc, "A linear collection that supports element insertion and removal at both ends. The name deque is short for "double ended queue" and is usually pronounced "deck"." It is implemented by ArrayDeque, LinkedBlockingDeque and LinkedList.

Answer 2

Because all container in Java store references to the object, then all containers in Java are intrusive by default, at least according to the definition from here:

The main difference between intrusive containers and non-intrusive containers is that in C++ non-intrusive containers store copies of values passed by the user.

I suggest you use standard ( well-implemented ) container from java.util package. For double linked list I think ArrayDeque supersedes vanilla LinkedList .

Answer 3

Java's semantics are by design intrusive, they use references and don't copy. You basically just want to find the best linked list implementation that java has, LinkedList or whatever, and it'll be intrusive.

import java.util.LinkedList;

public class Foo {

  public static void main(String[] args) {
    String[] i = new String[1];
    i[0] = "FOO";
    String[] j = new String[1];
    j[0] = "BAZ";

    LinkedList<String[]> list = new LinkedList<String[]>();

    list.add(i);
    list.add(j);

    for (String[] x: list) {
      System.out.println(x[0]);
    }

    i[0] = "ZILCH";

    for (String[] x: list) {
      System.out.println(x[0]);
    }
  }
}

Here's the output, notice how changing i changed the value in the list.

FOO
BAZ
ZILCH
BAZ

Answer 4

if you look to SDK code you will see that LinkedList is, in fact, a list of a private class Entry which contains next and previous elements. So, if you include MyClass in this list, an element of the list will be an Entry with your object and the links for the next and previous elements of the list.

So, i think it is intrusive...

private static class Entry<E> {
    E element;
    Entry<E> next;
    Entry<E> previous;

    Entry(E element, Entry<E> next, Entry<E> previous) {
        this.element = element;
        this.next = next;
        this.previous = previous;
    }
}

Answer 5

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;
  }
}

Answer 6

What do you hope to gain by using an intrusive list? I'm hard pressed to think what the advantages would be. Okay, there's a trivial efficiency that you have just one object instead of two for each node. But the price of this is a big loss in flexibility and reliability. For example, now you can't have the same object in two lists at the same time. What happens if a caller retrieves an instance of a list member and tries to change one of the pointers itself? What it a caller clones a node and fails to update the pointers? Etc.

Dave Ray makes the point that with an intrusive list you can delete a node in constant time because you already have the pointers and don't need to re-find the item. True, but that assumes that you've saved a handle to the node somewhere and are now coming back to it. With the Java LinkedList class pretty much the only way to access elements is to traverse the list with an Iterator, or to search for a particular object. If you traverse with an Iterator, the Iterator.remove will remove in constant time. So it's only if you search, find, and then decide to remove that you pay this penalty. I think it would be an improvement on the LinkedList implementation if they cached a pointer to the last object found to improve the performance on precisely this point. My guess is that they didn't because it would make the remove non-deterministic: You could have the same object in the list multiple times -- either literally the same instance or two objects that compare equal -- and the contract on remove presently says that it always removes the first occurrence. If there was a cached pointer, it would be difficult to say whether this was the first, second, or 42nd.

Oh, to actually answer your question: No, I'm not aware of an open-source implementation out there. But then if I needed my own flavor of a linked list, I think I'd just roll my own. Presumably if the standard Java one doesn't meet your needs, that must mean that you have some pretty specialized need. In which case searching for an off-the-shelf implementation that happens to meet your specialized need sounds like a lot of trouble, and you could surely implement it in, what, a day or two of work? You'd probably spend more time searching for a suitable product than it would take to just do it. You've probably already spent more time reading the replies to this post than it would have taken you to write it.