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

Question

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

• 具有无限大小。
• 维护其元素的插入顺序。
• 在列表的开头和结尾高效地插入(理想情况下是在常数时间内)。
• 在现有元素之前或之后高效地插入(理想情况下是在常数时间内)。

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

表面上 LinkedList 应该是完美匹配，但实际上 Java 实现在现有元素之前或之后插入时效率不高(即它遍历整个列表以找到插入位置) .

(我个人不需要存储重复元素，但其他人可能需要)

---

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

Answer 1

老实说，我认为 LinkedList 的自定义实现将是要走的路:

• 具有无限大小。
  • 是的。
• 维护其元素的插入顺序。
  • 是的。
• 在列表的开头和结尾高效地插入(理想情况下是在常数时间内)。
  • 是的，O(1)。
• 在现有元素之前或之后高效地插入(理想情况下是在常数时间内)。
  • 如果您维护 Map<?, Node>插入/删除元素时，您可以访问 Node (及其上一个/下一个节点)在恒定时间内插入/删除。

根据事件总量(以及事件作弊的频率)，也可以考虑线性时间，允许您使用 API 的 LinkedList 实现.