0

Java 提供了 List 接口的 LinkedList 实现，它实际上是一个双向链表。如果我们执行以下操作：

linkedlist.remove(obj);

接着：

linkedlist.add(obj);

我们实际上从链表中删除对象 obj 并从右端（尾部）重新插入它。

我们还可以手动实现带有节点、头和尾的链表。在诸如 C++ 等具有一些低级特性的语言中，可以使用指针指向 obj 对象的下一个和上一个对象。因此，我们实际上不必删除该项目，而只需更新前一个和下一个指针。

Java中是否有任何数据结构可以产生相同的效果（因此仅删除对象本身的“指针”可以获得相同的性能增益）？

请注意，我想使用现成的数据结构，而不是手动编写我的一个链表实现（并且可能重新发明轮子）。此外，请注意它不一定是链表 - 例如，它可能是某种队列，例如 ArrayDeque。

编辑：换一种说法，如果 Java 中 List 接口的 LinkedList 实现在内部使用了 prev 和 next 指针，那么为什么 l.remove(obj) 是 O(n) 而不是 O(1)？因此在实践中，当您有一个包含数百万个对象的 LinkedList（如我的情况）时，执行此删除和重新插入需要很长时间？（与 ArrayList 相同，与 ArrayDeque 相同 - 很长时间）。

4

2 回答 2

4

Java 做的事情与 C++ 完全相同。所有对对象的引用都是指针。所以，在像这样的节点中

public class Node [
    private Object value;
    private Node next;
    private Node previous;
}

value,next和previous分别是指向节点、下一个节点和前一个节点的值的指针（在 Java 中称为引用）。

与 C++ 的不同之处在于您没有指针算术:value++例如，它不会编译并且不会使指针引用位于下一个内存地址的内容。

编辑：

LinkedList 类不会将其节点暴露给外部。它们对 LinkedList 是完全私有的。因此，删除对象包括遍历所有节点以找到具有等于（根据Object.equals()）给定对象的值的节点，并从列表中删除找到的节点。删除节点包括使前一个点指向下一个，反之亦然。这就是为什么移除一个对象是 O(n) 的原因。当然，如果您可以访问节点并且能够将其删除，那么操作将是 O(1)。如果需要，您必须实现自己的 LinkedList，与在 C++ 中实现的方式完全相同。引用是指针。

于 2014-03-03T16:15:28.890 回答
1

要回答为什么remove(Object obj)是 O(n) 的问题：

首先，为了使其成为 O(1)，您需要提供remove实际Node参考，而不是Object. Object不会Node指向. 为了找到正确Node的返回值，代码必须要么搜索列表以找到Node包含对象的 ，要么保留一个哈希映射，让它找到Node. 实际的LinkedList实现做了一个简单的线性搜索。然而，从技术上讲，即使是哈希映射也是 O(n)，因为列表中的所有对象都有可能具有相同的哈希码，尽管它仍然比线性搜索快得多。

其次，remove(Object obj)是根据 来定义的equals。如果有一个不同的对象obj2被添加到列表中，并且obj2.equals(obj)is true，那么如果引用本身从未添加到列表 中，remove(obj)则将删除。obj2obj

要真正做到这一点，您需要一个add返回节点引用的方法，以便您的程序可以跟踪节点引用并将其用作remove参数；或者您可以要求列表中的对象实现某种NodePointer接口：

interface NodePointer {
    void setNodePointer(Object node);
    Object getNodePointer();
}

然后列表将使用该列表将节点指针填充到对象中。（但这可能意味着一个对象一次只能存在于一个链表上，这是一个LinkedList不会强加的限制。）在任何一种情况下，我都不认为这是 Java 库支持的东西。

于 2014-03-03T16:38:22.690 回答