一般我们在面试中经常会被问到这个问题：“请说一下ArrayList和LinkedList的区别是什么？”大部分人都能说出ArrayList是基于数组结构的，LinkedList是基于链表结构的，而且大部分人还会想当然的说LinkedList的插入效率比ArrayList的要高，因为LinkedList是基于链表的，插入元素时只要改变一下指针指向的位置就可以了。

从理论上来说，这样确实没问题，但是我们学习一种知识，不能仅仅局限于理论知识上，还应该实际动手操作一下，结合实践结果再得出结论才是一个严谨的治学风格。古话说的好：“纸上得来终觉浅，绝知此事要躬行。”所以只要你实际操作一遍，就会发现一个和上面正好相反的结论：在把元素插入到集合尾部的时候，ArrayList的效率比LinkedList的效率更高。

为什么会出现这种情况，难道童话里都是骗人的？当然不是，其实只要我们看一下源码就会发现：LinkedList在插入元素的时候，确实是会改变指针指向的位置，但是除此之外会new一个Node对象用来存储新元素，然后再把指针指向这个新的Node。我们都知道，在Java中new一个对象是比较耗时的，这也就是为什么插入元素到集合末尾的时候，LinkedList比ArrayList花费的时间更多的原因。

说明一下前提，这里我是基于ArrayList的初始容量足够大，至少要比同时插入的元素个数大，排除动态扩容数组容量的过程，如果有动态扩容的情况，ArrayList效率也会降低。

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++;
}

插入元素到集合头部

前面一直在强调插入元素到集合末尾，原因就在于插入元素的位置会影响插入的效率。现在我们再来测试一下插入元素到集合的头部会有什么不同。

因为是插入到头部，所以对于数组结构的ArrayList来说，一次插入过程需要移动后面所有的元素，效率非常低下。而对于链表结构（实际是双向链表），一次插入过程也只还是new一个Node节点和移动指针指向的位置，因为是添加到头部，所以搜索链表中要添加的位置也很快。因此在这种情况下，就像我们想象的那样，LinkedList的插入效率要高于ArrayList。但是一般情况下，谁又会插入元素到集合头部呢？

插入元素到集合中间

在这种情况下，ArrayList需要移动一半的元素，LinkedList也需要查找一半的元素才能找到中间位置，所以这种情况下哪个效率更高呢，我们通过实验结果来证明。

public static void addFromMidForArray(int DataNum) {
        ArrayList<String> list = new ArrayList<String>(DataNum);
        int i = 0;
        long begin = System.currentTimeMillis();
        while (i < DataNum) {
            int temp = list.size();
            list.add(temp/2, i + "abcd");
            i++;
        }
        long after = System.currentTimeMillis();
        System.out.println("ArrayList插入元素到集合中间花费的时间" + (after - begin));
}

public static void addFromMidForLlinked(int DataNum){
        LinkedList<String> list=new LinkedList<String>();
        int i = 0;
        long begin = System.currentTimeMillis();
        while(i<DataNum) {
            int temp = list.size();
            list.add(temp/2, i + "abcd");
            i++;
        }
        long after=System.currentTimeMillis();
        System.out.println("LinkedList插入元素到集合中间花费的时间" + (after - begin));
}

测试结果为：

ArrayList插入元素到集合中间元素花费的时间14
LinkedList插入元素到集合中间元素花费的时间1020

两者相差的时间非常大，甚至不是一个数量级的。

所以得出结论：插入元素到集合中间时，ArrayList的效率更高。

其实我们看ArrayList的set(index,value)的源码发现，它移动元素使用了System.arraycopy函数，而这个函数的效率是很高的，因为它是一个native方法，可能直接操作了内存。

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++;
    }

public static native void arraycopy(Object src, int  srcPos, Object dest, int destPos, int length);

总结

因为添加和删除都会引起集合元素个数的变化，所以删除的性能和添加的是一样的，于是可以得出下面的结论：

• 从集合头部添加、删除元素：ArrayList>LinkedList

• 从集合中部添加、删除元素：ArrayList<LinkedList

• 从集合尾部添加、删除元素：ArrayList<LinkedList

而对于遍历来说，因为ArrayList支持随机访问，而LinkedList不支持，所以基于一般的for循环的遍历来说肯定是ArrayList的更快的。但是这两个集合还支持通过迭代器迭代循环，而这个迭代器是可以直接拿到我们的元素的，不用循环拿到数据。所以基于迭代器的遍历这两者花费时间差不多，即：

• for循环：ArrayList<LinkedList

• 迭代器迭代循环：ArrayList≈LinkedList

---