Java 列表排序：有没有办法让列表像 TreeMap 一样自动永久排序？

Question

在 Java 中，您可以使用项目构建一个 ArrayList ，然后调用：

 Collections.sort(list, comparator);

无论如何在列表时传递比较器，创建就像你可以用 TreeMap 做的那样？

目标是能够将一个元素添加到列表中，而不是让它自动附加到列表的末尾，列表将根据 Comparator 保持自身排序，并在索引处插入新元素由 Comparator 确定。所以基本上列表可能必须根据添加的每个新元素重新排序。

有没有办法通过 Comparator 或其他类似方式以这种方式实现？

原文由 Dave L. 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

您可以更改 ArrayList 的行为

List<MyType> list = new ArrayList<MyType>() {
    public boolean add(MyType mt) {
         super.add(mt);
         Collections.sort(list, comparator);
         return true;
    }
};

注意：PriorityQueue 不是 List，如果您不关心它是什么类型的集合，最简单的方法是使用 TreeSet，它就像 TreeMap 但它是一个集合。 PriorityQueue 的唯一优点是允许重复。

注意：对于大型集合，求助不是很有效，使用二进制搜索和插入条目会更快。 （但更复杂）

编辑：很大程度上取决于您需要“列表”做什么。我建议您为 ArrayList、LinkedList、PriorityQueue、TreeSet 或其他排序集合之一编写一个 List 包装器，并实现将实际使用的方法。这样您就可以很好地了解集合的要求，并且可以确保它适合您。

编辑（2）：因为人们对使用 binarySearch 非常感兴趣。 ;)

 List<MyType> list = new ArrayList<MyType>() {
    public boolean add(MyType mt) {
        int index = Collections.binarySearch(this, mt);
        if (index < 0) index = ~index;
        super.add(index, mt);
        return true;
    }
};

原文由 Peter Lawrey 发布，翻译遵循 CC BY-SA 4.0 许可协议