ArrayList vs LinkedList隨機訪問和添加刪除

我很熟悉ArrayList和LinkedList的優點和缺點。 ArrayList是隨機訪問的首選，當添加和刪除較少時，反之亦然。如果我需要一個數據結構，我需要同時進行隨機訪問，並且需要添加&經常從列表中刪除項目？ArrayList vs LinkedList隨機訪問和添加刪除

哪一個可以選擇？

來源

2012-10-20 Kumar Manish

http://docs.oracle.com/javase/6/docs/api/java/util/LinkedList.html –

@BheshGurung我不知道如何評論你的評論？ –

如果你想隨機訪問去ArrayList，你可以使用它作爲一個普通的列表和添加/刪除項目。

ArrayList的內存以塊的形式分配，除非您的ArrayList變大，否則可能會耗盡內存。

既然你沒有提到你是否有任何內存約束（只有約束是隨機訪問），我會說ArrayList應該滿足你的所有需求。

來源

2012-10-20 07:41:06

一般來說，'ArrayList'的內存要求比'LinkedList'要少。這是因爲'ArrayList'只有一個包含數組的對象，而'LinkedList'則需要爲每個列表元素添加一個額外的對象來表示鏈接。但是記憶在這裏似乎沒有問題。 – MvG

'內存耗盡，除非和直到你的ArrayList變大「是一個矛盾的術語。 – EJP

這些數據結構是API兼容的，只需對您的代碼進行基準測試/分析即可。

另一個提示：與ArrayList假設您執行N查找和N突變。這總計爲O(N) + O(N * N) <=> O(N^2)的複雜性。使用LinkedList，您將獲得O(N*N) + O(N) <=> O(N^2)（線性查找時間N +恆定時間突變時間N）。所以兩種數據結構都是可比的。

如果你願意深入一點兔子洞，scala.collection.immutable.Vector有amortized constant cost的查找和插入/刪除。它是不可變的，因此是線程安全的！這是通過使用一些複雜的數據結構實現的。

來源

2012-10-20 07:44:08

ArrayList vs LinkedList隨機訪問和添加刪除

回答

相關問題