前言

数据结构在计算机中的存储方式(线性表的物理结构)主要分为以下两种：

顺序存储结构：数据存储在连续的存储单元中，如数组
- 优点
  - 存储密度大（＝1），存储空间利用率高，不需要为元素之间的逻辑关系而增加额外存储空间
  - 随机存取表中元素
- 缺点
  - 插入和删除操作需要移动元素，效率低
  - 当线性表变化较大的时候，难以确定存储空间的容量
链式存储结构：数据存放在任意的存储单元中，如链表
- 优点：
  - 逻辑相邻的节点物理上不必相邻，插入、删除灵活，只需改变节点中的指针指向
- 缺点：
  - 存储密度小（<1），存储空间利用率低，需为元素之间的逻辑关而增加额外存储空间
  - 查找节点时需遍历元素节点，效率比顺序存储慢

ArrayList是基于数组结构(顺序存储)的列表，LinkedList是基于双向链表(链表存储)的列表，在介绍了以上两种存储结构后，相信即使不了解LinkedList和ArrayList的源码也知道这两个列表的核心区别了，但作为开发者，一定的源码了解还是需要的。

ArrayList源码分析

核心结构(类图分析)

List：声明是一个有序的集合，可以控制元素位置并索引访问。
RandomAccess：声明支持快速随机访问的标记接口，常用于列表类实现。该接口的主要目的是允许通用算法更改其行为，即必要时选择更好的算法进行性能上的提高，实现了该接口的列表使用for遍历比迭代器Iterator遍历效率高。
Serializable：启用类的可序列化特性。
Cloneable：声明类是可克隆的，且调用clone()方法时不会抛出CloneNotSupportedException
AbstractList：提供了List接口的基本实现，并尽可能的减少List接口”随机访问”数据存储支持的工作

属性解析

DEFAULT_CAPACITY：默认容量10，用于构造函数初始化与容量运算。
EMPTY_ELEMENTDATA：共享的空数组，调用ArrayList有参构造函数参数容量值为0(即一般考虑不再进行容量扩展)时赋给elementData。

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

DEFAULTCAPACITY_EMPTY_ELEMENTDATA：共享的空数组，与EMPTY_ELEMENTDATA区别在于该数组是用来容量运算的，调用ArrayList无参构造函数时会把该对象赋给elementData,添加元素时再重新计算扩容，所以一般建议使用有参构造函数赋予原始容量。

1
2
3

public ArrayList() {
  this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

elementData：存储ArrayList的元素的数组缓冲区。
size：ArrayList包含的元素数量，elementData数组的元素数量。
MAX_ARRAY_SIZE：分配的最大数组大小,值为Integer.MAX-8

方法解析

add(E)添加元素

/**
 * (1) 数组末尾添加元素 
 */
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 容量值自增并将元素附加到数组末尾
    elementData[size++] = e;
    return true;
}

/**
 * (2) 确保内部的容量能满足所需最小容量minCapacity
 */
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

/**
 * (3) 根据数组所需的最小容量minCapacity进行容量计算
 */
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    // 若元素数组为引用的空数组，则返回默认容量(10)与minCapacity之间的最大值，不为空则返回minCapacity
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

/**
 * (4) 根据数组所需的最小容量minCapacity确保精确的容量
 */
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // 判断添加元素后的元素数目是否大于数组长度，true则进行数组扩容，false则完成元素添加
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

/**
 * (5) 根据数组所需的最小容量minCapacity判断是否扩容
 */
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // 判断添加元素后的元素数目是否大于数组长度，true则进行扩容，false则完成元素添加
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}


/**
 * (6) 重新建一个至少可以容纳最小容量minCapacity的数组并进行数组元素拷贝，消耗大
 */
private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    // 若所需最小容量minCapacity大于旧容量oldCapacity+oldCapacity右移1值，则新容量为minCapacity，反正新容量为旧容量运算值
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 大容量数组，一般不会调用到
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // 新建一个长度为newCapacity的数组并将旧数组元素负责过来
    elementData = Arrays.copyOf(elementData, newCapacity);
}

/**
 * 大容量计算，一般不会调用到
 */
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

以下重新整理一下新增的的步骤：

add()数组末尾添加元素
ensureCapacityInternal()确保内部的容量能满足所需最小容量minCapacity
calculateCapacity()根据数组所需的最小容量minCapacity进行容量计算
ensureExplicitCapacity()根据数组所需的最小容量minCapacity确保精确的容量
ensureExplicitCapacity()根据数组所需的最小容量minCapacity判断是否扩容,若需要则进行步骤6
grow()重新建一个至少可以容纳最小容量minCapacity的数组并进行数组元素拷贝，消耗大，所以建议一般使用有参构建函数创建列表时设置好容量

由上述流程可以看出，ArrayList的add(E e)方法在容量足以确保的情况下效率是很高的，直接将新元素赋予数组元素的末尾下标+1即可，复杂度仅为O(1)。

add(int, E)增元素

public void add(int index, E element) {
    rangeCheckForAdd(index);
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1, size - index);
    elementData[index] = element;
    size++;
}

该方法的主要核心在System.arraycopy()方法，该方法把elementData数组中的index位置起的size-index个元素(即index下标后的元素)复制到下标index+1，然后再把新的元素element赋到index下标位置。由于需要进行元素的位置逐个后移，所以性能耗费大，时间复杂度为O(n)，n为指定位置后的元素数目。
如在非末尾位置插入元素的操作较多，选择LinkedList效果会比ArrayList更好。

addAll(Collection<? extends E>)添加元素

public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // Increments modCount
    System.arraycopy(a, 0, elementData, size, numNew);
    size += numNew;
    return numNew != 0;
}

由上源码可以看到当添加集合元素时，也是需要进行数组拷贝的，不过是直接拷贝到列表数组末尾，时间复杂度由集合元素数目而定，即为O(n)。

remove(Object)删元素

public boolean remove(Object o) {
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    } else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}

private void fastRemove(int index) {
    modCount++;
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    elementData[--size] = null; // clear to let GC do its work
}

虽然删除元素的主要方面命名为fastRemove()，但从其代码依然可以看出这方法并不fast，指定位置删除元素后还要进行元素前移，性能耗费与指定位置添加差别不大，时间复杂度为O(n)，n为指定位置后的元素数目。
如删除元素的操作较多，选择LinkedList效果会比ArrayList更好。

set(int, E)改元素

public E get(int index) {
    rangeCheck(index);
    return elementData(index);
}

替换指定下标数组元素，复杂度为O(1)，效率高。

get(int)查元素

public E get(int index) {
    rangeCheck(index);
    return elementData(index);
}

根据下标获取数组元素，复杂度为O(1)，效率高。

总结

ArrayList有以下特点：

添加元素性能因参数有所区别，但都需注意数组容量不足时ArrayList会进行扩容产生性能消耗
- add(E)在数组末尾添加元素，复杂度O(1)
- add(int, E)在数组指定位置添加元素，复杂度O(n),n为下标后的元素数目
- addAll(Collection)在数组末尾添加集合元素，复杂度O(n),n为集合中的元素数目
删除元素慢，remove()删除元素，后面元素需逐个移动，复杂度O(n),n为下标后的元素数目
更改效率高，set(index, E)直接根据下标替换数组元素，复杂度O(1)
查询效率高，get(index)直接根据下标获取数组元素，复杂度O(1)

`LinkedList`源码解析

核心结构(类图分析)

LinkedList是基于双向链表数据结构的列表，链表中的每个节点对应内部类Node。

LinkedList实现了List和Deque(双向队列)接口，即该类包含了列表与双向队列的操作方法，其类图如下：

AbstractSequentialList：提供List接口的基本实现，以最小化实现List接口类顺序访问数据存储所需要提供的支持(实现)。

从类的继承与接口实现角度看，LinkedList与ArrayList的区别在于LinkedList继承了AbstractSequentialList列表类与实现了Deque双向队列接口，少实现了一个快速访问接口RandomAccess，因而相比于ArrayList访问效率会有所不及，但多了双向队列的特性(从这个角度看挺有意思的)。

`LinkedList`常用源码解析

由于LinkedList是链表结构列表，所以访问该列表中的元素只能通过第一个节点或最后一个节点遍历获取，因此查询的效率比使用数组根据下标获取元素的ArrayList慢。

属性解析

size：列表元素数目
first：第一个节点
last：最后一个节点

方法解析

add(E)添加元素

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++;
}

由源码看出，LinkedList添加元素的流程如下：

将当前列表的最后一个节点引用赋予临时变量l
创建一个新的节点存放新元素e，并把最后一个节点的引用l赋予新节点e
将最后一个节点的last指向新节点newNode
判断列表之前的最后一个节点是否为空(即列表是否为空)，空则将第一个节点first指向新节点newNode，非空则将之前最后一个节点的下一节点指向新节点

LinkedList的add(E)与addLast(E)的调用与效果是一样的，都是新建一个Node节点并更改最后一个节点的指向，消耗也不大，时间复杂度为O(1)。

add(int,E)添加元素

public void add(int index, E element) {
    checkPositionIndex(index);  // 1. 校验索引是否超出列表范围
    if (index == size)
        linkLast(element);  // 2. 下标为元素数目则直接末尾添加
    else
        linkBefore(element, node(index)); // 3. 获取链表中指定索引的节点，为新元素创建节点并插入到指定节点之前
}

private void checkPositionIndex(int index) {
    if (!isPositionIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

private boolean isPositionIndex(int index) {
    return index >= 0 && index <= size;
}

/**
 * 3.1 遍历节点以获取指定下标节点
 */
Node<E> node(int index) {
    // 若index < size / 2. 则从第一个节点开始遍历，否则从最后一个节点开始遍历
    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;
    }
}


/**
 * 3.2 为新元素创建节点并插入到指定节点之前
 */
void linkBefore(E e, Node<E> succ) {
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}

重新梳理一下LinkedList指定位置添加元素流程：

校验位置索引是否超出列表范围
若index < size / 2. 则从第一个节点开始遍历，否则从最后一个节点开始遍历
获取链表中指定索引index的节点，为新元素创建节点并插入到指定节点之前
3-1. 若index < size / 2. 则从第一个节点开始遍历，否则从最后一个节点开始遍历，并返回指定索引节点
3-2. 为新元素创建节点并插入到指定节点之前

LinkedList虽然要遍历才能获取到指定位置节点，但插入元素时只需新建一个节点并更改相应的引用而已，并没有更多的更改操作，相比ArrayList的列表元素后移性能自然要好上不少，所以当对列表位置添加元素操作较多时选择LinkedList比ArrayList更好。

remove(Object)删除元素

public boolean remove(Object o) {
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

/**
 * 删除节点链接
 */
E unlink(Node<E> x) {
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;
    if (prev == null) {
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }
    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }
    x.item = null;
    size--;
    modCount++;
    return element;
}

删除节点流程：

遍历获取目标元素节点
更改目标节点的上一节点与下一节点引用，更改元素数目

删除节点与添加节点的操作区别不大，都是遍历更改节点的链接，效率比ArrayList的删除操作效率高。

get(int)获取节点

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}
Node<E> node(int index) {
    // 若index < size / 2. 则从第一个节点开始遍历，否则从最后一个节点开始遍历
    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;
    }
}

由于LinkedList是基于双向链表的数据结构，所以查询时也是按照双向链表的查询方式，需要从头部或尾部开始遍历查找，故查询的性能比基于数组结构的ArrayList要差。

总结

LinkedList有以下特点：

增删元素快，遍历到指定节点后只需更改”指针”指向
查询效率慢，每次查询都需遍历链表
相比ArrayList需更多的存储空间来存储指向

前言

ArrayList源码分析

核心结构(类图分析)

属性解析

方法解析

add(E)添加元素

add(int, E)增元素

addAll(Collection<? extends E>)添加元素

remove(Object)删元素

set(int, E)改元素

get(int)查元素

总结

LinkedList源码解析

核心结构(类图分析)

LinkedList常用源码解析

属性解析

方法解析

add(E)添加元素

add(int,E)添加元素

remove(Object)删除元素

get(int)获取节点

总结

`LinkedList`源码解析

`LinkedList`常用源码解析