在Java中有SortedSet和SortedMap接口。两者都属于Java Collections框架,并提供了一种访问元素的排序方式。

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

知道它为什么是这样设计的吗?


当前回答

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

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

其他回答

另一点是插入操作的时间复杂度。 对于列表插入,期望复杂度为O(1)。 但是,排序的列表并不能保证这一点。

最重要的一点是,列表对它们的元素没有任何假设。 例如,您可以列出不实现等于或比较的东西。

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

如果任何列表实现都以某种顺序存储元素,而不是基于索引,那么上述列表方法就没有意义了。

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


树数据结构SortedSet和SortedMap接口使用常用的红黑树实现算法分别实现TreeSet和TreeMap。因此,它确保没有重复的项(或Map情况下的键)。

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

因为所有列表都已经按照条目的添加顺序(FIFO顺序)“排序”了,所以可以使用java.util.Collections.sort()使用另一种顺序“使用”它们,包括元素的自然顺序。

编辑:

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

集合没有这个信息。

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

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

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