1.背景

众所周知，arrayList底层是通过数组实现，当其超过容量时，会进行1.5的扩容，将原数组数据迁移至新数组中。

而LinkedList底层为双向链表，其增加操作直接在尾部新增一个node节点即可。

那么，在插入相同的数据情况下（集合默认长度都是0），到底谁更快呢？

2.案例

  public static void main(String[] args) {
    List array = new ArrayList<>();
    List linked = new LinkedList<>();
    long start = System.currentTimeMillis();
    int index = 10000000;
    for (int i = 0; i < index; i++) {
      array.add("" + i);
    }
    long end = System.currentTimeMillis();
    System.out.println("ArrayList用时：" + (end - start) / 1000 + "s");
 
    start = System.currentTimeMillis();
    for (int i = 0; i < index; i++) {
      linked.add("" + i);
    }
    end = System.currentTimeMillis();
    System.out.println("LinkedList用时：" + (end - start) / 1000 + "s");
 
  }

3.结果

4.分析

此处我是这么理解的，arrayList是通过下标直接去放入数据，而linked需要创建一个Node然后 将数据放入，再与前节点建立链接。

然后不需要扩容的情况下，明显arrayList快，那么扩容呢？其实我们测试用的是尾部插入。

也就是arrayList扩容后直接将前面的数据放入对应下标，之后的在继续按照下标插入就行，也就是有序在尾部插入。

如果数据量大通过尾部插入的话（不指定下标，默认就是在尾部插入），linked的插入需要建立对应的对象，绑定关系，

而array则直接放置，其扩容也是按照原来顺序放入新数组，速度比较链表 要更快。

我还专门做了一个按照头部插入的方式，发现这时明显链表高于数组的速度。

5.总结（个人观点）

数组比之链表:

在需要扩容的前提下

插入效率随着下标的递增，其性能逐渐由链表偏向数组。

下标靠中间（链表的查询惨不忍睹），所以其中间效率也是极低的

而数组插入的下标靠前，会涉及其下标之后元素移位操作，所以index越靠前插入，效率越低

6.插入性能