这是《Java 程序员进阶之路》专栏的第 61 篇，我们来继续探讨 ArrayList 和 LinkedList，这一篇比上一篇更深入、更全面，源码讲解、性能考量，方方面面都有涉及到了。
首先必须得感谢大家，《Java 程序员进阶之路》在 GitHub 上已经突破 400 个星标了，感谢感谢，还没 star 的赶紧安排一波了，冲击 500 星标了。
https://github.com/itwanger/toBeBetterJavaer
目前已更新或计划更新的内容，绿色✅的是已经更新的。
01、ArrayList 是如何实现的？
ArrayList 实现了 List 接口，继承了 AbstractList 抽象类。
底层是基于数组实现的，并且实现了动态扩容
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable { private static final int DEFAULT_CAPACITY = 10; transient Object[] elementData; private int size; }
ArrayList 还实现了 RandomAccess 接口，这是一个标记接口：
public interface RandomAccess {
}
内部是空的，标记“实现了这个接口的类支持快速（通常是固定时间）随机访问”。快速随机访问是什么意思呢？就是说不需要遍历，就可以通过下标（索引）直接访问到内存地址。
public E get(int index) { Objects.checkIndex(index, size); return elementData(index); } E elementData(int index) { return (E) elementData[index]; }
ArrayList 还实现了 Cloneable 接口，这表明 ArrayList 是支持拷贝的。ArrayList 内部的确也重写了 Object 类的 clone() 方法。
public Object clone() { try { ArrayList<?> v = (ArrayList<?>) super.clone(); v.elementData = Arrays.copyOf(elementData, size); v.modCount = 0; return v; } catch (CloneNotSupportedException e) { // this shouldn't happen, since we are Cloneable throw new InternalError(e); } }
ArrayList 还实现了 Serializable 接口，同样是一个标记接口：
public interface Serializable {
}
内部也是空的，标记“实现了这个接口的类支持序列化”。序列化是什么意思呢？Java 的序列化是指，将对象转换成以字节序列的形式来表示，这些字节序中包含了对象的字段和方法。序列化后的对象可以被写到数据库、写到文件，也可用于网络传输。
眼睛雪亮的小伙伴可能会注意到，ArrayList 中的关键字段 elementData 使用了 transient 关键字修饰，这个关键字的作用是，让它修饰的字段不被序列化。
这不前后矛盾吗？一个类既然实现了 Serilizable 接口，肯定是想要被序列化的，对吧？那为什么保存关键数据的 elementData 又不想被序列化呢?
这还得从 “ArrayList 是基于数组实现的”开始说起。大家都知道，数组是定长的，就是说，数组一旦声明了，长度（容量）就是固定的，不能像某些东西一样伸缩自如。这就很麻烦，数组一旦装满了，就不能添加新的元素进来了。
ArrayList 不想像数组这样活着，它想能屈能伸，所以它实现了动态扩容。一旦在添加元素的时候，发现容量用满了 s == elementData.length，就按照原来数组的 1.5 倍（oldCapacity >> 1）进行扩容。扩容之后，再将原有的数组复制到新分配的内存地址上 Arrays.copyOf(elementData, newCapacity)。
private void add(E e, Object[] elementData, int s) { if (s == elementData.length) elementData = grow(); elementData[s] = e; size = s + 1; } private Object[] grow() { return grow(size + 1); } private Object[] grow(int minCapacity) { int oldCapacity = elementData.length; if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { int newCapacity = ArraysSupport.newLength(oldCapacity, minCapacity - oldCapacity, /* minimum growth */ oldCapacity >> 1 /* preferred growth */); return elementData = Arrays.copyOf(elementData, newCapacity); } else { return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)]; } }
动态扩容意味着什么？大家伙想一下。嗯，还是我来告诉大家答案吧，有点迫不及待。
意味着数组的实际大小可能永远无法被填满的，总有多余出来空置的内存空间。
比如说，默认的数组大小是 10，当添加第 11 个元素的时候，数组的长度扩容了 1.5 倍，也就是 15，意味着还有 4 个内存空间是闲置的，对吧？
