15-谈谈ArrayList和LinkedList的区别

1，底层数据结构的差异

ArrayList，数组，连续一块内存空间
LinkedList，双向链表，不是连续的内存空间

2，一个常规的结论

虽然不严谨，但也可以应付很多面试了

ArrayList，查找快，因为是连续的内存空间，方便寻址，但删除，插入慢，因为需要发生数据迁移
LinkedList，查找慢，因为需要通过指针一个个寻找，但删除，插入块，因为只要改变前后节点的指针指向即可。

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，该如何实现，编写伪代码即可