ArrayList 与 LinkedList的插入效率实践分析，

ArrayList 与 LinkedList的效率实践分析

我们已知的ArrayList以及LinkedList是如下的一个描述:

ArrayList 底层使用连续空间进行顺序存储，随机查询快O(1)，增加和删除慢

LinkedList 底层使用双向队列实现，随机查询较慢,插入速度，删除速度快

但是不经过验证如何说明问题。本文将会对ArrayList和LinkedList的插入、查询、删除进行实验，通过实验得到的数据来说明性能问题

测试机器配置：
CPU： i7 - 6700HQ
内存：16GB

1.ArrayList与LinkedList的极端插入情况

何为极端插入？，我们令一个列表是S[1…n],我们知道ArrayList是顺序存储，每一次插入都需要移动元素，如果我们将数据插入S[1],那么数组将会最大次数的移动元素，会导致内存数据的大批量复制这也是插入的最坏情况。在ArrayList源码中的add(int index,E element)是这样做的

  /**
 * Inserts the specified element at the specified position in this
 * list. Shifts the element currently at that position (if any) and
 * any subsequent elements to the right (adds one to their indices).
 *
 * @param index index at which the specified element is to be inserted
 * @param element element to be inserted
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public void add(int index, E element) {
    rangeCheckForAdd(index);

    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

而LinkedList采用链表，则不存在移动元素的问题，只是会新建节点并修改相关引用。

   public void add(int index, E element) {
    checkPositionIndex(index);

    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
    }

/**
 * Inserts element e before non-null Node succ.
 */
void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}
/**
 * Links e as last element.
 */
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++;
}

我们具体的测试代码如下：

    List<Integer> list = new ArrayList<>();
    Integer n = new Integer(1);
    long start = System.currentTimeMillis();
    for (int i = 0; i < 50000; i++) {
        list.add(0, n);
    }
    long end = System.currentTimeMillis();
    System.out.println("arraylist time:" + (end - start));


    List<Integer> list1 = new LinkedList<>();
    start = System.currentTimeMillis();
    for (int i = 0; i < 50000; i++) {
        list1.add(0, n);
    }
    end = System.currentTimeMillis();
    System.out.println("linkedlist time:" + (end - start));


得出的结果是
arraylist time:128
linkedlist time:4

2.ArryList与LinkedList的随机插入情况

随机插入我们采用生成随机数的做法来模拟.

    List<String> list = new ArrayList<>();
    Random random=new Random();
    long start = System.currentTimeMillis();
    for (int i = 1; i < 50000; i++) {
        int x=random.nextInt(i);
        list.add(x,"a");
    }
    long end = System.currentTimeMillis();
    System.out.println("arrayList insert time "+(end-start));


    List<String> list1 = new LinkedList<>();
    start = System.currentTimeMillis();
    for (int i = 1; i < 50000; i++) {
        int x=random.nextInt(i);
        list1.add(x,"a");
    }
    end = System.currentTimeMillis();
    System.out.println("arrayList insert time "+(end-start));
   结果是：
   arrayList insert time 68
   linkedList insert time 3000

3.ArrayList与LinkedList的尾部插入情况

ArrayList<String> arr = new ArrayList<>();
long start =System.currentTimeMillis();
for (int i = 0; i < 200000; i++) {
    arr.add("a");
}
long end=System.currentTimeMillis();
System.out.println("arrylist time:" + (end - start));


LinkedList<String> link = new LinkedList<>();
start =System.currentTimeMillis();
for (int i = 0; i < 200000; i++) {
    link.add( "a");
}
end=System.currentTimeMillis();
System.out.println("linkedlist time:" + (end - start));

结果是：
arrylist time:9
linkedlist time:5

但这个仅仅是20w条数据的样子，如果我们数据再大一点会怎么样呢？这次我们调节数据到100w，200w条?
100w条时：
arrylist time:15
linkedlist time:11
200w条时：
arrylist time:28
linkedlist time:76
剧情开始反转了，具体测算后大约是150w左右运算时间相差无几，但是超过这个限度就会发生极大变化（可能不同机器不一样），
之后arraylist的性能反而会比linkedlist好。但是实际上我们用到那么大的数据量实在是太少了。
为何之后linkedlist会比arraylist插入速度慢的原因我认为可能是由于linkedlist进行内存分配的原因，arraylist的内存管理采用内存扩容的方案，初始是10,扩容时每次增加老容量的一半，然后直接插入数据

/**
     * Increases the capacity to ensure that it can hold at least the
     * number of elements specified by the minimum capacity argument.
     *
     * @param minCapacity the desired minimum capacity
     */
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

而linkedlist是每一次都需要去new新对象，修改与链表之间的相互引用。一次性分配内存总是会比多次分配内存花费的时间少。但是还是不足以解释这个问题，如果对这个问题有答案的朋友可以说下。

关于ArrayList与LinkedList的删除和查询便不再叙述了，LibkedList是基于列表实现的，删除过程中只需修改引用，而ArrayList还是需要进行内存复制。关于查询，ArrayList是基于顺序存储的，可以通过索引访问，访问速度O(1)，但是LibkedList首先需要从头节点进行顺序查，时间复杂度是O(n)级别的。