为什么Java中没有SortedList？

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

我将按照我个人认为的有用性顺序排列方式：

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 在评论中链接到一个也回答了这个问题的 related question。

在排序的集合中，您很可能不想操作内部数据结构，这就是 PriorityQueue 不实现 List 接口的原因（因为这将使您可以直接访问其元素）。

关于 PriorityQueue 迭代器的警告

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

请注意，您可以通过 constructor that takes any collection 将列表转换为优先级队列：

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 类，在每次添加新元素时进行排序。根据您的实现，这可能会变得相当繁重并且毫无意义，除非您想将其作为练习来进行，原因有两个：

它打破了 List 接口的约定，因为 add 方法应确保元素将驻留在用户指定的索引中。为什么要重新发明轮子？正如上面第一点所指出的，您应该使用 TreeSet 或 Multisets。

但是，如果您想将其作为练习，这里有一个代码示例可以帮助您入门，它使用 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。

---

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

---

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

编辑：

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

套装没有该信息。

如果您想通过添加时间来订购，请使用 List。如果您想按其他标准排序，请使用 SortedSet。

---

Set 和 Map 是非线性数据结构。列表是线性数据结构。

https://i.stack.imgur.com/rsbMd.gif

树数据结构SortedSet和SortedMap接口分别使用使用的Red-Black tree实现算法实现TreeSet和TreeMap。因此它确保没有重复的项目（或 Map 的情况下的键）。

List 已经维护了一个有序集合和基于索引的数据结构，而树不是基于索引的数据结构。

根据定义，树不能包含重复项。

在 List 中我们可以有重复项，因此没有 TreeList（即没有 SortedList）。

List 按插入顺序维护元素。因此，如果我们想对列表进行排序，我们必须使用 java.util.Collections.sort()。它根据元素的自然顺序将指定列表按升序排序。

---

JavaFX 排序列表

尽管花了一些时间，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

---

对于任何新手，截至 2015 年 4 月，Android 现在在支持库中有一个 SortedList 类，专门设计用于与 RecyclerView 一起使用。这是关于它的blog post。

---

还有一点是插入操作的时间复杂度。对于列表插入，人们期望复杂度为 O(1)。但这不能用排序列表来保证。

最重要的一点是列表对它们的元素没有任何假设。例如，您可以列出未实现 equals 或 compare 的事物。

---

可以这样想：List 接口具有 add(int index, E element)、set(int index, E element) 等方法。约定是，一旦您在位置 X 添加了一个元素，您就会在那里找到它，除非您在它之前添加或删除元素。

如果任何列表实现会以某种顺序存储元素而不是基于索引，那么上述列表方法将毫无意义。

---

如果您正在寻找一种对元素进行排序的方法，但也能够通过索引以有效的方式访问它们，您可以执行以下操作：

使用随机访问列表进行存储（例如 ArrayList） 确保始终排序

然后要添加或删除一个元素，您可以使用 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);
    }
}

（在 this answer 中查看更完整的实现）

---

List API 中的第一行表示它是一个有序集合（也称为序列）。如果对列表进行排序，则无法保持顺序，因此 Java 中没有 TreeList。
正如 API 所说，Java List 的灵感来自于 Sequence 并查看序列属性 http://en.wikipedia.org/wiki/Sequence_(mathematics）

这并不意味着您不能对列表进行排序，而是 Java 严格遵守他的定义，并且默认情况下不提供列表的排序版本。

---

我认为由于以下原因，以上所有内容都不能回答这个问题，

由于可以通过使用其他集合来实现相同的功能，例如 TreeSet、Collections、PriorityQueue..etc（但这是一种替代方案，它也会施加它们的约束，即 Set 将删除重复的元素。简单地说，即使它没有施加任何约束，它没有回答为什么 SortedList 不是由 java 社区创建的问题）因为 List 元素不实现 compare/equals 方法（这适用于 Set & Map 也适用于一般项目不实现 Comparable 接口但当我们需要这些项目时按排序顺序并希望使用 TreeSet/TreeMap，项目应实现 Comparable 接口）由于 List 使用索引并且由于排序而无法工作（这可以通过引入中间接口/抽象类轻松处理）

但是没有人告诉它背后的确切原因，因为我相信这些问题最好由 java 社区本身来回答，因为它只有一个具体的答案，但让我尽力回答如下，

正如我们所知，排序是一项昂贵的操作，List 和 Set/Map 之间存在一个基本区别，即 List 可以有重复项，而 Set/Map 则不能。这就是为什么我们以 TreeSet/TreeMap 的形式获得 Set/Map 的默认实现的核心原因。在内部，这是一个红黑树，每个操作（插入/删除/搜索）都具有 O(log N) 的复杂性，其中由于重复，列表无法适应此数据存储结构。

现在问题来了，我们也可以为 List 选择一个默认的排序方法，也可以像 MergeSort 那样被 Collections.sort(list) 方法使用，复杂度为 O(N log N)。社区并没有故意这样做，因为我们确实有多种排序算法可供选择，用于非不同元素的排序算法，如 QuickSort、ShellSort、RadixSort...等。未来可能会有更多。此外，有时相同的排序算法会根据要排序的数据执行不同的操作。因此，他们希望保持此选项处于打开状态，并将其留给我们选择。这不是 Set/Map 的情况，因为 O(log N) 是最好的排序复杂度。

---

https://github.com/geniot/indexed-tree-map

考虑使用 indexed-tree-map 。它是一个增强的 JDK 的 TreeSet，它提供通过索引访问元素并查找元素的索引，而无需迭代或隐藏的底层列表来备份树。该算法基于每次发生更改时更新更改节点的权重。

---