是否有可用于
Java的任何(良好实现的)入侵的双链表类？还是应该做我自己的？升压有C：
http://beta.boost.org/doc/libs/1_40_0/doc/html/boost/intrusive/list.html.
Intrusive列表是一个容器(在这种情况下)和元素中的prev指针,所以典型的列表操作(如replace和remove)可以直接定位到基本类而不是容器类.在某些情况下,侵入式列表是最好的解决方案.
我试着给出一个恰当的例子.让我们假设我有链接列表L list1和L list2由不同类型的类X1和Y2拥有.
Q类(没有什么关系或不容易访问x1和Y2的接口)需要做到这一点i)替换,ii)删除元素e的操作,它总是存在于list1 xor list2的某个地方,这取决于运行时状态,但该信息不会直接存储在任何地方.
使用入侵者列表Q可以将元素的引用存储到成员元素e,并且它始终指向正确的位置.
否则,您必须从几个明显更复杂的解决方法中选择一个或另一个.
– 元素e的包装类和完成操作的其他方法i和ii.没有.
基本上,问题仍然不是关于性能,而是架构的复杂性.这也可以被理解为一种共享对象情况,其中解决方案IL避免了每个客户端Lx和Q的更新需要.
请注意,我不需要与其他标准容器兼容.只是一个通用的侵入式lsit实现,用于对未知元素类进行迭代,添加,删除和查找操作.
谢谢.
解决方法
我不知道任何现有的实现(不,我不认为普通的Java集合是侵入性的).
这可能是因为这个列表在Java中的唯一主要优点是当您已经有要删除的元素(并且在该位置没有迭代器)时,将快速的remove()调用.不复制的元素在Java中不是有效的参数,因为Java List实现仅处理引用(并且不会复制整个对象).
但是您可以通过创建必要的界面轻松地编写一个通用的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;
}
}
