java列表插入效率

Question

我必须对一个大列表进行排序（超过10000个元素）。在添加元素时，我必须将其插入正确的位置。我看到一个ArrayList将移动插入点之后的所有元素

在这种情况下，List接口的所有不同实现是如何工作的？在选择一种实现而不是另一种实现时，优点和缺点是什么

Answer 1

可能是重复的，但我会给你一个提示

要对数据进行排序，可以使用：

Collections.sort(List list);

方法，它无论如何都会将列表转换为数组，所以您不必太在意列表实现的类型。它只需要在对象中实现接口

Answer 2

List的两个主要实现是ArrayList和LinkedList。还有一些，但它们通常用于特殊情况

ArrayList可以通过索引非常快速地访问，因为它由一个数组支持——您只需要array[i]——但是修改列表需要移动很多底层数组，所以效率不高

使用LinkedList可以非常有效地添加/删除项目，但查找第n个条目的速度很慢，因为它必须从开头开始，遍历列表计数节点，直到到达所需的位置

Answer 3

您的数据是否包含重复项

如果没有，可以使用TreeSet<?>

如果是，可以使用TreeMap<?, Integer>，其中整数是每项的计数