java - Java的侵入式列表实现？

是否有可用于Java的(实现良好的)侵入式双链表类？还是我应该自己做？ Boost适用于C++:http://beta.boost.org/doc/libs/1_40_0/doc/html/boost/intrusive/list.html。

侵入列表是一个在元素中具有next和prev指针的容器，因此典型的列表操作(例如replace和remove)可以直接定位到基本类而不是容器类。在某些情况下，侵入列表是最佳解决方案。

我尝试举一个适当的例子。假设我链接了由不同类型的类X1和Y2拥有的列表L list1和L list2。

Q类(无关紧要或无法轻易访问x1和Y2的接口(interface))需要执行i)替换，ii)删除元素e的操作，该元素始终存在于list1 xor list2中的某个位置，具体取决于运行时状态，但该信息不会直接存储在任何地方。

使用侵入式列表Q可以仅将对元素的引用存储到成员元素e中，并且它始终指向正确的位置。

否则，您必须从几种明显更复杂的解决方法中选择一种。
-元素e的包装程序类，以及用于完成操作i和ii的其他方法。不。

基本上，问题仍然不在于性能，而在于体系结构的复杂性。这也可以理解为一种共享对象的情况，其中解决方案IL避免了每个客户端Lx和Q的更新需求。

请注意，我不需要与其他标准容器兼容。只是具有迭代，添加，删除和查找与未知元素类一起使用的操作的通用侵入式lsit实现。

谢谢。

最佳答案

我不知道任何现有的实现(不，我不认为普通的Java集合具有侵入性)。

这可能是因为这样的列表在Java中具有的唯一主要优点是，当您已经手头要删除Element(并且在该位置没有remove())时，可以快速进行Iterator调用。在Java中，非复制元素不是有效的参数，因为Java List实现始终只能处理引用(并且永远不会复制整个对象)。

但是您可以通过创建必要的接口(interface)来轻松编写具有侵入性的通用List实现:

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
}

您的元素类可能如下所示:

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