0

在我看来，没有办法在 O(1) 时间内在 Deque 类的中间某处插入元素。我想在哈希表中维护对双端队列中特定节点的引用，如果我需要删除这个节点，我只需转到它的 prev 并设置 prev.next=this.next 和类似的 this.next.prev =prev 并删除这个当前元素。

但是如果我有一个双端队列

Deque<String> myDeque = new ArrayDeque<String>();
or 
Deque<String> myDeque = new LinkedList<String>();

这些都不会提供这个。

有没有替代方案？如果我必须实现自己的双向链表，有没有一种方法可以通过扩展 ArrayDeque 已经完成的功能来消除，这样我就不必重写插入等的代码？...据我所知...我不这么认为 :( :(

4

2 回答 2

2

如果不编写自己的 Deque，这是不可能的。然而：

如果我理解正确，您希望在具有 Deque 接口的对象中的一个特定点进行 O(1) 删除和插入？我可以建议您使用两个Deques 吗？

插入和删除一开始只在其中一个中进行Deque，直到遇到要保存的节点。此时，根据您是在前面还是在后面插入此节点，您不这样做，而是将节点插入 empty Deque，并且该 emptyDeque成为您在前面的所有插入和删除的目标或从那时起背面，另一个Deque只处理背面或正面的插入和移除。

这可能会扩展到几个关键节点（导致使用[number of nodes]+1 Deques），只有插入/删除发生在一个节点的前面和另一个节点Deque的后面Deque（所有其他节点都是静态的）。您还必须引入一个固定约定，即每个中的第一个或最后一个项目Deque（第一个或最后一个除外Deque）是一个“关键”节点。

当然，如果你在很多点上随机插入和删除，问题就变成了：你为什么坚持使用双端队列？

于 2013-09-26T13:18:36.127 回答
2

我不会删除节点。相反，当您从 Deque 中获取它时，我会检查您要删除/忽略的元素集合，然后在需要时将其丢弃。

于 2013-09-26T12:44:34.027 回答