侵入式列表实现Java？

发布时间：2020-12-14 05:24:45 所属栏目：Java 来源：网络整理

导读：是否有可用于 Java的任何(良好实现的)入侵的双链表类？还是应该做我自己的？升压有C： http://beta.boost.org/doc/libs/1_40_0/doc/html/boost/intrusive/list.html. Intrusive列表是一个容器(在这种情况下)和元素中的prev指针,所以典型的列表操作(如replace

是否有可用于 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;
  }
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!