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

Question

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

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

我希望找到一个可索引的跳过列表，但我没有。他们有满足我所说的要求的数据结构吗？

Answer 1

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

当我需要具有这些属性的数据结构时，我使用 List 实现（通常是 ArrayList，但这并不重要），并且使用 < a href="http://download.oracle.com/javase/6/docs/api/java/util/Collections.html#binarySearch(java.util.List,%20T)" rel="noreferrer">Collections.binarySearch。

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

Answer 2

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

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

Answer 3

非常相似

• 这个问题与Sorted array list in Java

，看看< a href="https://stackoverflow.com/questions/4031572/sorted-array-list-in-java/4031849#4031849">我对该问题的回答。

基本上它建议如下：

class SortedArrayList<T> extends ArrayList<T> {

    @SuppressWarnings("unchecked")
    public void insertSorted(T value) {
        add(value);
        Comparable<T> cmp = (Comparable<T>) value;
        for (int i = size()-1; i > 0 && cmp.compareTo(get(i-1)) < 0; i--) {
            T tmp = get(i);
            set(i, get(i-1));
            set(i-1, tmp);
        }
    }
}

---

关于您的第一个要求的注释：“元素的数量是无限的。”：

您可能希望将其限制为“元素的数量不应受到更少的限制”大于 2³¹-1...”，否则您将排除 Java 数组支持的所有选项。 （您可以使用 LinkedList 等任意数量的元素，但我不知道如何在其中进行快速查找。）

Answer 4

TreeSet 为您提供在向列表添加元素时自然排序的功能。
但如果您不需要这个并且允许使用 Collections.sort()，您可以使用简单的 ArrayList。

Answer 5

考虑将 List 与 Collections.sort() 结合使用。

Answer 6

按照 dwb 使用 List 和 Collections.sort() 的说明，您可以使用 ArrayList 来实现 List（并且不会像 Vector 那样同步，除非您当然想要这种开销）。这可能是你最好的选择，因为他们（Sun）通常对这些领域进行大量研究（无论如何，从我所看到的来看）。如果您需要按“默认”以外的其他方式排序（即您不对整数列表等进行排序），请提供您自己的比较器。

编辑：唯一不满足您的要求的是快速删除......

Answer 7

查看 PriorityQueue。

如果您的数据结构中不需要类似的元素，那么通常的 TreeSet 也适合您的要求。