ArrayList,LinkedList,CopyOnWrite

本文基于JDK1.8
在看dubbo的时候，看到使用了CopyOnWriteArrayList，顺带了解下

ArrayList

底层结构

ArrayList的底层是基于数组的

transient Object[] elementData;

并且默认初始化的大小为0,可以从构造函数看到

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() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

在默认没有设置大小或者传入Collection为空的情况下，会设置elementData为EMPTY_ELEMENTDATA或者DEFAULTCAPACITY_EMPTY_ELEMENTDATA，这两个常量都是长度为0数组

private static final Object[] EMPTY_ELEMENTDATA = {};

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

扩容机制

由于数组初始化长度是固定的，所以当个数超过一定限制时，会进行扩容操作，从add方法看起

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

可以看到在对数组增加元素前，会调用ensureCapacityInternal方法进行扩容相关工作

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

在ensureCapacityInternal方法中来确定扩容的最小值，在数组长度为0的情况下，使用默认数组大小，其他情况使用当前数组长度+1,

private static final int DEFAULT_CAPACITY = 10;

然后在ensureExplicitCapacity会判断是否需要进行扩容

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

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

只有最小扩容长度大于当前的数组长度时，才需要进行扩容，因为minCapacity是数组放入下一个元素后的长度，如果大于 elementData.length，说明当前数组已经放不下下一个数据，需要进行扩容
在grow方法中是具体的扩容逻辑

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

对于初始化为0的数组，会直接扩容为10
对于长度不为0的数组，扩容大小为 oldCapacity + (oldCapacity >> 1)，也就是变为原来的1.5倍
具体扩容的方式，使用Arrays.copyOf(elementData, newCapacity)进行深拷贝处理，新建一个数组，把老数组元素拷贝过去

public static <T> T[] copyOf(T[] original, int newLength) {
        return (T[]) copyOf(original, newLength, original.getClass());
    }
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
        @SuppressWarnings("unchecked")
        T[] copy = ((Object)newType == (Object)Object[].class)
            ? (T[]) new Object[newLength]
            : (T[]) Array.newInstance(newType.getComponentType(), newLength);
        System.arraycopy(original, 0, copy, 0,
                         Math.min(original.length, newLength));
        return copy;
    }

关于 System.arraycopy方法，是一个native方法

public static native void arraycopy(Object src,  int  srcPos,
                                        Object dest, int destPos,
                                        int length);

如果是数组比较大，那么使用System.arraycopy会比较有优势，因为其使用的是内存复制，省去了大量的数组寻址访问等时间

SubList

可以调用subList方法来获取当前数组的子数组，对子数组的操作会影响到父数组，因为实际操作对象还是父数组,看下add方法

public void add(int index, E e) {
    rangeCheckForAdd(index);
    checkForComodification();
    parent.add(parentOffset + index, e);
    this.modCount = parent.modCount;
    this.size++;
}

其实parent就指向了父数组

迭代器

在ArrayList中迭代器有2种，Itr和ListItr，分别通过iterator和listIterator拿到，ListItr继承于Itr
使用Itr只支持删除数组中的元素，不支持新增
使用ListItr支持新增,修改操作，但是新增的元素不会迭代出来

Itr的next方法返回的是原数组的引用

public E next() {
    checkForComodification();
    int i = cursor;
    if (i >= size)
        throw new NoSuchElementException();
    //使用的是原数组的引用
    Object[] elementData = ArrayList.this.elementData;
    if (i >= elementData.length)
        throw new ConcurrentModificationException();
    cursor = i + 1;
    return (E) elementData[lastRet = i];
}

因此对使用迭代器获取的元素进行修改时，原数组的元素也会被修改
但是在Itr迭代器使用过程中不能对数组内的元素个数进行修改，不然会抛出ConcurrentModificationException异常,主要通过modCount来实现
在得到迭代器的时候，会把当前数组的modCount存到expectedModCount变量中，并且涉及数组元素的修改操作都会对modCount++
当使用next方法获取下一个元素的时候，会使用checkForComodification方法会对比两个modCount，如果不一致，说明数组被修改了，抛出异常

final void checkForComodification() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
}

下面看下remove方法的实现

public void remove() {
    if (lastRet < 0)
        throw new IllegalStateException();
    checkForComodification();

    try {
        ArrayList.this.remove(lastRet);
        cursor = lastRet;
        lastRet = -1;
        expectedModCount = modCount;
    } catch (IndexOutOfBoundsException ex) {
        throw new ConcurrentModificationException();
    }
}

lastRet保存的是当前元素的index，cursor保存的是下一个元素的index
remove的时候因为把当前元素删除了，后面元素整体向前移动一位，所以cursor就等于lastRet了，并且要重置expectedModCount
继续看下ListItr的add方法

public void add(E e) {
    checkForComodification();

    try {
        int i = cursor;
        ArrayList.this.add(i, e);
        cursor = i + 1;
        lastRet = -1;
        expectedModCount = modCount;
    } catch (IndexOutOfBoundsException ex) {
        throw new ConcurrentModificationException();
    }
}

在增加元素后，会把cursor向右移动一位，并且重置expectedModCount

线程安全

ArrayList不是线程安全的，如果在多线程进行add的时候，发生了扩容，会发生不可知的错误吧，在多线程中使用ArrayList，需要进行同步

LinkedList

底层结构

LinkedList底层基于链表，会保留first，last 头尾指针，不存在扩容问题

transient Node<E> first;

transient Node<E> last;

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

是一个双向链表，所以LinkedList支持对头尾的操作，可以用来当栈，队列

查询优化

因为是链表，所以查询一个元素必须从头或尾开始查找，LinkedList会根据查找元素index进行优化

Node<E> node(int index) {
        // assert isElementIndex(index);

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

size >> 1就是当前长度的中位数
如果在中位数左边，那么从头开始遍历
如果在中位数右边，从尾开始遍历
相比数组的随机访问，链表在查询方面是要慢一些，插入方面，也不一定链表占优，因为涉及到数组插入删除的位子，以及是否扩容问题。

CopyOnWriteArrayList

底层结构

CopyOnWriteArrayList底层基于数组，是一个线程安全的List，进行增删改的时候都会底层数组同步进行覆盖，相当于每次修改都会扩容，主要用于使用迭代器或者foreach的时候返回的是副本，提高遍历效率，但是修改操作性能降低。

修改操作

在修改，增加，删除操作都会使用ReentrantLock进行同步,我们以增加方法示例

public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] elements = getArray();
        int len = elements.length;
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        newElements[len] = e;
        setArray(newElements);
        return true;
    } finally {
        lock.unlock();
    }
}

在add方法中会调用Arrays.copyOf方法对原数组进行深拷贝，增加元素后，对原数组进行覆盖
其他修改操作也都会这样做，为什么？在修改操作把底层数组指向新的数组，但是迭代器里面引用的还是老数组，相当于每个迭代器都会存在特定时间点的一个副本，当然，对副本的操作，不会影响到新的底层数组

这个设计很巧妙，并没有弄两个数组来回切换，很好的利用了强引用。

看下CopyOnWriteArrayList中一个变量

private final Object[] snapshot;

会把之前老数组的引用保存下来，
而在ArrayList或者LinkedList使用的都是从外部类拿直接引用，如

Object[] elementData = ArrayList.this.elementData;

总结

ArrayList和LinkedList不是线程安全的，在多线程情况下需要进行同步，
ArrayList底层数组，查询，修改快，插入，删除较慢
LinkedList底层链表插入，删除较快，查询，修改慢，同时可以模拟栈，队列操作
ArrayList和LinkedList不太好对比，和数据量，插入删除位置都有关，量级到一定程度在根据操作择优而选吧，一般使用ArrayList
而CopyOnWriteArrayList是线程安全的，但是也要考虑场景，查询以及遍历是多数操作的情况下适合使用，毕竟每次修改都需要深拷贝，数据量大了也很损耗性能，并且也浪费内存，可能还不如同步的ArrayList

最后

希望大家关注下我的公众号

image