添加元素时，java linkinglist比arraylist慢？

Question

我以为链表在添加元素时应该比数组表快？我只是测试了添加，排序和搜索元素（数组列表，链表，哈希集）需要多长时间。我只是对数组列表和链接列表使用java.util类…使用每个类都可以使用的两个add（object）方法。

arraylist在填充列表中执行链表…并在列表中进行线性搜索。

这是正确的吗？我在执行中做错了吗？

*_ __ _ _ __ _编辑 __ * __ __ *

*

我只想确保我正确使用了这些东西。这是我在做什么：

public class LinkedListTest {

    private List<String> Names;

    public LinkedListTest(){
            Names = new LinkedList<String>();
    }

然后，我只使用链表方法，即“ Names.add（strings）”。当我测试数组列表时，几乎是相同的：

public class ArrayListTest {

    private List<String> Names;

    public ArrayListTest(){
            Names = new ArrayList<String>();
    }

我做对了吗？

Answer 1

是的，这是对的。LinkedList将必须在每次插入时进行一次内存分配，同时ArrayList允许执行更少的分配，从而将其摊销为O（1）插入。内存分配看起来很便宜，但实际上可能非常昂贵。

LinkedList由于参考位置的限制，线性搜索时间可能会变慢：ArrayList元素之间的距离更近，因此缓存未命中的次数更少。

当您计划仅在a的末尾插入时List，ArrayList是执行的选择。