你什麼時候知道何時使用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？

回答

相關問題