面试：“谈谈ArrayList和LinkdeList之间的区别？”，究竟有多少人回答错了？该怎么回答？

多数人的回答：

        1.ArrayList的底层是顺序表，基于数组，而LinkedList底层是一个双向链表；

        2.LinkedList增加删除比较快，ArrayList查找比较快；

---

这样回答真的正确吗？

        第一点回答的没有问题，问题就出现在了第二点，第二点回答完全错误！！！

        为什么？往下看~

        第一，ArrayList查找并不快，只是具有随机访问的能力，什么是随机访问？就是根据下标获取元素，而查找则是需要遍历的，ArrayList的查找的时间复杂度为O(n)，并没有优势！

        第二，LinkedList增加删除也不快！首删和尾删还可以，时间复杂度为O(1)，中间位置的删除虽然不像顺序表那样需要搬运元素，但时间复杂度依然是O(n)！为什么？删除元素你得先找到元素啊，找到了之后才能删除。而LinkedList指定位置增加元素也是这样，add(n, value)，这是通过下标来描述的，对于链表来说，依然需要遍历，Java的这种封装，导致没有发挥出链表应有的优势！这中间位置的插入和删除元素不是链表不行，只是LinkedList不太行啊~

        再来聊聊C++，C++中STL  std : : list的插入元素是需要显式的指定一个迭代器，迭代器就指向了要插入的位置，这里的中间位置插入元素的时间复杂度才是O(1)；

---

那该如何回答？

        1.ArrayList的底层是顺序表，基于数组，而LinkedList底层是一个双向链表；

        2.对于随机访问，ArrayList要优于LinkedList，ArrayList可以通过下标以O(1)的时间复杂度访问元素，而LinkedList不具备随机访问能力，是需要以O(n)的时间复杂度遍历链表，通过查找，找到元素。说到查找，ArrayList和LinkedList查找所需的时间复杂度是一样的，都为O(n)；

        3.对于插入和删除元素，LinkedList要优于ArrayList，因为LinkedList插入和删除元素不需要像ArrayList那样去搬运元素，计算大小；

        4.LinkedList比ArrayList更占内存，因为LinkedList的结点不光需要ArrayList那样一份空间存储val值，LinkedList还需要另外需要两个空间，一个存储上一个结点的地址，一个存储下面位置的结点；

---