Java.util包中是否有可索引的排序列表？

Question

我正在寻找java.util包中的数据结构.我需要它来满足以下要求:

• 元素的数量(理论上)是无界的.
• 元素按升序排序.
• 你可以获得第n个元素(快速).
• 您可以删除第n个元素(快速).

我希望找到一个可索引的跳过列表,但我没有.他们是否有任何符合我所述要求的数据结构？

Answer 1

Java标准库中没有这样的容器.

当我需要具有这些属性的数据结构时,我使用了一个List实现(通常是一个ArrayList,但没关系),并且我使用了所有的插入Collections.binarySearch.

如果我有封装排序列表作为一个可重用的类,我实现了List接口,所有的委托方法"标准" List实现(它甚至可以作为一个参数构造函数传递).我想实现在每次插入法(加,中的addAll,设置,迭代器的remove)抛出一个异常(UnsupportedOperationException),这样就没有人能打破"总排序"属性.最后,我想提供一种方法insertSorted,将用Collections.binarySearch做插入.

Answer 2

不存在满足您所有标准的简单数据结构。

据我所知，唯一能够满足所有这些要求的是可索引的跳过列表。然而，我不知道有任何现成的 Java 实现。