【数据结构】谈谈ArrayList和LinkedList的区别

 （此图源于比特高博）

上图简洁明了的列出了二者的不同点

下面咱们详细聊聊具体的

要问的是区别，问不同点，那就得从二者共有的但是不同的点来讨论

1.底层实现上：ArrayList底层是顺序表，采用数组结构；LinkedList底层是双向链表，采用链表节点的结构

2.存储空间上：ArrayList储存是在物理上连续，同时逻辑上也连续的一种数据结构；而LinkedList则是在物理上不一定连续，但在逻辑上连续的一种数据结构（这也导致了二者不同的应用场景）

3.从功能上来看

经常会有一种错误的说法：LinkedList增加删除比较快，ArrayList查找比较快

上述是一种错误的或者说是不严谨的说法

1）ArrayList的查找其实并不快，它不过是具备了随机访问的能力，因此它在随机访问上的时间复杂度为O(1)，随机访问=》根据下标来获取元素，这种叫随机访问，真正快的查找应该是能根据值来获取元素的下标：indexOf这种才叫做查找！！！

你要是想在数组中查找某个元素，你不还是得遍历数组才能找到下标？这种查找的时间复杂度不就是O(