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

Question

我认为在添加元素时链表应该比数组列表更快？我刚刚测试了添加、排序和搜索元素需要多长时间(arraylist vs linkedlist vs hashset)。我只是将 java.util 类用于 arraylist 和 linkedlist...使用每个类可用的两种 add(object) 方法。

arraylist 在填充列表...和列表的线性搜索方面优于链表。

这样对吗？是不是我在实现过程中做错了什么？

********* ******编辑*****************

我只是想确保我正确使用这些东西。这就是我正在做的:

public class LinkedListTest {

    private List<String> Names;

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

然后我只使用链表方法，即“Names.add(strings)”。当我测试 arraylists 时，它几乎是一样的:

public class ArrayListTest {

    private List<String> Names;

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

我做的对吗？

Answer 1

是的，没错。 LinkedList 必须在每次插入时进行内存分配，而 ArrayList 允许进行较少的操作，即 amortized O(1) insertion .内存分配看起来很便宜，但实际上可能非常昂贵。

由于引用的局部性，LinkedList 中的线性搜索时间可能较慢:ArrayList 元素靠得更近，因此 cache misses 较少。 .

当您计划仅在 List 的末尾插入时，ArrayList 是选择的实现。