在日常开发中对于List集合的使用频率是非常高的，它的使用也比较简单，创建一个List实现类的实例，然后调用add、remove、get等方法就可以对其进行增删改查操作了，会使用了就代表了解它了吗？想了解它，就要去看下它的源码，List是一个接口，就去看一看它的实现类ArrayList和LinkedList。
ArrayList
ArrayList是List的实现类，底层是由数组实现的一个集合类。由于平时使用到的数组创建后，其大小就不可以改变，而ArrayList的大小是可以改变的，也可以将ArrayList称为动态数组。
ArrayList<String> list = new ArrayList();
通过上面就可以创建一个ArrayList实例，在ArrayList的构造函数中，会创建一个默认容量为10的空数组，用于后面的数据存储；
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
DEFAULTCAPACITY_EMPTY_ELEMENTDATA就是一个默认的空数组，这里所说的空是元素为空；
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
另外在创建实例化对象时，还可以通过调用有参的构造函数来指定初始化时动态数组的容量的大小；
public ArrayList(int initialCapacity) {
//initialCapacity 容量的大小
if (initialCapacity > 0) {
//如果传入的容量大于0 就安装传入的容量创建数组
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
//如果传入的容量大小为0 就使用系统默认的数组
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
在调用ArrayList的构造函数时，就会创建对应容量的数组实例，就会在堆空间中申请对应空间大小且内存地址连续的内存空间，创建好实例对象后，通过调用add方法，可以添加对应的元素。
public boolean add(E e) {
//如果当前数组的容量不足时，会进行扩容处理
ensureCapacityInternal(size + 1); // Increments modCount!!
//存储对应的元素
elementData[size++] = e;
return true;
}
public void add(int index, E element) {
//传入index的不能大于数组元素的大小 size 也不能小于0
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
//如果当前数组的容量不足时，会进行扩容处理
ensureCapacityInternal(size + 1); // Increments modCount!!
//将index位置后的元素往后挪动 给新元素空出index的位置 存储新元素
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
//存储新元素
elementData[index] = element;
size++;
}
第一个add方法默认是往数组元素的最后一个位置添加，第二个add方法是往数组指定位置进行添加，在添加的时候都会去看数组的当前容量是否够，不够的话，就会进行扩容，扩容其实就是创建一个新的指定容量大小的数组，然后将之前数组中的元素copy到新的数组中；
private void ensureCapacityInternal(int minCapacity) {
//minCapacity 是数组当前元素的大小size+1 不是数组length哦
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
//数组创建可 没有添加任何元素 DEFAULT_CAPACITY 默认容量 为10 走到这里minCapacity 最终为10
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
//在数组有元素的前提下 minCapacity 是数组元素大小size+1
//elementData.length 代表的是数组的长度
//如果数组元素大小大于数组的长度 就需要进行扩容处理
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
//未扩容前数组的长度
int oldCapacity = elementData.length;
//计算新的容量 旧容量+旧容量的一半 其实就是旧容量的1.5倍
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
elementData = Arrays.copyOf(elementData, newCapacity);
}
通过Arrays.copyof就达到了扩容的目的，第一个add方法默认是将新元素添加到数组元素大小的最后，第二个add方法，是添加到指定位置，扩容之后，还要将插入位置后的元素往后面挪动，便于新元素的添加；
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
public E get(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
//返回指定位置的元素
return (E) elementData[index];
}
通过调用get方法就可以返回指定位置的元素，并且不管传入的index是多少只要是在动态数组size的返回之内，都能快速的返回对应的元素，数组中元素都有对应的内存地址，在一开始创建的时候就会纪录下数组首元素的地址，由于数组中元素的地址都是连续的，查找的时候就会根据数组首元素的地址，及每个元素占用的字节大小*index位置，快速得到index对应元素的内存地址，从而获取到该元素。
//修改指定位置的元素
public E set(int index, E element) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
//获取该位置的之前的元素
E oldValue = (E) elementData[index];
//将新元素覆盖之前的元素
elementData[index] = element;
//返回旧元素
return oldValue;
}
//删除指定位置的元素
public E remove(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
modCount++;
//获取指定位置的元素
E oldValue = (E) elementData[index];
int numMoved = size - index - 1;
//这里的删除 如果删除的元素不是数组的最后一个元素 采用的是先将index位置后面的元素往前挪到index位置，将index位置
//的元素覆盖掉，然后将数组的最后一个元素置为null
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//这里置为null 在gc时能及时的回收掉
//如果不置为null，只是将size-- 虽然不能操作该元素 但是在gc的时候不能回收掉
elementData[--size] = null; // clear to let GC do its work
//返回删除的元素
return oldValue;
}
//直接删除数组元素
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
}
在删除指定位置的元素时，如果index位置不是最后，采用的是将数组index后的元素往前挪到index位置，将index位置的元素覆盖掉，然后删除掉数组最后的一个元素，这样index位置的元素就删除了，remove(Object o)是一样的，通过获取到元素的位置index，然后删除index位置的元素。
//情况所有元素
public void clear() {
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
在情况所有元素时，其实将size置为0，数组中的元素就不可以进行操作了，但是源码中对数组进行遍历将数组中的元素置为null，这样在gc时，能及时回收掉，不过并没有将数组置为null，这样便于后续使用时不用去创建新的数组。
总结：
1、在使用动态数组时，会申请一段内存地址连续的内存空间，这样容易造成内存的浪费；
2、在进行查询操作时，由于申请的是一段内存地址连续的内存空间，会根据首元素的地址、元素占用的字节大小*index，快速计算出任意index元素的内存地址，找到该元素，查询速度很快；
3、同样的修改指定位置的元素的速度和查询一样也很快；
4、在添加元素时如果超过了容量的大小，需要进行扩容，然后将原数组进行拷贝操作，会耗时；
5、在添加或删除元素时，如果不是在数组最后位置进行添加或删除，需要对数组index进行往前挪动(删除)或往后挪动(添加)，会耗时；
LinkedList
LinkedList是List的实现类，底层采用的是双向链表的结果进行数据的存储，同时它还是Deque的实现类，也是一个双端队列，它是将一个一个元素存储在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;
}
}
//往集合尾部添加
public boolean add(E e) {
linkLast(e);
return true;
}
//往指定位置添加
public void add(int index, E element) {
checkPositionIndex(index);
//对index进行了判断 是否是往尾部添加
if (index == size)
//往尾部添加元素
linkLast(element);
else
linkBefore(element, node(index));
}
在add的时候，先看往尾部添加元素，往尾部添加的话，需要修改之前last元素的next指向和现有last元素的pre和next指向，原有last元素的next需要执行添加的元素，添加元素的pre需要指向之前的last，然后添加的元素的next指向null；
void linkLast(E e) {
//获取之前last的节点
final Node<E> l = last;
//创建添加元素的节点 它的pre就是之前的last，next为null 因为它是最后一个节点了
final Node<E> newNode = new Node<>(l, e, null);
//修改last节点的值
last = newNode;
if (l == null)
//这里代表的时首次添加 集合中没有其他元素，first和last是同一节点
first = newNode;
else
//修改之前last的next指向 指向新添加元素的节点
l.next = newNode;
size++;
modCount++;
}
通过修改之前last和新添加元素节点的指向就在尾部添加完新元素了，如果不是往尾部添加元素，就需要先查找出现有元素中index位置对应的元素，然后修改index对应元素节点的pre、next，新元素对应节点的pre、next指向；
//查找对应位置的节点
Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {
//如果index的位置小于size的一半 从左往右开始查找
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
//如果index的位置大于size的一半 从右往左开始查找
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
不管是从左往右查找，还是从右往左查找，都只查找到index位置；
//进行元素的添加
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
//之前index位置对应的pre 的节点
final Node<E> pred = succ.prev;
//创建新的节点 新节点的pre是之前index位置节点的pre next就是之前index位置的节点
final Node<E> newNode = new Node<>(pred, e, succ);
//修改之前index节点的pre的指向 之前index节点的pre就是新添加元素的节点
succ.prev = newNode;
if (pred == null)
//代表添加的index位置为0 往首部添加 修改first的值
first = newNode;
else
//修改之前index位置对应节点 pre 节点的next的指向 指向新添加元素的节点
pred.next = newNode;
size++;
modCount++;
}
不管是往哪个位置添加，修改的是对应节点的pre和next的指向，并不需要像动态数组那样挪动元素。
//查找指定位置的元素
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
查找最终调用node(index)获取到指定位置的节点，然后再获取到对应的元素，node(index)在上面的添加元素时，提到过了；对于修改也差不多，找到对应index位置的节点，覆盖掉该节点中的元素就可以了；
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
//删除指定位置的元素
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
E unlink(Node<E> x) {
// assert x != null;
//指定位置的元素
final E element = x.item;
//指定位置的next指向的节点
final Node<E> next = x.next;
//指定位置的pre指向的节点
final Node<E> prev = x.prev;
//修改index对应的节点的pre的指向
if (prev == null) {
//说明删除的是第一个元素 index为0 需要修改first的值
first = next;
} else {
//它的pre的next的指向为它的next
prev.next = next;
//自身的pre指向为null
x.prev = null;
}
//修改index对应的节点的next的指向
if (next == null) {
//删除的是最后一个节点 需要修改last的值
last = prev;
} else {
//它的next的pre指向它的pre
next.prev = prev;
//它的next指向为null
x.next = null;
}
//将节点中的元素置为null
x.item = null;
size--;
modCount++;
//返回删除的元素
return element;
}
删除对应index的元素时，首先通过node(index)，获取到对应的节点，然后修改当前节点的pre、next、当前节点的pre的next、当前节点的next的pre的指向，当前节点没有引用指向，在gc时，就会将内存回收掉。
//清空所有元素
public void clear() {
// Clearing all of the links between nodes is "unnecessary", but:
// - helps a generational GC if the discarded nodes inhabit
// more than one generation
// - is sure to free memory even if there is a reachable Iterator
//循环遍历所有的节点
for (Node<E> x = first; x != null; ) {
//获取当前节点的next节点
Node<E> next = x.next;
//将当前节点的元素置为null
x.item = null;
//将当前节点的next置为null
x.next = null;
//将当前节点的pre置为null
x.prev = null;
//修改当前节点的值
x = next;
}
//将first和last都置为null
first = last = null;
//size置为0
size = 0;
modCount++;
}
将所有节点的pre和next指向都断开后，在发生gc时，就会将节点所占用的内存回收掉。
总结：
1、在添加和删除元素时，是通过修改当前元素pre、next、当前元素的pre的next、当前元素的next的pre的指向来实现的，不需要对元素进行挪动和拷贝，在添加和删除的的那一刻，也即使修改指向的时候的复杂度是O1，但是在添加和删除时首先需要找到对应index位置的节点，就这点说它的复杂度并不是O1的；
2、在查找对应位置的元素节点时，采用的是二分查找；
3、需要多少内存就申请多少内存，不会造成内存的浪费；
ArrayList和LinkedList的对比
1、ArrayList底层是数组实现的，LinkedList(也是一个双端队列)是双向链表实现的；
2、ArrayList的查找通过首元素地址和字节所占用的内存大小*index的方式快速定位该元素对应的内存地址要比LinkedList的二分查找快，即ArrayList的元素查找比LinkedList的元素查找快；
3、LinkedList的增加和删除是通过修改当前元素的pre和next、当前元素的pre的next、当前元素的next的pre的指向来实现的，不需要扩容和挪动元素，对于ArrayList涉及到扩容、首位置添加还是尾位置添加：
ArrayList的添加和删除
3.1添加未扩容、删除(尾位置)：尾位置添加和删除，不需要挪动元素位置，复杂度O1
3.2添加扩容、删除(非尾位置)：添加扩容需要创建新的数组，拷贝原有数组的元素，同时需要往前(删除)、往后(添加)挪动元素
4、ArrayList创建时会申请连续内存地址的内存空间，LinkedList不需要，使用时才会申请内存空间
