java 你什么时候知道什么时候使用 TreeSet 或 LinkedList ？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/3774543/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
When do you know when to use a TreeSet or LinkedList?
提问by Enf
What are the advantages of each structure?
每种结构的优点是什么？
In my program I will be performing these steps and I was wondering which data structure above I should be using:
在我的程序中，我将执行这些步骤，我想知道我应该使用上面的哪种数据结构：
- Taking in an unsorted array and adding them to a sorted structure1.
- Traversing through sorted data and removing the right one
- Adding data (never removing) and returning that structure as an array
- 接收一个未排序的数组并将它们添加到一个已排序的结构中1。
- 遍历已排序的数据并删除正确的数据
- 添加数据（从不删除）并将该结构作为数组返回
回答by Stephen C
When do you know when to use a TreeSet or LinkedList? What are the advantages of each structure?
你什么时候知道什么时候使用 TreeSet 或 LinkedList ？每种结构的优点是什么？
In general, you decide on a collection type based on the structural and performance properties that you need it to have. For instance, a TreeSet is a Set, and therefore does not allow duplicates and does not preserve insertion order of elements. By contrast a LinkedList is a List and therefore does allow duplicates and does preserve insertion order. On the performance side, TreeSet gives you O(logN)insertion and deletion, whereas LinkedListgives O(1)insertion at the beginning or end, and O(N)insertion at a selected position or deletion.
通常，您可以根据所需的结构和性能属性来决定集合类型。例如，TreeSet 是一个集合，因此不允许重复并且不保留元素的插入顺序。相比之下，LinkedList 是一个列表，因此允许重复并保留插入顺序。在性能方面，TreeSet的给你O(logN)插入和删除，而LinkedList给出O(1)的开头或结尾，并插入O(N)插入在选定的位置或删除。
The details are all spelled out in the respective class and interface javadocs, but a useful summary may be found in the Java Collections Cheatsheet.
详细信息都在相应的类和接口 javadoc 中详细说明，但可以在Java Collections Cheatsheet 中找到有用的摘要。
In practice though, the choice of collection type is intimately connected to algorithm design. The two need to be done in parallel. (It is no good deciding that your algorithm requires a collection with properties X, Y and Z, and then discovering that no such collection type exists.)
但实际上，集合类型的选择与算法设计密切相关。两者需要同时进行。（决定你的算法需要一个具有 X、Y 和 Z 属性的集合，然后发现不存在这样的集合类型是不好的。）
In your use-case, it looks like TreeSet would be a better fit. There is no efficient way (i.e. better than O(N^2)) to sort a large LinkedList that doesn't involve turning it into some other data structure to do the sorting. There is no efficient way (i.e. better than O(N)) to insert an element into the correct position in a previously sorted LinkedList. The third part (copying to an array) works equally well with a LinkedList or TreeSet; it is an O(N)operation in both cases.
在您的用例中，看起来 TreeSet 更合适。没有有效的方法（即比 更好O(N^2)）对大型 LinkedList 进行排序，而不涉及将其转换为其他一些数据结构来进行排序。没有有效的方法（即比 更好O(N)）将元素插入到先前排序的 LinkedList 中的正确位置。第三部分（复制到数组）同样适用于 LinkedList 或 TreeSet；它是O(N)两种情况下的操作。
[I'm assuming that the collections are large enough that the big O complexity predicts the actual performance accurately ... ]
[我假设集合足够大，大 O 复杂度可以准确地预测实际性能......]
回答by Sergii Shevchyk
The genuine power and advantage of TreeSetlies in interface it realizes - NavigableSet
TreeSet真正的威力和优势在于它实现的接口——NavigableSet
Why is it so powerfull and in which case?
为什么它如此强大，在哪种情况下？
Navigable Set interface add for example these 3 nice methods:
Navigable Set 接口添加例如这 3 个不错的方法：
headSet(E toElement, boolean inclusive)
tailSet(E fromElement, boolean inclusive)
subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive)
These methods allow to organize effective search algorithm(very fast).
这些方法允许组织有效的搜索算法（非常快）。
Example: we need to find all the names which start with Milla and end with Wladimir:
示例：我们需要找到所有以 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"));
output:
输出：
[Milla Jovovich, Ruslana Lyzhichko, Taras Schewtschenko, Wayne Gretzky]
TreeSet doesn't go over all the elements, it finds first and last elemenets and returns a new Collection with all the elements in the range.
TreeSet 不会遍历所有元素，它会查找第一个和最后一个元素并返回一个包含范围内所有元素的新集合。
回答by CuriousIndeed
The most important point when choosing a data structure are its inherent limitations. For example if you use TreeSet to store objects and during run-time your algorithm changes attributes of these objects which affect equal comparisons while the object is an element of the set, get ready for some strange bugs.
选择数据结构时最重要的一点是其固有的局限性。例如，如果您使用 TreeSet 存储对象，并且在运行时您的算法更改了这些对象的属性，这些属性会影响相等比较，而对象是集合的一个元素，请准备好应对一些奇怪的错误。
The Java Doc for Set interface state that:
Set 接口的 Java Doc 声明：
Note: Great care must be exercised if mutable objects are used as set elements. The behavior of a set is not specified if the value of an object is changed in a manner that affects equals comparisons while the object is an element in the set. A special case of this prohibition is that it is not permissible for a set to contain itself as an element.
注意：如果将可变对象用作集合元素，则必须非常小心。如果对象的值以影响等于比较的方式更改，而对象是集合中的元素，则不会指定集合的行为。此禁止的一个特殊情况是不允许集合将自身包含为元素。
回答by JustinShoffstall
If you want to keep it sorted and it's append-mostly, TreeSet with a Comparator is your best bet. The JVM would have to traverse the LinkedList from the beginning to decide where to place an item. LinkedList = O(n) for any operations, TreeSet = O(log(n)) for basic stuff.
如果你想保持它的排序并且它主要是附加的，带有比较器的 TreeSet 是你最好的选择。JVM 必须从一开始就遍历 LinkedList 来决定放置项目的位置。LinkedList = O(n) 用于任何操作，TreeSet = O(log(n)) 用于基本内容。
回答by u290629
TreeSet:
树集：
TreeSetuses Red-Black tree underlying. So the set could be thought as a dynamic search tree. When you need a structure which is operated read/write frequently and also should keep order, the TreeSet is a good choice.
TreeSet底层使用红黑树。所以这个集合可以被认为是一个dynamic search tree. 当你需要一个频繁读写操作又要保持秩序的结构体时，TreeSet 是一个不错的选择。
