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

data-structures collections java sortedlist

2022-09-02 10:52:09

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

元素的数量（理论上）是无限的。
元素按升序排序。
您可以获取第 n 个元素（快速）。
您可以删除第 n 个元素（快速）。

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

答案 1

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

当我需要具有这些属性的数据结构时，我使用一个实现（通常是，但这并不重要），并且我使用 Collections.binarySearch 执行所有插入。ListArrayList

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

答案 2

不存在满足所有条件的简单数据结构。

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