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

Question

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

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

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

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

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

---

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

标签： javaperformancelist

Answer 1

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

• 具有无限大小。
  • 是的。
• 保持其元素的插入顺序。
  • 是的。
• 在列表的开头和结尾有效插入（理想情况下在恒定时间内）。
  • 是的，而且 O(1)。
• 在现有元素之前或之后有效插入（最好是在恒定时间内）。
  • 如果您Map<?, Node>在插入/删除元素时维护 a ，那么您可以Node在恒定时间内访问 a （及其上一个/下一个节点）并以这种方式插入/删除。

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