1，底层数据结构的差异
ArrayList，数组，连续一块内存空间
LinkedList，双向链表，不是连续的内存空间
2，一个常规的结论
虽然不严谨，但也可以应付很多面试了
ArrayList，查找快，因为是连续的内存空间，方便寻址，但删除，插入慢，因为需要发生数据迁移
LinkedList，查找慢，因为需要通过指针一个个寻找，但删除，插入块，因为只要改变前后节点的指针指向即可。
细节
1.查找
ArrayList->a,c,b,d
LinkedList->a,c,b,d
1.1查找第2个元素
ArrayList连续的内存空间，可计算的偏移量
LinkedList不连续，无法计算，一个个往下找
ArrayList > LinkedList
1.2查找b在哪？
遍历 只能一个个比较ArrayList ≈ LinkedList
2.插入
2.1中间的位置插入，ArrayList连续的内存空间
LinkedList指针的转换
2.2末尾插入
ArrayList可计算，直接插入即可。
LinkedList有两个指针分别指向头部和尾部（last)。
3，ArrayList细节分析
1，增加
添加到末尾，正常不需要做特别的处理，除非现有的数组空间不够了，需要扩容
数组初始化容量多大？10，当你知道需要存储多少数据时，建议在创建的时候，直接设置初始化大小
怎么扩容？
当发现容量不够之后，就进行扩容
按原先数组容量的1.5倍进行扩容，位运算，下面是关键的源码
int oldCapacity = elementData.length;
//左边的运算数的各bai二进位全部右移若干位，“>>”右边的数指定移动的位数。
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，
哪个更耗内存，为什么？
LinkedList除了数据还要有前后两个指针,pre next
6，LinkedList，要实现在A和B之间插入C，该如何实现，编写伪代码即可
网友评论