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

考虑使用索引树映射。它是一个增强的JDK的TreeSet，它提供了通过索引访问元素的功能，并且无需迭代或隐藏的底层列表来备份树，就可以找到元素的索引。该算法基于每次有变化时更新已更改节点的权重。

我认为以上都不能回答这个问题，原因如下:

Since same functionality can be achieved by using other collections such as TreeSet, Collections, PriorityQueue..etc (but this is an alternative which will also impose their constraints i.e. Set will remove duplicate elements. Simply saying even if it does not impose any constraint, it does not answer the question why SortedList was not created by java community) Since List elements do not implements compare/equals methods (This holds true for Set & Map also where in general items do not implement Comparable interface but when we need these items to be in sorted order & want to use TreeSet/TreeMap,items should implement Comparable interface) Since List uses indexing & due to sorting it won't work (This can be easily handled introducing intermediate interface/abstract class)

但没有人告诉它背后的确切原因，因为我相信这类问题最好由java社区自己来回答，因为它只有一个具体的答案，但让我尽我所能回答如下:

我们知道排序是一个昂贵的操作，列表和Set/Map之间有一个基本的区别，列表可以有重复，而Set/Map不能。 这就是我们为Set/Map提供TreeSet/TreeMap形式的默认实现的核心原因。在内部，这是一个红黑树，每个操作(插入/删除/搜索)的复杂度为O(log N)，其中由于重复列表无法适合这种数据存储结构。

Now the question arises we could also choose a default sorting method for List also like MergeSort which is used by Collections.sort(list) method with the complexity of O(N log N). Community did not do this deliberately since we do have multiple choices for sorting algorithms for non distinct elements like QuickSort, ShellSort, RadixSort...etc. In future there can be more. Also sometimes same sorting algorithm performs differently depending on the data to be sorted. Therefore they wanted to keep this option open and left this on us to choose. This was not the case with Set/Map since O(log N) is the best sorting complexity.

因为List的概念与自动排序集合的概念是不兼容的。List的意义在于调用List之后。添加(7,elem)，调用list.get(7)将返回elem。在自动排序的列表中，元素可以位于任意位置。

列表迭代器首先保证以列表的内部顺序获取列表的元素。插入顺序)。更具体地说，它是在您插入元素的顺序或您如何操作列表。排序可以看作是对数据结构的操作，有几种方法可以对列表进行排序。

我将按照我个人认为的有用性来排序:

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)，这是一个允许重复元素的集合，而不是它们的第三方实现。Guava库中最值得注意的是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，它对于locale敏感的字符串排序非常有用。这里有一个例子:

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

Collections.sort(strings, usCollator);

并发环境中的排序

但是请注意，在并发环境中使用sort方法并不友好，因为集合实例将被操作，您应该考虑使用不可变的集合。这是Guava在ordered类中提供的东西，是一个简单的一行程序:

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在评论中指出的那样)，您需要轮询()队列直到空为止。

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

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<E>接口的契约，因为add方法应该确保元素驻留在用户指定的索引中。 为什么要重新发明轮子?你应该使用树集或多集，而不是在上面的第一点指出。

但是，如果你想把它作为练习，这里有一个代码示例来开始，它使用了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。

我们有Collections.sort(arr)方法，它可以帮助对ArrayList arr进行排序。要以desc方式排序，我们可以使用集合。排序(arr Collections.reverseOrder ())

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

考虑使用索引树映射。它是一个增强的JDK的TreeSet，它提供了通过索引访问元素的功能，并且无需迭代或隐藏的底层列表来备份树，就可以找到元素的索引。该算法基于每次有变化时更新已更改节点的权重。