列表插入效率

Question

我必須對大列表（超過10,000個元素）進行排序。在添加元素時，我必須將它插入到正確的位置。我看到ArrayList將會移動插入點之後的所有元素。

在這種情況下，List接口的所有不同實現如何表現？當選擇其中一個實施時，有什麼優點和缺點？

Answer 1

List的兩個主要實現是ArrayList和LinkedList。還有其他人，但他們通常用於特殊情況。

ArrayList可以通過索引非常快地訪問，因爲它是由數組支持的 - 您只需要array[i] - 但修改列表需要移動大部分底層數組，因此效率不高。

您可以非常高效地添加/刪除LinkedList的項目，但找到第012項是比較慢的，因爲它必須從頭開始，走到列表的計數節點，直到它到達所需的位置。

Answer 2

可能重複，但我會給你一個提示。

排序你的數據，你可以使用：

Collections.sort(List list); 

方法，將列表轉換爲數組，所以你不必在意太多類型的List實現的。它只需要在對象中實現的接口Comparable。

Answer 3

您的數據是否包含重複項？

如果沒有，你可以使用一個TreeSet<?>

如果是，你可以使用一個TreeMap<?, Integer>其中整數每件

計數