转载

ArrayList和LinkedList的区别以及部分重要源码（JDK8）分析

首先，他们都是线程不安全的、插入有序的集合。

以下结论只存在于理论中，需要大量的数据才能有明显的区别，而有时这种区别也并不稳定

ArrayList数据结构是数组，所以查询快，增删慢，因为它是数组，可以通过索引进行查找，而增删慢的原因是要不断创建新数组扩容

LinkedList数据结构是链表，所以增删快，查找慢，因为链表之间首尾相连，查找时需要移动指针，而增删快的原因是不需要频繁创建新结构来扩容，只需要修改节点之间的引用关系即可

ArrayList源码分析

private static final int DEFAULT_CAPACITY = 10;
复制代码

初始长度为10，如果已知数据长度，最好一开始就设置好，这样可以避免扩容

add方法：

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}
复制代码

在添加元素时，ArrayList会先判断是否需要扩容，也就是ensureCapacityInternal(size + 1);方法

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
复制代码

首先，modCount自增，记录当前集合变化的次数，然后判断当前增加一个元素后的集合长度 - 当前集合的长度是否大于0，如果是，则需要扩容，否则则不需要

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;//1
    int newCapacity = oldCapacity + (oldCapacity >> 1);//2
    if (newCapacity - minCapacity < 0)//3
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)//4
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);//5
}
复制代码

1.计算当前集合的长度

2.计算新长度 = 当前集合的长度 + 当前容器长度右移运算1位后的新集合长度，也就是当前集合长度的1.5倍

3.判断新长度 - 当前集合所需长度是否小于0，如果是则表示当前集合扩容1.5倍无法满足当前集合所需长度，所以将当前集合所需长度的值赋给新长度

4.判断新集合长度 - (Integer最大值 - 8)是否大于0，如果是则进入hugeCapacity(minCapacity);方法

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}
复制代码

第一步判断是否小于0，是因为如果minCapacity的值大于Integer所允许的最大值，则抛出内存溢出异常
第二步判断当前所需长度是否大于集合最大长度，如果是，则将Integer所允许的最大值赋值给集合的新长度，否则使用允许的最大集合长度

5.将当前数组按照新长度完全复制一份给新数组

而ArrayList集合的最大长度为什么为Integer.MAX_VALUE - 8？因为存储数组需要8字节，所以需要减8。

LinkedList

它是一个数据结构为链表的集合，每一个节点都保存了当前节点的数据和上下连接的两个节点的实例

LinkedList没有初始大小，因为每一个都是首尾连接的Node

add方法:

public boolean add(E e) {
    linkLast(e);
    return true;
}
复制代码

void linkLast(E e) {
    final Node<E> l = last;//1
    final Node<E> newNode = new Node<>(l, e, null);//2
    last = newNode;//3
    if (l == null)//4
        first = newNode;
    else
        l.next = newNode;
    size++;//5
    modCount++;//6
}
复制代码

1.获取当前集合的末端节点

2.创建一个新节点，参数由左至右依次：上一节点，当前节点数据，下一节点

3.将新的节点设置为末端节点

4.如果上一个末端节点为空，则证明这是当前集合的第一个节点，则将新节点设置为头部节点。否则证明当前集合之前已有数据，则将新节点与上一个末端节点连接起来

5.当前集合长度+1

6.记录集合变化数+1

以上，是个人的总结，如有疑问请留言指出，感谢

原文 https://juejin.im/post/5e1a0790e51d450200787605

正文到此结束