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

Question

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

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

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

Answer 1

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

当我需要具有这些属性的数据结构时，我使用 List 实现(通常是 ArrayList，但没关系)，然后我完成所有使用 Collections.binarySearch 插入.

如果我必须将排序列表封装为可重用类，我会实现 List 接口(interface)，将所有方法委托(delegate)给“标准”List 实现(它甚至可以作为参数传递给构造函数)。我会通过抛出异常(UnsupportedOperationException)来实现每个插入方法(add、addAll、set、Iterator's remove)，这样没有人可以破坏“始终排序”的属性。最后，我将提供一个 insertSorted 方法，该方法将使用 Collections.binarySearch 进行插入。