有 Java 编程相关的问题?

你可以在下面搜索框中键入要查询的问题!

java为什么LinkedList在添加到列表末尾时比ArrayList慢?

我读了THIS

并且理解LinkedList add(E元素)是O(1) ArrayList add(E元素)是O(1)摊销的,但O(n)是最坏的情况,因为数组必须调整大小并复制

但是,当我试图检查它的时候

public class ArrayListVSLinkeedList {

public ArrayListVSLinkeedList() {

    final int COUNTER = 15000000;

    List<Integer> arrayList = new ArrayList<Integer>();

    long tStart_add = System.currentTimeMillis();

    for (int i = 0; i < COUNTER; i++) {
         arrayList.add(i);
    }
    long tEnd_add = System.currentTimeMillis();
    long tDelta_add = tEnd_add - tStart_add;
    System.out.println("Adding to ArrayList: " +tDelta_add);


    List<Integer> linkedList = new LinkedList<Integer>();
    tStart_add = System.currentTimeMillis();
    for (int i = 0; i < COUNTER; i++) {
        linkedList.add(i);
    }
    tEnd_add = System.currentTimeMillis();
    tDelta_add = tEnd_add - tStart_add;
    System.out.println("Adding to LinkedList: " +tDelta_add);
}

public static void main(String[] args) {
    new ArrayListVSLinkeedList();
}
}

我在输出时收到:

添加到阵列列表9122

添加到链接列表:19859

我知道,这不是真正的基准,但是。。。 最后,将元素添加到ArrayList的末尾比添加到LinkedList要快。为什么会发生这种情况


共 (2) 个答案

  1. # 1 楼答案

    好吧,这取决于你在机器上有多少内存,想想你正在创建的ArrayList已经在内存中了,LinkedList必须分配新内存。。试着用另一种方式运行,看看结果

    更好的方法是尝试用不同的方法运行它们,并看到一个公平的结果

  2. # 2 楼答案

    这仅仅是由于实施

    请看一下ArrayList.add的实现:

    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
    

    ArrayList在内部保存一个数组,该数组的元素是对使用该列表管理的对象的引用。方法ensureCapacityInternal只是检查这个内部数组是否仍然足够大,可以添加另一个元素

    如果是,则添加元素并返回方法。这是非常快的(顺便说一句,是O(1))

    如果阵列已满,则将分配一个较大的新阵列,每个引用都将从旧阵列复制到新阵列。之后,将添加元素。这当然是O(n)。但这种情况很少发生,而且由于调整规模的策略(将规模扩大一倍),这种情况将变得越来越少

    另一方面,让我们看看LinkedList.add的实现:

    public boolean add(E e) {
        linkLast(e);
        return true;
    }
    
    void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }
    

    这里您可以看到,对于每个添加的元素,必须创建一个新的节点对象,然后将其添加为最后一个元素。不进行大小调整,因此方法始终为O(1),但创建节点对象比简单地存储引用花费更多的时间