ArrayList

ArrayList实现了RandomAccess，Cloneable，Serializable接口

RandomAccess接口使得ArrayList反对随机读，这里举例在Collections中有简略的利用：

public static <T>    int binarySearch(List<? extends Comparable<? super T>> list, T key) {        if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)            return Collections.indexedBinarySearch(list, key);        else            return Collections.iteratorBinarySearch(list, key);    }

在二分查找的办法中，依据是否实现RandomAccess接口，抉择不同的遍历形式。

ArrayList是List接口的一个实现类，底层是基于数组实现的存储构造，能够用于装载数据，数据都是寄存到一个数组变量中。

transient Object[] elementData; // non-private to simplify nested class access 非公有，不便嵌套类拜访

transient是一个关键字，它的作用能够总结为一句话：将不须要序列化的属性前增加关键字transient，序列化对象的时候，这个属性就不会被序列化。你可能会感觉奇怪，ArrayList能够被序列化的啊，源码可是实现了java.io.Serializable接口啊，为什么数组变量还要用transient定义呢？

对于transient，文章开端会进行解答。

当咱们新建一个实例时，ArrayList会默认帮咱们初始化数组的大小为10

//Default initial capacity.private static final int DEFAULT_CAPACITY = 10;

但请留神，这个只是数组的容量大小，并不是List真正的大小，List的大小应该由存储数据的数量决定，在源码中，获取实在的容量其实是用一个变量size来示意

//The size of the ArrayList (the number of elements it contains).private int size;

在源码中，数据默认是从数组的第一个索引开始存储的，当咱们增加数据时，ArrayList会把数据填充到上一个索引的前面去，所以，ArrayList的数据都是有序排列的。而且，因为ArrayList自身是基于数组存储，所以查问的时候只须要依据索引下标就能够找到对于的元素，查问性能十分的高，这也是咱们十分青眼ArrayList的最重要的起因。

然而，数组的容量是确定的啊，如果要存储的数据大小超过了数组大小，那不就有数组越界的问题？

对于这点，咱们不必放心，ArrayList帮咱们做了动静扩容的解决，如果发现新增数据后，List的大小曾经超过数组的容量的话，就会新增一个为原来1.5倍容量的新数组，而后把原数组的数据一成不变的复制到新数组中，再把新数组赋值给原来的数组对象就实现了。

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

数组的最大容量为Integer.MAX_VALUE（2,147,483,648），而-8只是为了防止一些机器内存溢出

/**  * The maximum size of array to allocate.  * Some VMs reserve some header words in an array.  * Attempts to allocate larger arrays may result in  * OutOfMemoryError: Requested array size exceeds VM limit  */private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;private static int hugeCapacity(int minCapacity) {    if (minCapacity < 0) // overflow        throw new OutOfMemoryError();    return (minCapacity > MAX_ARRAY_SIZE) ?        Integer.MAX_VALUE :    MAX_ARRAY_SIZE;}

扩容之后，数组的容量足够了，就能够失常新增数据了。

除此之外，ArrayList提供反对指定index新增的办法，就是能够把数据插入到设定的索引下标，删除的时候也是一样，指定index，而后把前面的数据拷贝一份，并且向前挪动，这样原来index地位的数据就删除了。

而通过index进行add和remove办法，底层都是用到System.arraycopy办法

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++;}public E remove(int index) {    rangeCheck(index);    modCount++;    E oldValue = elementData(index);    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    return oldValue;}

而System.arraycopy办法为本地办法

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

这里插入一个知识点：java的复制操作可分为浅复制和深复制，深度复制能够将对象的值和对象的内容复制，浅复制是针对对象援用的复制。

System.arraycopy在二维数组或一维数组中放的是对象的时候，复制后果是一维的援用变量传递给正本的一维数组，批改正本时，会影响原来的数组。

而对于简略的一维数组，这种复制属性值传递，批改正本不会影响原来的值。

到这里咱们也不难发现，这种基于数组的查问尽管高效，但增删数据的时候却很耗性能，因为每增删一个元素就要挪动对应index前面的所有元素，数据量少点还无所谓，但如果存储上千上万的数据就很吃力了，所以，如果是频繁增删的状况，不倡议用ArrayList。

既然ArrayList不倡议用的话，这种状况下有没有其余的汇合可用呢？

当然有啊，这就是咱们上面要说的LinkedList

LinkedList

LinkedList 是基于双向链表实现的，不须要指定初始容量，链表中任何一个存储单元都能够通过向前或者向后的指针获取到后面或者前面的存储单元。在 LinkedList 的源码中，其存储单元用一个外部类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增删数据的时候不须要像ArrayList那样挪动整片的数据，只须要通过援用指定index地位前后的两个节点即可。

删除数据也是同样原理，只须要扭转index地位前后两个节点的指向地址即可。

这样的链表构造使得LinkedList能十分高效的增删数据，在频繁增删的情景下能很好的应用，但不足之处也是有的。

尽管增删数据很快，但查问就不怎么样了，LinkedList是基于双向链表存储的，当查问对应index地位的数据时，会先计算链表总长度一半的值，判读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;    }}

尽管曾经二分法来做优化，但仍然会有遍历一半链表长度的状况，如果是数据量十分多的话，这样的查问无疑是十分慢的。

这也是LinkedList最无奈的中央，鱼和熊掌不可兼得，咱们既想查的快，又想增删快，这样的坏事怎么可能都让咱们遇到呢？所以，个别倡议LinkedList应用于增删多，查问少的情景。

除此之外，LinkedList对内存的占用也是比拟大的，毕竟每个Node都保护着前后指向地址的节点，数据量大的话会占用不少内存空间。

外表上看，LinkedList的Node存储构造仿佛更占空间，但别忘了后面介绍ArrayList扩容的时候，它会默认把数组的容量扩充到原来的1.5倍的，如果你只增加一个元素的话，那么会有将近原来一半大小的数组空间被节约了，如果原先数组很大的话，那么这部分空间的节约也是不少的。

所以，如果数据量很大又在实时增加数据的状况下，ArrayList占用的空间不肯定会比LinkedList空间小，这样的答复就显得审慎些了，听下来也更加让人容易认同，但你认为这样答复就完满了吗？非也

还记得我后面说的那个transient变量吗？它的作用曾经说了，不想序列化的对象就能够用它来润饰，用transient润饰elementData意味着我不心愿elementData数组被序列化。为什么要这么做呢？

这是因为序列化ArrayList的时候，ArrayList外面的elementData，也就是数组未必是满的，比方说elementData有10的大小，然而我只用了其中的3个，那么是否有必要序列化整个elementData呢？显然没有这个必要，因而ArrayList中重写了writeObject办法：

private void writeObject(java.io.ObjectOutputStream s)    throws java.io.IOException{    // Write out element count, and any hidden stuff    int expectedModCount = modCount;    s.defaultWriteObject();    // Write out size as capacity for behavioural compatibility with clone()    s.writeInt(size);    // Write out all elements in the proper order.    for (int i=0; i<size; i++) {        s.writeObject(elementData[i]);    }    // modCount 与 expectedModCount用来保障，在进行迭代遍历时，add或remove等操作引起的谬误    if (modCount != expectedModCount) {        throw new ConcurrentModificationException();    }}

每次序列化的时候调用这个办法，先调用defaultWriteObject()办法序列化ArrayList中的非transient元素，elementData这个数组对象不去序列化它，而是遍历elementData，只序列化数组外面有数据的元素，这样一来，就能够放慢序列化的速度，还可能缩小空间的开销。

个别状况下，LinkedList的占用空间更大，因为每个节点要保护指向前后地址的两个节点，但也不是相对，如果刚好数据量超过ArrayList默认的长期值时，ArrayList占用的空间也是不小的，因为扩容的起因会节约将近原来数组一半的容量，不过，因为ArrayList的数组变量是用transient关键字润饰的，如果汇合自身须要做序列化操作的话，ArrayList这部分多余的空间不会被序列化。