文章前言：不要盲目相信网上的博客教程，我更建议自己动手看代码分析。

ArrayList 是基于数组的数据结构， 源码中是一个Object类型的elementData成员变量维护着一个数组。每次插入或者删除元素时会涉及到数组元素的移动，当前维护的数组长度不够时会进行扩容，扩容的时候是新建一个更大长度的数组，然后将现有的元素用System.arrayCopy拷贝过去。如果是在尾部添加那么时间复杂度就是O(1) ，不会涉及元素移动 如果在中间插入时间复杂度就是O(N)，取决于当前位置距离数组末端有多远。越远越消耗性能。

LinkedList 是基于双向链表的数据结构，源码中是用Node节点来维护存储对象，每一个节点分别存储着上一个、下一个元素的引用和当前对象（的引用），并且LinkedList自己保存了第一个和最后一个节点的引用。当插入元素时，源代码中会根据当前要插入的索引位置进行二分判断，如果当前索引位置小于 当前容量/2 就从first节点开始遍历，如果索引位置大于 当前容量/2 就从last节点反向遍历

那么两者有什么区别呢，分别适用于什么场景呢？曾经当我还是一个小菜鸟为面试做准备的时候，我也去网上看了很多人的博客，他们都说ArrayList适合查询，LinkedList适用增删。那么，事实真的是这样吗？LinkedList增删操作真的比ArrayList快吗？

ArrayList<Integer> arrayList = new ArrayList<>();
LinkedList<Integer> linkedList = new LinkedList<>();
long start1 = System.currentTimeMillis();
for(int i=0;i<1000000;i++){
    arrayList.add(i);
}
long end1 = System.currentTimeMillis();
System.out.println("ArrayList尾部添加时间："+(end1 - start1));

long start2 = System.currentTimeMillis();
for(int i=0;i<1000000;i++){
    linkedList.add(i);
}
long end2 = System.currentTimeMillis();
System.out.println("LinkedList尾部添加时间："+(end2 - start2))

反复测试以上代码，发现在当循环次数小于10000时，LinkedList添加速度稍微比ArrayList快1到2ms，当循环次数大于10000时ArrayList的速度要比LinkedList快。当次数到达一百万时，两者有明显差距。并且越大差距越明显。分别看两个类的add方法源码：

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

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

相对来说，LinkedList的add方法比较简单，调用的linkLast就这么点代码，而ArrayList会判断当前容量，是否需要扩容，扩容的时候，会新建一个更大的数组，将当前元素Copy到新数组中。两者的时间复杂度都是O(1)，这个时间差距我并不知道是什么原因……可能是由于垃圾回收导致的。至少可以确定，在不同的数据量时，两者的性能各有千秋。

再次测试中间插入元素，如下代码：

        long start3 = System.currentTimeMillis();
        for(int i=0;i<50000;i++){
            arrayList.add(99999,1000);
        }
        long end3 = System.currentTimeMillis();
        System.out.println("ArrayList中间插入时间："+(end3 - start3));

        long start4 = System.currentTimeMillis();
        for(int i=0;i<50000;i++){
            linkedList.add(99999,1000);
        }
        long end4 = System.currentTimeMillis();
        System.out.println("LinkedList中间插入时间："+(end4 - start4));

当两个List容量为一百万时的结果：

ArrayList中间插入时间：7593
LinkedList中间插入时间：16440

可以看到明显不是一个数量级的时间。我们去分别查看这个重载的add(index,element)方法，ArrayList的实现是（此处请自己去看源码），将add方法的第一个参数，也就是插入的索引位置后面的数据使用System.arrayCopy方法全部往右移动了一位，然后索引位置赋值当前插入的对象。那么就显而易见了。当我们插入的索引位置越靠近数组尾部，需要移动的数组元素越少，性能就越高。反之越低，当我们把上面代码的插入索引位置99999改成2之后再看结果

ArrayList中间插入时间：8135
LinkedList中间插入时间：9

看到了吗？LinkedList只需要9ms！！！我们再去研究一下LinkedList重载的add(index,element)方法（此处请自己去看源码，算了我贴在下面了！）。乍一看这兄弟源码很简单，只要拿到当前索引的节点，把它的前后引用改掉就OK。但是仔细一看会发现，我如何拿到

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

当前索引的节点呢？关键代码来了：

   Node<E> node(int index) {
        // assert isElementIndex(index);

        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

先把当前索引和总容量的一半比较，如果index < size/2 从链表头遍历查找，如果 index > size/2 从链表尾反过来遍历查找。那么问题又显而易见了，当插入的索引位置越接近 size/2 需要遍历的Node节点越多，性能就越差。

总结：ArrayList是基于数组的数据结构，LinkedList是基于双向链表的数据结构。数组和双向链表都是线性表，数组是内存连续的空间，而链表不是。数组支持随机访问，而链表不支持，当链表访问时必须从头或者尾部根据当前存储的其他节点引用来一个一个查找。当进行中间插入时，索引位置越接近 size / 2  的位置，LinkedList效率越慢。当索引位置越接近起始位置，ArrayList效率越慢。你还敢说ArrayList查询快，LinkedList增删快吗？