在可修改列表的應用程序中使用什麼數據結構？

Question

在一些應用程序中，您可以在其中移動項目，刪除項目，添加或插入項目等項目列表。

通常我會說一個ArrayList可以工作，但顯然很多操作都是線性時間。

有沒有更好的數據結構，大多數人用這個？

Answer 1

如果您的優先級是從維護任意順序的集合中插入和/或移除元素，那麼與Java捆綁在一起的類將滿足該需求。您可以快速插入或刪除任何特定索引編號的元素。

鏈中的每個環節是一個雙向鏈表知道它的前身和它的後繼者。每個元素都包含一個引用/指向前面元素的指針和另一個引用/指向下一個元素的指針。因此，插入意味着告訴鏈接對將新元素視爲其後繼者或前任者。鏈條的其餘部分保持不變。

LinkedList的缺點是，索引號的訪問很昂貴，因爲查找第n個元素意味着遍歷鏈中從一個元素到下一個元素的n個鏈接。鏈接列表固有地意味着順序訪問。因此，獲取元素的代價很高，但一旦出現插入/刪除的機制便宜。

LinkedList的另一個缺點是搜索，因爲類似的原因（順序訪問）。由於排序是任意的並且沒有排序，所以沒有辦法近似預測/預期元素可能被發現的位置。因此，搜索意味着從一個元素到下一個元素遍歷鏈，並對每個元素進行比較。

另一方面，如果索引訪問是您的優先級，那麼ArrayList是要走的路。直接訪問第n個元素是ArrayList的專業。插入和移除元素是非常昂貴的操作，除非處理最後一個元素，否則需要重建支持陣列。對於大型數組，這會影響內存管理，因爲數組必須位於連續內存中。

LinkedList和ArrayList都允許重複。

LinkedList和ArrayList都不是線程安全的。因此，如果要從多個線程訪問，則需要解決其他一類問題。

要了解細微差別，一般研究linked lists和arrays。