ArrayList 和 LinkedList 区别

ArrayList：基于数组实现；

LinkedList：基于双向链表实现；使用 Node 存储链表节点信息；

ArrayList 和 LinkedList 都实现了 List 接口，且两者都是线程不安全的

区别：

1. ArrayList 使用动态数组存储元素，而 LinkedList 使用双向链表来存储元素。

2. 对于随机访问，ArrayList要优于LinkedList； 对于插入和删除操作，LinkedList优于ArrayList。

3. LinkedList比ArrayList更占内存，因为LinkedList的节点除了存储数据，还存储了两个引用，一个指向前一个元素，一个指向后一个元素。

4. ArrayList 只能用作列表；LinkedList 可以用作列表或者队列，因为它还实现了 Deque 接口。

   在查询时，ArrayList 直接根据下标获取，和数组的长度无关，查询速度快；而LinkedList 则需要从头节点开始遍历，下标小于链表长度的一半时，从前往后遍历；否则从后往前遍历，查询速度慢。

   在增加时，ArrayList 将新的元素添加的指定的位置时，会将插入位置后的元素依次向后复制，添加速度慢；而 LinkedList 则是可以直接加入进去，先用 n 记录 p.next ,然后 p.next = newNode ,再把 newNode.next = n；这样就实现了添加，而且速度更快。

   在删除时，ArrayList 会将指定位置后的元素依次向前复制，删除速度也慢；而 LinkedList 则是将原来的 p.next 变为了p.next.next，就实现了删除，而且速度更快。