我正在寻找一种数据结构：
我排除了ArrayList，因为它在列表开头插入时效率不高。
表面上LinkedList应该是一个完美的匹配，但实际上Java实现在插入现有元素之前或之后并不有效（即它遍历整个列表以查找插入位置）。
（我个人不需要存储重复的元素，但其他人可能会）
动机：我正在构建一个允许偶尔作弊的事件队列（在现有事件之前或之后插入）。
老实说，我认为一个LinkedList的定制实现将是最好的选择：
地图根据事件的总量（以及事件作弊的频率），还可以考虑使用线性时间，从而允许您使用API的LinkedList实现。
AVL树怎么样？因为树总是平衡的，所以它的高度为O（log（N）），其中N是树中的节点数。这将使最坏情况下的插入也为O（log（N））。
我相信对于你所寻找的东西来说，这是尽可能接近恒定的时间。抱歉，如果这不是答案，我的声誉还不足以发表评论：/
我正在构建一个允许偶尔作弊的事件队列（在现有事件之前或之后插入）。
如果作弊很少，那就选择你自己的基于数组的结构。java.util.ArrayDeque在O（1）中处理两端，但它不能在中间进行插入。它们可以很容易地添加，但复杂性是O（n）。
请注意，LinkedList对于大多数操作（由于其糟糕的数据局部性）比ArrayList和ArrayDeque慢得多。
让我们假设，你非常需要在中间插入恒定的时间。差不多
insertAfter(existingElement, newElement);
java的问题。util。LinkedList就是它没有这样的操作。它所拥有的是
所以你需要自己的链表。基本实现相当简单，您还需要直接访问其节点（包含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;
}
