在给定元素时,哪个Java集合的链接列表添加到O(1)中?

如果在每次插入之后对LinkedList进行排序,我怀疑您是否能够找到这样的数据结构,因为这意味着您将得到一个时间复杂度为o(n)的排序算法,这已被证明是不可能的。(排序的最低界限是O(n log n)。)插入时可以获得的最佳值是O(log n)。

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

使用treeset或treemap。插入是O(log(n)),但记住这意味着日志。因此,如果您有40亿个条目,那么运行时是O(32)。如果你有2个 ^六十四 条目,然后插入需要O(64),所以这不是什么大问题。

因为“保持列表的有序性很重要”,所以有效地执行 insertion sort 具有O(n)的最佳情况性能。此外,不能将散列与排序混淆,因为散列的顺序没有定义,因为它取决于基础散列表的大小。(仅当您知道要插入的节点的前置节点或后续节点时,使用哈希进行插入才有用)

当你说你必须保持你的列表的顺序-但这不是键的自然顺序,我听到你说你必须保持插入顺序。

但我不知道为什么Linkedhashmap不符合你的要求。

你能解释一下Linkedhashmap失败了什么吗?