哪個數據結構？鏈表或Java中的任何其他？

我對Java程序中使用的數據結構有特殊的要求。它（數據結構）應該能夠保存大量的數據（不是固定的），我的主要操作是在最後添加，並從頭開始刪除/讀取（LinkedLists看起來不錯）。但偶爾，我需要從中間刪除，這是LinkedLists非常痛苦的地方。任何人都可以建議我解決這個問題嗎？或者我可以通過哪些優化來減少LinkedList中的刪除操作？哪個數據結構？鏈表或Java中的任何其他？

感謝您的幫助！

來源

2010-02-28 Superman16885

你可以嘗試使用帶有指針的鏈表之後的第10000個元素，這樣你就可以減少找到你想要刪除的中間的時間。這裏有一些鏈接列表的一些不同變化： http://experimentgarden.blogspot.com/2009/08/performance-analysis-of-thirty-eight.html

來源

2010-02-28 06:36:52

思考一個跳過列表？ http://en.wikipedia.org/wiki/Skip_list 原因添加和刪除是O（日誌n） – 2010-02-28 09:26:52

是啊我研究了pugh等人的skiplists，他們似乎是一個可行的解決方案 – 2010-02-28 19:19:11

LinkedList落在隨機訪問。沒有隨機訪問查找的刪除是不變的，對於長列表來說真的不算太壞。

ArrayList一般很快。從中間插入和移除的速度比您預期的要快，因爲阻止內存移動的速度驚人地快。在開始附近移除和插入以使所有以下數據向下或向上移動。

ArrayDeque就像ArrayList只有它使用循環緩衝區和有一個奇怪的接口。

通常的建議：嘗試一下。

來源

2010-02-28 06:37:16

@Spedge好點。 – 2010-02-28 07:07:16

LinkedHashMap中可能適合你的目的你會用一個迭代器從正面拉的東西，並通過查找關鍵的條目時，你需要訪問列表

來源

2010-02-28 07:12:14 objects

LinkedHashMap中間大概是辦法走。偉大的迭代，deque操作，並尋找到中間。但是，在內存中需要額外的成本，因爲您需要在基本集合上管理一組密鑰。另外，我認爲它會在你刪除的空間中留下'空白'，導致非連續的一組鍵（儘管不應該影響迭代）。

編輯：啊哈！我知道你需要什麼：A LinkedMultiSet！一個LinkedHashMap的所有好處，但沒有多餘的密鑰集。不過，這只是一個更復雜的使用。

來源

2010-02-28 09:17:32

首先您需要考慮您是否會從列表中心刪除經常與列表的長度相比較。如果您的清單有N項目，但刪除次數比1/N少得多，請不要擔心。根據您的喜好使用LinkedList或ArrayDeque。（如果你的列表偶爾很大，然後縮小，但大多很小，LinkedList更好，因爲它很容易恢復內存;否則，ArrayDeque不需要額外的對象，所以它更快一點，也更緊湊 - 除了底層陣列永遠不會收縮）

如果，另一方面，你刪除相當多的往往比1/N，那麼你應該考慮一個LinkedHashSet，它保持在一個哈希集合的頂部鏈表隊列 - 但它是一套，所以請記住，您不能存儲重複的元素。這會將開銷LinkedList和ArrayDeque放在一起，但如果您經常執行中央刪除操作，則可能會值得。然而，如果你真的需要最後一盎司的速度並且願意花費編碼時間來獲得它，那麼最優結構將會是一個「可調整大小」的數組（即在它太小時重新分配），這個數組與一個循環緩衝區，您可以通過將元素設置爲null來清空中間的元素。（如果你有一個不正當的用例，那麼你也可以重新分配緩衝區。）我不建議編碼，除非你真的喜歡編碼高性能數據結構，或者有充分的證據表明這是一個代碼中的關鍵瓶頸，因此您真的需要它。

來源

2010-03-01 06:55:51

哪個數據結構？鏈表或Java中的任何其他？

回答

相關問題