先看网上结论：

1.ArrayList的底层是数组，根据下标可以直接定位到元素的位置，这样查找的时间复杂度就是O(1)，插入由于要移动其他元素的下标，所以增加删除的复杂度是O（n）。

2.LinkList的底层是链表，查询时需要从第一个元素一个一个的查到目标索引，所以时间复杂度是O（n），而插入时只需要改变上一个元素的指向位置，所以时间复杂度是O（1）。

我们来验证下，这个结论是否属实呢。

第一：我们先来测试一千万条数据的顺序插入

这个结论有点意外啊：ArrayList的性能比linkList差了四倍。这里的慢速是因为移动其他元素的下表导致的吗？其实不是，例子中的插入，是尾部插入，并不是随机插入，也就是说先前的元素下表并不需要移动，这里插入的耗时就是O（1）。

真是原因导致顺序插入比较慢的原因是：ArrayList的扩容机制，ArrayList的底层是数组，是数组就有大小，初始大小是10，负载因子是0.75，也就是一旦ArrayList的元素个数到达数据长度就需要扩容。扩容的过程是，新建一个1.5倍的新空数组，然后将旧数组复制过去，期间，原始的hash值不重新计算，旧数组删除。

结论：顺序插入多条数据时，ArrayList的效率比LinkList慢很多，原因是ArrayList有扩容机制，LinkList无扩容

第二：我们测试随机访问

结果爆炸，LinkList的查询效率远远低于ArrayList，简直天差地别啊，随机访问测试，ArrayList完胜，应了网上的结论，而且不是差一点，而是差N倍

第三：我们测试随机插入

哎哎哎，这不科学啊，为啥LinkList的耗时比ArrayList还高五倍呢？不是说好的LinkList的随机插入与删除效率要好于ArrayList吗？

其实，LinkList的插入删除效率O（1）的前提是，知道上一个元素节点的指针，关键是怎么知道上一个元素节点的指针呢？还是要从头循环知道找到上一个节点，才能得知指针，这个寻找过程还是O（n）.这样大家的时间复杂度都是O（n），为什么LinkList还是要慢呢？这里我认识，是ArrList的下表移动效率要高于指针的移动效率，而且LinkList采取的指针移动方式必然导致内存碎片化，从而加剧内存移动的耗时。

结论：只有在顺序大规模数据写入的时候，LinkList效率高于ArrList，其他操作的执行效率均低于ArrList,尤其是随机读写。考虑日常编程中的List使用习惯，除非有超大规模数据的顺序写入要求，都推荐使用ArrList，时间复杂度也不是简单的O(1),O(N)可以解释的。