11

每种结构的优点是什么？

在我的程序中，我将执行这些步骤，我想知道我应该使用上面的哪个数据结构：

  1. 接受一个未排序的数组并将它们添加到一个排序的结构1。
  2. 遍历排序的数据并删除正确的数据
  3. 添加数据（从不删除）并将该结构作为数组返回
4

5 回答 5

13

您何时知道何时使用 TreeSet 或 LinkedList？每种结构的优点是什么？

通常，您根据您需要的结构和性能属性来决定集合类型。例如，TreeSet 是一个 Set，因此不允许重复并且不保留元素的插入顺序。相比之下，LinkedList 是一个列表，因此确实允许重复并保留插入顺序。在性能方面，TreeSet 为您提供O(logN)插入和删除，而在开头或结尾LinkedList提供插入，并在选定位置或删除处插入。O(1)O(N)

详细信息都在相应的类和接口 javadocs 中进行了详细说明，但可以在Java Collections Cheatsheet中找到有用的摘要。

但在实践中，集合类型的选择与算法设计密切相关。两者需要同时进行。（决定您的算法需要具有属性 X、Y 和 Z 的集合，然后发现不存在这样的集合类型是不好的。）

在您的用例中，看起来 TreeSet 会更合适。没有有效的方法（即比 更好O(N^2)）来对一个不涉及将其转换为其他数据结构进行排序的大型 LinkedList 进行排序。没有有效的方法（即比 更好O(N)）将元素插入到先前排序的 LinkedList 中的正确位置。第三部分（复制到数组）同样适用于 LinkedList 或 TreeSet；在这两种情况下都是一个O(N)操作。

[我假设集合足够大，大 O 复杂度可以准确预测实际性能......]

于 2010-09-23T00:40:54.527 回答
2

TreeSet真正的强大和优势在于它实现的接口——NavigableSet

为什么它如此强大，在什么情况下？

Navigable Set 接口添加了例如这 3 个不错的方法：

    headSet(E toElement, boolean inclusive) 
    tailSet(E fromElement, boolean inclusive)
    subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive)

这些方法允许组织有效的搜索算法（非常快）。

示例：我们需要找到所有以 Milla 开头并以 Wladimir 结尾的名字：

    TreeSet<String> authors = new TreeSet<String>();
    authors.add("Andreas Gryphius");
    authors.add("Fjodor Michailowitsch Dostojewski");
    authors.add("Alexander Puschkin");
    authors.add("Ruslana Lyzhichko");
    authors.add("Wladimir Klitschko");
    authors.add("Andrij Schewtschenko");
    authors.add("Wayne Gretzky");
    authors.add("Johann Jakob Christoffel");
    authors.add("Milla Jovovich");
    authors.add("Taras Schewtschenko");
    System.out.println(authors.subSet("Milla", "Wladimir"));

输出：

    [Milla Jovovich, Ruslana Lyzhichko, Taras Schewtschenko, Wayne Gretzky]

TreeSet 不会遍历所有元素，它会查找第一个和最后一个元素并返回一个包含范围内所有元素的新 Collection。

于 2012-08-30T15:26:45.653 回答
1

树集：

TreeSet使用红黑树底层。所以这个集合可以被认为是一个dynamic search tree. 当你需要一个经常读/写操作，又要保持有序的结构时，TreeSet 是一个不错的选择。

于 2010-09-23T01:35:57.110 回答
0

如果你想让它保持排序并且它主要是附加的，那么带有 Comparator 的 TreeSet 是你最好的选择。JVM 必须从一开始就遍历 LinkedList 来决定在哪里放置项目。LinkedList = O(n) 用于任何操作，TreeSet = O(log(n)) 用于基本操作。

于 2010-09-23T00:22:14.180 回答
0

选择数据结构时最重要的一点是其固有的局限性。例如，如果您使用 TreeSet 来存储对象，并且在运行时您的算法会更改这些对象的属性，这些属性会影响相等比较，而对象是集合的一个元素，请为一些奇怪的错误做好准备。

Set 接口的 Java Doc 声明：

注意：如果将可变对象用作集合元素，则必须非常小心。如果对象的值以影响等于比较的方式更改，而对象是集合中的一个元素，则不指定集合的​​行为。此禁令的一个特殊情况是不允许集合包含自身作为元素。

接口集Java文档

于 2019-04-21T18:39:17.370 回答