在endpoint和元素之前/之后以恒定时间插入的数据结构？

Question

我正在寻找一种数据结构：

• 具有无界的大小。
• 保持其元素的插入顺序。
• 在列表的开头和结尾有效地插入（理想情况下为常量时间）。
• 在现有元素之前或之后有效地插入（理想情况下是在恒定时间内）。

我排除了ArrayList，因为它在列表开头插入时效率不高。

表面上LinkedList应该是一个完美的匹配，但实际上Java实现在插入现有元素之前或之后并不有效（即它遍历整个列表以查找插入位置）。

（我个人不需要存储重复的元素，但其他人可能会）

动机：我正在构建一个允许偶尔作弊的事件队列（在现有事件之前或之后插入）。

Answer 1

我正在构建一个允许偶尔作弊的事件队列（在现有事件之前或之后插入）。

如果作弊很少，那就选择你自己的基于数组的结构。java.util.ArrayDeque在O（1）中处理两端，但它不能在中间进行插入。它们可以很容易地添加，但复杂性是O（n）。

请注意，LinkedList对于大多数操作（由于其糟糕的数据局部性）比ArrayList和ArrayDeque慢得多。

让我们假设，你非常需要在中间插入恒定的时间。差不多

insertAfter(existingElement, newElement);

java的问题。util。LinkedList就是它没有这样的操作。它所拥有的是 ListItRealter < /Cord>，它允许你在中间插入，但是只有当你先定位你的迭代器（O（n））时才有帮助。

所以你需要自己的链表。基本实现相当简单，您还需要直接访问其节点（包含next和prev链接的内容，而不是添加的内容）。然后维护一张地图

要消除边界情况（第一个/最后一个/唯一的节点），请在链接列表中添加两个虚拟节点（prefirst和postlast）。显然，这些是唯一不会存储在地图中的节点。它们使实现变得非常简单，例如。，

void insertAfter(MyThing existingElement, MyThing newElement) {
   Node found = map.get(existingElement);
   if (found == null) throw ...
   Node newNode = new Node(newElement);
   map.put(newElement, newNode);

   // Link newNode where it belongs to.
   newNode.next = found.next;
   newNode.prev = found;

   // Fix links.
   newNode.prev.next = newNode;
   newNode.next.prev = newNode;   
}

void insertFirst(MyThing newElement) {
   Node found = prefirst;

   // All the remaining code is simply copied from above.
   // Factor it out.

   Node newNode = new Node(newElement);
   map.put(newElement, newNode);

   // Link newNode where it belongs to.
   newNode.next = found.next;
   newNode.prev = found;

   // Fix links.
   newNode.prev.next = newNode;
   newNode.next.prev = newNode;   
}

Answer 2

AVL树怎么样？因为树总是平衡的，所以它的高度为O（log（N）），其中N是树中的节点数。这将使最坏情况下的插入也为O（log（N））。

我相信对于你所寻找的东西来说，这是尽可能接近恒定的时间。抱歉，如果这不是答案，我的声誉还不足以发表评论：/

Answer 3

老实说，我认为一个LinkedList的定制实现将是最好的选择：

• 具有无界大小。
  • 是的。
  • 对
  • 是的，还有O（1）
  • 如果你维护一张地图

  根据事件的总量（以及事件作弊的频率），还可以考虑使用线性时间，从而允许您使用API的LinkedList实现。