1，底层数据结构的差异
ArrayList，数组，连续一块内存空间
LinkedList，双向链表，不是连续的内存空间
2，一个常规的结论
虽然不严谨，但也可以应付很多面试了
ArrayList，查找快，因为是连续的内存空间，方便寻址，但删除，插入慢，因为需要发生数据迁移
LinkedList，查找慢，因为需要通过指针一个个寻找，但删除，插入块，因为只要改变前后节点的指针指向即可。
解释：
查找：
1、对于查找某个位置而言，ArrayList更胜LinkedList，比如两个List均有a,b,c,d ，要查找第二个位置，则ArrayList更快，因为ArrayList连续的内存空间，可计算的偏移量，而LinkedList不连续，无法计算，一个哥我往下找。
2、对于查找某个固定元素而言，ArrayList与LinkedList相差无几，因为都需要进行遍历所有数据，所以两者差不多。
插入：
1、对于头部或中间位置插入，LinkedList更胜ArrayList，因为ArrayList是连续的存储空间，需要向后移动。
2、对于尾部位置插入，二者相差无几。
3，ArrayList细节分析
1，增加
- 添加到末尾，正常不需要做特别的处理，除非现有的数组空间不够了，需要扩容
- 数组初始化容量多大？10，当你知道需要存储多少数据时，建议在创建的时候，直接设置初始化大小
- 怎么扩容？
- 当发现容量不够之后，就进行扩容
- 按原先数组容量的1.5倍进行扩容，位运算，下面是关键的源码
int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1);
- 再将原先数组的元素复制到新数组，Arrays
elementData = Arrays.copyOf(elementData, newCapacity)
- 添加到其他位置，这个时候需要做整体的搬迁
- 2，删除
- 删除末尾，并不需要迁移
- 删除其他的位置，这个时候也需要搬迁
- 3，修改
- 修改之前，必须先定位
- 定位-查找-ArrayList（数组是一段连续的内存空间，定位会特别快）
- 4，查找
- 如上所述
4，LinkedList细节分析
1，提供了的两个引用（first，last）
2，增加
添加到末尾，创建一个新的节点，将之前的last节点设置为新节点的pre，新节点设置为last
我们看下源码：
void linkLast(E e) { //获取到最后一个节点 final Node<E> l = last; //构建一个新节点，将当前的last作为这个新节点的pre final Node<E> newNode = new Node<>(l, e, null); //把last指向新节点 last = newNode; //如果原先没有最后一个节点 if (l == null) //将first指向新节点 first = newNode; else //否则，将原先的last的next指向新节点 l.next = newNode; size++; modCount++; } Node节点的定义：内部类 private static class Node<E> { E item; Node<E> next; Node<E> prev; Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; } }
添加到其他位置，这个时候，就需要调整前后节点的引用指向
3，如何去定义一个双向链表的节点，如上述的源码所示
4，修改
修改最后一个节点或者第一个节点，那么就很快（first，last）
修改其他位置，如果是按坐标来定位节点，则会按照二分查找法，源码如下：
if (index < (size >> 1)) { Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; }
5，一个思考题，假如我们可以确定要存储1000个元素，那么采用ArrayList和LinkedList，
哪个更耗内存，为什么？
6，LinkedList，要实现在A和B之间插入C，该如何实现，编写伪代码即可
假设我们定位到了A节点，那么A.next就是B节点，这个是前提。
你的答案是？可以思考过后，再看答案
C.pre = A;
C.next = A.next;
A.next.pre = C;
A.next = C;