java - 给定一个元素时，哪个 Java 集合的链表在 O(1) 中添加？

Question

我需要插入一个非常大的 LinkedList，我将其元素保存在一个快速访问的 HashMap 中。
保持列表有序(这不是键的自然顺序)很重要。

我认为可以对链表节点进行哈希处理，然后直接在节点上插入(从映射中获取节点+插入链表==常数时间)。

但是，我找不到任何可以执行此操作或类似操作的 Java 集合...
我目前使用的是 LinkedHashMap，它不符合上述要求。

谢谢，asaf :-)

Answer 1

如果 LinkedList 在每次插入后都进行排序，我怀疑你能否找到这样的数据结构，因为这意味着你会得到一个时间复杂度为 O(n) 的排序算法，这已被证明是不可能的。 (排序的最低限度是 O(n log n)。)插入时的最佳限度是 O(log n)。

然后你可以使用TreeMap数据结构。