LinkedList-和有什么区别ArrayList？什么时候最好使用 a LinkedList？
我认为每个 Java 开发人员在面试时都至少听说过一次这个问题。
- 如果您希望能够在列表中间插入项目，则链接列表更可取。
这是这个问题的常见答案。每个人都知道。每次您询问有关 List 实现之间差异的问题时，您都会得到以下答案：
什么时候应该使用 LinkedList？您何时需要在元素之间或开始时有效地移除？
忘了提及插入费用。在 LinkedList 中，一旦你有正确的位置，插入成本
O(1)，而在 ArrayList 中它上升到O(n)- 必须移动超过插入点的所有元素。
当您希望能够在列表中间插入项目（例如优先级队列）时，链接列表优于数组。
ArrayList 速度较慢，因为它需要复制数组的一部分才能删除已空闲的插槽。LinkedList 只需要操作几个引用。
和更多...
但是你有没有尝试过自己复制它？我昨天试过，得到了这些结果：
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
public class Test {
public static void main(String... args) {
final int MAX_VAL = 10000;
List<Integer> linkedList = new LinkedList<Integer>();
List<Integer> arrayList = new ArrayList<Integer>();
for(int i = 0; i < MAX_VAL; i++) {
linkedList.add(i);
arrayList.add(i);
}
long time = System.nanoTime();
for(int i = 0; i < MAX_VAL; i++) {
linkedList.add(MAX_VAL/2, i);
}
System.out.println("LL time: " + (System.nanoTime() - time));
time = System.nanoTime();
for(int i = 0; i < MAX_VAL; i++) {
arrayList.add(MAX_VAL/2, i);
}
System.out.println("AL time: " + (System.nanoTime() - time));
}
}
输出：
LL时间：114098106
阿尔时间：24121889
那是什么？为什么 LinkedList 这么烂？也许我们应该尝试删除操作而不是添加？好的，让我们试试：
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
public class Test {
public static void main(String... args) {
final int MAX_VAL = 10000;
List<Integer> linkedList = new LinkedList<Integer>();
List<Integer> arrayList = new ArrayList<Integer>();
for(int i = 0; i < MAX_VAL; i++) {
linkedList.add(i);
arrayList.add(i);
}
long time = System.nanoTime();
for(int i = 0; i < MAX_VAL/2; i++) {
linkedList.remove(MAX_VAL/2);
}
System.out.println("LL time: " + (System.nanoTime() - time));
time = System.nanoTime();
for(int i = 0; i < MAX_VAL/2; i++) {
arrayList.remove(MAX_VAL/2);
}
System.out.println("AL time: " + (System.nanoTime() - time));
}
}
输出：
LL时间：27581163
阿尔时间：3103051
哦，ArrayList 还是比 LinkedList 快。是什么原因？这个神话破灭了吗？或者也许我错了？
