为什么Java中没有SortedList？

Question

在Java中，有 SortedSet 和 SortedMap 两个接口。它们都属于Java集合框架，提供了一种排序访问元素的方式。

然而，在我的理解中，Java中没有SortedList。可以使用java.util.Collections.sort()对列表进行排序。

为什么Java没有设计SortedList呢？您有什么想法吗？

- Jijoy

---

这个链接是否对你有帮助？ - Nico Haase

当你在列表中间插入一个元素时，你希望得到什么样的结果？ - bestsss

完全可以创建一个SortedList类，该类不实现java.util.List接口。把问题看作是对没有支持所需功能的数据结构进行的询问。不要被像命名这样微不足道的细节所分散注意力。 - Alderath

@Alderath，通常的结构是树（红黑树、AVL树或B树），带有额外的prev/next链接来支持排序。我使用类似的红黑树结构，带有prev/next链接。虽然它是一个相当小众的用途，但树可以按顺序遍历和插入顺序，具有O(logn)的查找/包含，但get(int)是O(n)的。考虑到它的小众适用性，我认为如果需要，开发人员应该自己实现一个。 - bestsss

不回答“为什么”的问题，但对于TreeSet来说，最简单的解决方法是使用一个永远不会返回零的比较器，例如int diff = this.score - that.score;``return (diff == 0) ? 1 : diff;。由于这是一种不好的做法，建议将其作为匿名构造函数参数提供，而不是实现Comparable接口。 - earcam

Answer 1

列表迭代器首先保证您以列表的内部顺序（即插入顺序）获取列表的元素。更具体地说，它是按照您插入元素或操作列表的方式排序的。排序可以看作是对数据结构的一种操作，有多种方法可以对列表进行排序。

我会按我个人认为的有用程度的顺序列出这些方法：

1. 考虑使用Set或Bag集合

注意：我把这个选项放在首位，因为这通常是您想要做的。

一个已排序的集合在插入时自动对集合进行排序，这意味着在将元素添加到集合时进行排序。这也意味着您不需要手动排序。

此外，如果您确信不需要担心（或者没有）重复元素，那么可以使用TreeSet<T>。它实现了SortedSet和NavigableSet接口，并且像列表一样工作。

TreeSet<String> set = new TreeSet<String>();
set.add("lol");
set.add("cat");
// automatically sorts natural order when adding

for (String s : set) {
    System.out.println(s);
}
// Prints out "cat" and "lol"

如果您不想使用自然排序，可以使用带有Comparator<T>参数的构造函数。

另外，您可以使用Multisets（也称为Bags），它是允许重复元素的Set，并且有第三方实现。最著名的是来自Guava libraries的一个TreeMultiset，它的工作原理很像TreeSet。

2.使用Collections.sort()对列表进行排序

如上所述，List的排序是一种数据结构的操作。因此，在需要“单一真相源”以各种方式排序的情况下，手动排序是正确的选择。

您可以使用java.util.Collections.sort()方法对列表进行排序。以下是一个代码示例:

List<String> strings = new ArrayList<String>()
strings.add("lol");
strings.add("cat");

Collections.sort(strings);
for (String s : strings) {
    System.out.println(s);
}
// Prints out "cat" and "lol"

使用比较器

一个明显的好处是，你可以在 sort 方法中使用 Comparator。Java 还提供了一些实现了 Comparator 接口的类，例如 Collator，它非常适用于区域敏感的字符串排序。以下是一个示例：

Collator usCollator = Collator.getInstance(Locale.US);
usCollator.setStrength(Collator.PRIMARY); // ignores casing

Collections.sort(strings, usCollator);

并发环境下的排序

需要注意的是，在并发环境下使用sort方法并不友好，因为集合实例将被修改，您应该考虑使用不可变集合。这是Guava在Ordering类中提供的一个简单方法：

List<string> sorted = Ordering.natural().sortedCopy(strings);

3. 使用java.util.PriorityQueue来包装您的列表

虽然 Java 中没有排序列表，但是有一个已排序队列，可能对您也同样有效。它就是 java.util.PriorityQueue 类。

Nico Haase 在评论中链接了一个相关问题，也回答了这个问题。

在已排序集合中，您最有可能不想操纵内部数据结构，这就是为什么 PriorityQueue 没有实现 List 接口的原因（因为这会直接访问其元素）。

PriorityQueue 迭代器的注意事项

PriorityQueue 类实现了 Iterable<E> 和 Collection<E> 接口，因此可以像通常一样迭代。但是，迭代器无法保证按排序顺序返回元素。相反（正如 Alderath 在评论中指出的那样），您需要使用 poll() 函数直到队列为空。

请注意，可以通过接受任何集合的构造函数将列表转换为优先队列：

List<String> strings = new ArrayList<String>()
strings.add("lol");
strings.add("cat");

PriorityQueue<String> sortedStrings = new PriorityQueue(strings);
while(!sortedStrings.isEmpty()) {
    System.out.println(sortedStrings.poll());
}
// Prints out "cat" and "lol"

4. 编写自己的 SortedList 类

注意：您不应该这样做。

您可以编写自己的 List 类，在每次添加新元素时进行排序。这可能会大量消耗计算资源，取决于您的实现方式并且是无意义的，除非您想将其作为练习，因为有两个主要原因：

1. 它违反了 List<E> 接口的契约，因为 add 方法应该确保元素驻留在用户指定的索引中。
2. 为什么要重复发明轮子？正如上面第一个原因所指出的那样，您应该使用 TreeSet 或 Multiset。

但是，如果您想将其作为练习，这里是一个代码示例，它使用了 AbstractList 抽象类：

public class SortedList<E> extends AbstractList<E> {

    private ArrayList<E> internalList = new ArrayList<E>();

    // Note that add(E e) in AbstractList is calling this one
    @Override 
    public void add(int position, E e) {
        internalList.add(e);
        Collections.sort(internalList, null);
    }

    @Override
    public E get(int i) {
        return internalList.get(i);
    }

    @Override
    public int size() {
        return internalList.size();
    }

}

请注意，如果您没有覆盖需要的方法，则来自AbstractList的默认实现会抛出UnsupportedOperationException异常。

- Spoike

---

在我看来，这个回答比得票最高的回答更具建设性。不过，它有两个小缺点。优先队列不支持随机访问，你不能做peek(elementIndex)这样的操作，所以你不能写例如Integer maxVal = prioQueue.peek(prioQueue.size() - 1);。其次，如果你想把优先队列简单地用作排序列表，代码中看到“PriorityQueue”会比看到“SortedList”不太直观，如果这样的数据结构存在的话。 - Alderath

在评论中看到其他问题后，另一个重大缺点是PriorityQueue的迭代器不能保证以任何特定顺序返回元素。因此，除非我忽略了什么，否则按顺序打印PriorityQueue中的所有对象的唯一方法是重复地poll()队列直到它为空。对我来说，这感觉有些愚蠢。要两次打印PriorityQueue中的对象，您首先必须复制PriorityQueue，然后从原始PriorityQueue和副本中依次pol()l所有对象。 - Alderath

优先队列就是一个堆，你只能访问顶部，我认为它不属于问题的答案。 - bestsss

值得注意的是，Collections.sort() 方法甚至允许您使用 Comparator 对象定义用于排序的比较函数。 - Mike 'Pomax' Kamermans

TreeMultiset 以非常奇怪的方式允许重复。如果您有两个具有相同键的对象，它不会实际将所有对象插入 Multiset，而只是跟踪匹配该键的计数。如果您使用基元类型，则此操作是可以接受的。但如果您使用对象并计划使用对象的其他部分，则它将无法返回预期的对象。 - Caitlin

Answer 2

由于列表的概念与自动排序集合的概念不兼容。列表的重点在于，在调用list.add(7, elem)之后，调用list.get(7)将返回elem。对于自动排序列表，元素可能会出现在任意位置。

- Michael Borgwardt

---

“List”这个概念意味着有某种顺序，并且“list.get(n)”操作是确定性的，也就是说，只要列表没有被修改，它将始终返回位置“n”上相同的元素。我不同意“List”的概念需要保证插入顺序。是的，“List”接口确实具有list.add(index, element)方法，但对于排序集合来说是没有意义的，但根据文档，它是可选的。 - matt-pielat

Answer 3

由于所有列表已经按照添加项目的顺序（FIFO顺序）“排序”，您可以使用 java.util.Collections.sort() 以另一种顺序“重新排序”它们，包括元素的自然顺序。

编辑：

作为数据结构的列表基于插入项的顺序很有趣。

集合不具备该信息。

如果您想按添加时间排序，请使用List。 如果要按其他条件排序，请使用 SortedSet。

- SJuan76

---

集合不允许重复元素。 - bestsss

我认为这并不是一个非常好的答案。确实，Java API中的列表具有按照元素插入的时间/方式确定顺序的特定顺序。但是，以插入方法/时间为依据排序的列表的存在，并不妨碍有其他数据结构，该结构的顺序由另一种方式（例如，通过比较器）确定。基本上，OP想知道为什么没有一个数据结构等同于SortedSet，除了该数据结构应允许多个相等元素的出现。 - Alderath

我的后续问题是：“为什么没有一种数据结构可以像SortedSet一样工作，但可以包含多个相等的元素？”（请不要回答“因为集合只能包含一个元素”） - Alderath

我认为句子“列表已按其顺序排序”有点误导。是的，List具有默认的FIFO排序（即添加项目的顺序），但是读到这句话时，我想到的是元素的自然排序，这是一种有点不同的东西。我建议进行编辑。 - usr-local-ΕΨΗΕΛΩΝ

即使你在“sorted”一词外加上双引号，列表也并非“已排序”。它们是有序的，但不保证排序。 - Koray Tugay

Answer 4

集合(Set)和映射(Map)是非线性数据结构。列表(List)是线性数据结构。

---

树形数据结构SortedSet和SortedMap接口使用红黑树实现算法分别实现了TreeSet和TreeMap。因此，它确保没有重复的项目（或在Map的情况下是键）。

• List已经维护了一个有序的集合和基于索引的数据结构，而树不是基于索引的数据结构。
• 根据定义，Tree不能包含重复的元素。
• 在List中，我们可以有重复的元素，因此没有TreeList（即没有SortedList）。
• List按照插入顺序维护元素。因此，如果我们想对列表进行排序，我们必须使用java.util.Collections.sort()。它根据其元素的自然顺序将指定的列表排序为升序。

- Premraj

---

为什么集合和映射是非线性数据结构？你可以在它们上面模拟一个数组。 - piepi

Answer 5

JavaFX SortedList

虽然花费了一些时间，但Java 8确实拥有一个排序的List。 http://docs.oracle.com/javase/8/javafx/api/javafx/collections/transformation/SortedList.html

正如您在javadocs中所看到的，它是JavaFX集合的一部分，旨在为ObservableList提供排序视图。

更新：请注意，随着Java 11的发布，JavaFX工具包已经移出JDK并成为一个单独的库。 JavaFX 11可作为可下载SDK或从MavenCentral获取。请参见https://openjfx.io

- swpalmer

---

不幸的是，这个 SortedList 不像通常的列表一样工作 - 例如，它没有默认构造函数（你必须使用 ObservableList 构造它，不管那意味着什么...） - Erel Segal-Halevi

JavaFX中的SortedList明显是用于GUI组件的使用，因为它具有额外的开销，不适合仅仅拥有已排序对象列表的情况。此外，即使在项目中没有使用GUI，也意味着要引用整个FX模块。 - COBRA.cH

@COBRA.cH 是的，没错。一个更高性能的有序列表可能只需要在 TreeMap 的外面加上一个薄的包装器，其中整数用于计算键的重复次数。您还可以使用 TreeSet 和一个永远不返回 0 的比较器。 - swpalmer

为什么会有负评？这个问题的前提是JDK库中没有排序列表。这个答案纠正了这个假设。你是否喜欢或不喜欢这个特定排序列表的实现并不是负评的理由。这个答案并没有推荐这个类，只是指出它的存在。 - Basil Bourque

Answer 6

对于任何新手来说，从2015年4月开始，Android现在在支持库中有一个SortedList类，专门设计用于与RecyclerView一起使用。这是关于它的博客文章。

- Jim Pekarek

---

值得注意的是，在本评论发布时，Android的SortedList与RecyclerView缺乏对onItemMoved()功能的支持。为了绕过这些限制，我不得不编写自己的较低效的SortedList。 - Matthew

Answer 7

另一个需要考虑的问题是插入操作的时间复杂度。 对于列表插入，人们期望其复杂度为O(1)。 但是对于排序列表，这不能得到保证。

最重要的一点是列表对其元素没有任何假设。 例如，您可以将不实现equals或compare的东西制作成列表。

- Ingo

---

你可以使用具有O(logn)插入/删除/查找/包含功能的列表，但不能使用get(int)。 - bestsss

最后一点并不是一个好的解释。你可以使用实现了Comparator接口的SortedSet，以对不实现Comparable接口的对象进行排序。参考TreeSet构造函数。 - Alderath

@Alderath - 或许我的措辞太过温和了。但是观察表明，集合的元素和树的键至少需要可比较相等性，而列表元素则不需要。无论Sets和Trees的排序/相等关系是在比较器中实现还是其他地方实现都无关紧要 - 但你需要一个。 - Ingo

列表不保证O(1) _插入_，它们保证O(1) _访问_。http://bigocheatsheet.com/ - Matt Quigley

@Betlista 你说得对！我无法更新我的评论，但是Java的List接口不保证其方法的任何性能规范。 - Matt Quigley

@MattQuigley 值得注意的微妙差别：ArrayList 提供 O(1) 的 遍历时间，一旦到达目标位置，提供 O(1) 的访问时间。而链表则提供 O(n) 的 遍历时间，同样一旦到达目标位置，提供 O(1) 的访问时间。排序结构通常提供 O(log(n)) 的 遍历时间，一旦到达目标位置，提供 O(1) 的访问速度。除了遍历之外，其他操作可能具有不同的复杂度。例如，对于它们各自的实现，插入的复杂度分别为 O(n)、O(1) 和 O(log(n))。 - Simply Beautiful Art

Answer 8

想象一下，List接口有像add(int index, E element)、set(int index, E element)这样的方法。它们的约定是，一旦你在位置X添加了一个元素，除非你在它之前或之后添加或删除元素，否则你将在那里找到它。

如果任何列表实现以除索引之外的某种顺序存储元素，上述列表方法就毫无意义。

- Costi Ciudatu

Answer 9

如果您想要一种方法来对元素进行排序，并且还能够以有效的方式通过索引访问它们，您可以按照以下步骤操作：

1. 使用随机访问列表进行存储（例如ArrayList）
2. 确保它始终是有序的

然后，要添加或删除一个元素，可以使用Collections.binarySearch获取插入/删除索引。由于您的列表实现了随机访问，因此可以使用确定的索引高效地修改列表。

示例：

/**
 * @deprecated
 *      Only for demonstration purposes. Implementation is incomplete and does not 
 *      handle invalid arguments.
 */
@Deprecated
public class SortingList<E extends Comparable<E>> {
    private ArrayList<E> delegate;
    
    public SortingList() {
        delegate = new ArrayList<>();
    }
    
    public void add(E e) {
        int insertionIndex = Collections.binarySearch(delegate, e);
        
        // < 0 if element is not in the list, see Collections.binarySearch
        if (insertionIndex < 0) {
            insertionIndex = -(insertionIndex + 1);
        }
        else {
            // Insertion index is index of existing element, to add new element 
            // behind it increase index
            insertionIndex++;
        }
        
        delegate.add(insertionIndex, e);
    }
    
    public void remove(E e) {
        int index = Collections.binarySearch(delegate, e);
        delegate.remove(index);
    }
    
    public E get(int index) {
        return delegate.get(index);
    }
}

(在这个答案中，您可以看到更完整的实现。)

- Marcono1234

Answer 10

列表 API 中的第一行说明它是一个有序集合（也称为序列）。如果你对列表进行排序，就不能保持原来的顺序，因此 Java 中没有 TreeList。
API 表明 Java 的 List 受到序列的启发，并看到序列的属性 http://en.wikipedia.org/wiki/Sequence_(mathematics)。

这并不意味着你不能对列表进行排序，但 Java 严格遵循其定义，并不默认提供已排序的列表版本。

- Syam

---

https://commons.apache.org/proper/commons-collections/apidocs/org/apache/commons/collections4/list/TreeList.html - spudone