你什么时候知道何时使用TreeSet或LinkedList？

每个结构的优点是什么？你什么时候知道何时使用TreeSet或LinkedList？

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

以在未排序阵列和将它们添加到一个已排序structure1。
遍历通过整理数据，删除右边一个
添加数据（从未删除），如果你想保持它的分类，它的附加-居多，TreeSet中有返回该结构数组

2010-09-23 Enf

我不想开始一个额外的答案，因为已经有一些答案，但我想补充一点：你谈论添加/删除数据。更新怎么样？请注意，如果您更改元素对象的“排序键”，TreeSet将永远不会更新其排序顺序。如果你想这样做，请使用我的类[UpdateableTreeSet]（http://stackoverflow.com/a/11169301/1082681）或类似的东西。如果您的对象状态发生变化，这可能是一个决定性因素。 – kriegaex 2012-08-30 23:21:12

比较器是你最好的选择。 JVM必须从头开始遍历LinkedList以决定项目的放置位置。对于任何操作，LinkedList = O（n），对于基本的东西，TreeSet = O（log（n））。

来源

2010-09-23 00:22:14 JustinShoffstall

最佳选择是使用1和2的TreeSet，3使用LinkedList？ – Enf 2010-09-23 00:37:58

@Enf是你的三个用例，每个用于不同的值集合？ – slim 2012-08-30 15:47:29

您何时知道何时使用TreeSet或LinkedList？每种结构有哪些优点？

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

详细信息全部在相应的类和接口javadoc中阐述，但有用的摘要可在Java Collections Cheatsheet中找到。

实际上，集合类型的选择与算法设计密切相关。这两者需要并行进行。（决定你的算法需要一个具有属性X，Y和Z的集合，然后发现不存在这样的集合类型是不好的。）

在你的用例中，它看起来像TreeSet会更好。没有有效的方法（即比O(N^2)更好）对大的LinkedList进行排序，而不需要将其转变为其他数据结构来进行排序。没有有效的方法（即比O(N)更好）将元素插入到先前排序的LinkedList中的正确位置。第三部分（复制到数组）与LinkedList或TreeSet同样适用;在两种情况下都是O(N)操作。

[我假设集合足够大，大O的复杂精确地预测实际性能...]

来源

2010-09-23 00:40:54

伟大的cheatsheet。 – 2010-09-23 05:35:28

TreeSet中：

TreeSet采用红黑树的底层。所以这套可以被认为是一个dynamic search tree。当你需要一个经常读写的结构并且应该保持顺序时，TreeSet是一个不错的选择。

来源

2010-09-23 01:35:57

的真正实力，有优势TreeSet中的在于它的界面实现 - NavigableSet

为何如此强大，并在这种情况下？

通航设置界面中添加例如这3种不错的方法：

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

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

例子：我们需要找到所有与米拉开始的名称和弗拉基米尔结束：

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中没过所有的元素，它找到第一个和最后一个elemenets并返回一个新的Collection，其中包含该范围内的所有元素。

来源

2012-08-30 15:26:45 shevchyk

这是非常有趣的（诚实），但它不回答OP的任何问题。 – slim 2012-08-30 15:46:46

苗条，稍后我会加入其他的:) – shevchyk 2012-08-30 16:20:02

你什么时候知道何时使用TreeSet或LinkedList？

回答

相关问题