添加元素时java链表比arraylist慢？

Question

我认为链接列表在添加元素时应该比arraylist更快？我刚刚测试了添加,排序和搜索元素所需的时间(arraylist vs linkedlist vs hashset).我只是使用java.util类进行arraylist和linkedlist ...使用每个类可用的add(object)方法.

arraylist out在填写列表时执行链表...并在列表的线性搜索中执行.

这是正确的吗？我在实施中做错了吗？

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

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

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允许更少的内存分配,使其分摊O(1)插入.内存分配看起来很便宜,但实际上可能非常昂贵.

LinkedList由于引用的局部性,线性搜索时间可能较慢:ArrayList元素更靠近在一起,因此缓存未命中次数较少.

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