ArrayList和LinkedList的区别(面试必问的ArrayList和LinkedList知识)

问到ArrayList和LinkedList的区别，这个是我曾经面试真实被问到的一个问题，其实也完全可以换一个问法：数组和链表有什么区别。

数据结构

ArrayList 的内部数据结构就是数组（一块连续的存储空间）。

LinkedList 的结构是一个双向链表（不连续的存储空间）。

通过 Java 源码可以看得出来 LinkedList 的数据结构是一个双向链表，每个节点是一个 Node，节点中有 3 个属性：

1. item : 实际存放的内容；

2. prev : 指向前一节点的指针；

3. next : 指向后一节点的指针。

1. head 和 tail 分别作为头、尾节点，不包含数据。

及格答案

ArrayList：是连续的内存空间，所以查找快，方便寻址；但删除、插入慢，因为需要发生数据迁移；

LinkedList：需要通过指针一个个寻找，查找慢；但删除、插入快，因为只要改变前后节点的指针指向即可。

在这里在大部分情况下其实是没有什么问题的，但毕竟世上没有什么绝对的事！

特殊情况查找

如果说的是，帮我查找出第 n 个元素，那就是 ArrayList 更占优势，因为它是连续的内存空间，可计算的，可以算内存偏移多少就可以定位到第 n 个。

LinkedList 不连续，无法计算偏移量，只能一个个往下找。

但如果说我要查找具体的比如 "A" 在哪，那这时候就不是按位置查找了，是按内容查找，这时候就只有遍历了，ArrayList 就发挥不了它的内存优势，没法计算，只能遍历，一个一个比较，这时候 ArrayList 和 LinkedList 就都是半斤八两了。

插入

当从中间插入，ArrayList 的优势就变成劣势，中间插入的数据会导致后面大量的数据往后挪，而 LinkedList 就只需要改变指针指向就好了。

当往末尾插入，ArrayList 可计算的优势就出来了，往里扔就行了。

但 LinkedList 也不傻，也不会真的从第一个开始找，一直找到最后一个再加上去，它有两个指针，一个指向头部，一个指向尾部，所以每次要加新的元素可以把 tail 指向改一下，重新指向最新的节点，这时候两个其实也差不多。

附加分

其实在 JDK 1.6 中，LinkedList 是一个双向循环链表的数据结构。

如果你还能说出这里的不同，那简直。。。。