为什么在列表的结尾处插入速度比数组列表慢 [英] Why insertion at the End of the Linked list is slow as compare to Array list

问题描述

即使链接列表在内部使用Doubly Linked List，因此它可以轻松地识别最后一个元素并开始添加。现在仍然比数组列表为慢吗？

Even though Linked list internally use the Doubly Linked List , So it can easily identify the last element and start adding. Now still it's slow compare to array list why ?

请参考下面的代码输出：

Please refer the below code with output :

package com.collection;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
public class Performance {

    public static void main(String[] args) {
        List<Integer> arrayList = new ArrayList<Integer>();
        List<Integer> LinkedList = new LinkedList<Integer>();
        checkPerformance("arrayList", arrayList);
        checkPerformance("LinkedList", LinkedList);
    }

    private static void checkPerformance(String type, List<Integer> list) {
        for (int i = 0; i < 1E6; i++) {
        list.add(i);
        }
        long start = System.currentTimeMillis();
        for (int i = 0; i < 1E6; i++) {
            list.add(i);
        }
        long end = System.currentTimeMillis();
        System.out.println("Time Taken" + " " + (end - start)
        + " ms for the type " + type);
    }
}

输出：
所需时间250 ms类型arrayList
类型LinkedList的时间390毫秒

Output : Time Taken 250 ms for the type arrayList Time Taken 390 ms for the type LinkedList

推荐答案

所以，我认为你假设 ArrayList 将会更慢，因为它必须分配一个新的数组，并且每当你添加一个元素到新的数组复制到新的数组，但不是这样。

So, I think that you assume that ArrayList will be slower because it has to allocate a new array and copy the old array into the new one every time you add an element to it, but it's not the case.

当向 ArrayList 添加一个元素时，该元素被添加到一个经典数组中，但在之前，它会调用以下方法，以确保衬垫阵列足够大以添加您的元素：

When you add an element to an ArrayList, this element is added to a classical array, but before, it calls the following method to ensure that the backing array is of a sufficient size to add your element:

/**
 * Increases the capacity of this <tt>ArrayList</tt> instance, if
 * necessary, to ensure that it can hold at least the number of elements
 * specified by the minimum capacity argument.
 *
 * @param   minCapacity   the desired minimum capacity
 */
public void ensureCapacity(int minCapacity) {
    modCount++;
    int oldCapacity = elementData.length;
    if (minCapacity > oldCapacity) {
        Object oldData[] = elementData;
        int newCapacity = (oldCapacity * 3)/2 + 1;
        if (newCapacity < minCapacity)
        newCapacity = minCapacity;
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
}

这意味着如果数组不足以添加您的元素，它不会增加大小到 oldCapacity + 1 你可以期望，但到（oldCapacity * 3 ）/ 2 + 1 ，以允许您向其中添加更多元素，而无需再次分配和复制。

What this means is that if the size of the backing array isn't sufficient to add you element, it will not increase the size to oldCapacity + 1 as you can expect, but to (oldCapacity * 3)/2 + 1, to allow you to add more elements to it without having to allocate and copy it again.

你的第一个循环，数组的容量将是 1005308 （你可以通过在循环后设置一个断点并检查列表变量来检查它）。
因此，添加1000000个元素，您将重新分配它只有两次：一个从 1005308 到 1507963 ，一个从 > 1507963 到 2261945 。

At the end of your first loop, the capacity of your array will be 1005308 (you can check it by setting a breakpoint after the loop and inspecting the list variable). So to, add 1000000 more elements, you will re-allocate it only two times: one to go from 1005308 to 1507963 and one to go from 1507963 to 2261945. The rest of the time, you will just set an element in the backing array to another value (it's really cheap).

使用 LinkedList

With the LinkedList, on the other hand, you will have to allocate a new element every time you add something to the list, and you will have more operations (set the value, and change two pointers values), that's why it can take more time than with ArrayList (I tried, and LinkedList was faster for me).

这篇关于为什么在列表的结尾处插入速度比数组列表慢的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！