Java::LinkedList 的插入速度真的比 ArrayList 快吗？

Question

这个问题已经有答案了:

Performance differences between ArrayList and LinkedList [duplicate] (11 个回答)

When to use LinkedList over ArrayList in Java? (33 个回答)

已关闭 5 年前。

我观察到 ArrayList 中的插入操作与 LinkedList 相比，花费的时间更少(以毫秒为单位) 。请阐明这一点。

这是我的测试代码:

List<String> strLnkdList = new LinkedList<String>();

long start1 = System.currentTimeMillis();
for(int i=0;i<10000;i++){
    strLnkdList.add("Test"+i);
}
long end1 = System.currentTimeMillis();
System.out.println("LinkedList Time in millis: " + (end1-start1));

List<String> strArrayList = new ArrayList<String>(10);

start1 = System.currentTimeMillis();
for(int i=0;i<10000;i++){
    strArrayList.add("Test"+i);
}

end1 = System.currentTimeMillis();
System.out.println("ArrayList Time in millis: " + (end1-start1));

输出:

LinkedList Time in millis: 22
ArrayList Time in millis: 10

Answer 1

链表只需要改变要删除的节点的两个邻居节点(元素)中的指针位置。

ArrayList 中的所有元素都需要移动以填充删除元素所创建的空间。

有些人想象一个叠叠乐塔，用于让阵列缩短 1 个方 block ，您必须将其拉出，然后将每个方 block 向下移动 1

对于链表来说，就像你有一个字符串持有一个 block ，然后你只需剪切它