ArrayList 与 LinkedList 均是常用的数据结构，但是二者也存在部分区别。
底层数据结构
ArrayList 的底层数据结构是数组，LinkedList 的数据结构是双向链表，这也就表示：ArrayList 所占的内存空间是连续的，LinkedList 是不连续的。
具体内存分布如下图所示：
随机访问速度（根据下标进行访问）
当使用下标访问获取元素时，由于 ArrayList 底层是数据，那么知道了第一个元素的地址，就很容易计算出后面若干个元素的地址，使用下标访问的速度极快。
但是由于 LinkedList 底层是双向链表，元素与元素之间的地址并不连续，没有规律，这时就需要从首元素开始，一个一个遍历，从而获取到指定下标的元素。
相比之下，根据下标进行访问时，ArrayList 的访问速度比 LinkedList 的访问速度更快。
若是查找某个元素是否存在，那么这两个数据结构的查询速度是一样的，均为 o（n）。
增删性能
头插
- 向 ArrayList 头部插入元素时，由于需将 ArrayList 中所有的元素向后复制一次，所消耗的时间较多。
- 向 LinkedList 头部插入元素时，只需新增一个节点，改变原来头结点与新节点的指针指向，所以头插性能较高。
尾插
向 ArrayList 最后一位插入元素时，只需要新增一个元素，不涉及到元素的复制，因此性能较高。（此处不讨论 ArrayList 的扩容情况）。
向 LinkedList 最后一位插入元素时，与其头插相同，性能较高。
此时可能会有疑问，LinkedList 进行尾插时，不需要遍历一遍找到尾部元素再进行插入错误吗？