深入理解Java集合和Map 2：LIst接口实现类ArrayList，LinkedList，Vector源码剖析及相关特点
List接口
List接口父类为collection接口
此处主要介绍其三个实现类该三各类不仅实现了List接口，LinkedList同时继承AbstractSequentialList类，ArrayList和LinkedList继承了AbstractList类。这两个被继承类实现了一些方法和迭代器相关方法。
ArrayList类
- 该类常用方法增删改查此处不做详细解释和使用示例。
- 该类底层采用数组进行实现，数组类型为Object类型。可采用有参构造和无参构造，有参构造可规定列表长度。无参构造构造对象时，实际是创建一个空数组，在添加数据时才会真正的创建一个定长数组，数组长度源码中规定长度默认为10。
private static final int DEFAULT_CAPACITY = 10;
- 该类为非线程安全类
以add()方法为例，在源码中代码以及个人解释如下所示，可知在进行数组列表添加操作时，无锁和synchronized，可知该类时非线程安全的。(Vector为线程安全)
/**
* Appends the specified element to the end of this list.
* @param e element to be appended to this list
* @return <tt>true</tt> (as specified by {@link Collection#add})
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!//该方法下文继续进行解释
elementData[size++] = e;//elementData为底层实现的数组，size为当前数组最后一个位置数据的索引
return true;
}
- 那么我们在添加元素进入列表中时，他是怎么对容量进行判断，容量不够又是怎么进行扩容的？
上文中add方法中有ensureCapacityInternal(size + 1);该方法源码中定义以及个人解释如下，size+1为当前底层数组的存储数据个数，ensureCapacityInternal方法主要作用在于确认数组的容量是否能够继续添加数据。
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
//当前数组为空时，我们计算出数组默认初始容量DEFAULT_CAPACITY和当前数组容量minCapacity两者间的最大值
//作为当前数组的最小容量
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);//该方法下文中继续解释
}
ensureExplicitCapacity方法和grow方法
//该方法主要是明确底层数组的长度，如果最小数组大于真实数组长度，那么我们需要调用grow方法进行数组扩容，这也使得我们在List中看到可以随时向List中增加元素，而不需要考虑容量的问题。关于扩容的具体方法见下文grow源码及个人解释。
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);//由该句可知，新的容量是在旧的容量//基础上加上旧容量的右移一位，可知新的容量=oldCapacity+(int)(oldCapacity/2),
//第一次扩容若定义了长度则oldCapacity为定义长度，否则，oldCapacity 等于默认10，
//随后的扩容则在当前容量的基础上加上当前容量的1/2,默认扩容为10，15，22，33....
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);//由此句可知道，列表的扩容实际是内部的数组复制，将原容量的数组复制到新容量的数组中去。
}
Vector类
- Vector的内部实现与ArrayList类似，他们在无参构造是默认初始均为10
- Vector是线程安全的，在其方法上均有synchronized关键字。由此也可知它的速度上慢一些。
- Vector通过内部源码可知，其底层也是采用数组实现，其增加长度是与ArrayList不同，其是在原有的基础上再增加相同长度
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity);
//增加一个原来长度，无参构造增加示例，10，20，40，80.....
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
LinkedList
- LinkedList的底层实现为链表，其维护一个双向链表，链表中节点为一个内部类，源码定义如下所示，其不像ArrayList和Vector定义为Object,而是一个泛型，无参构造new该对象时实际啥也没干。
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增删改很快，查询慢于其他两个。
- 线程不安全的。
- 由于底层为链表实现，所以不涉及扩容问题，每次添加元素均为添加一个节点，链表长度加一，删除减一。
- 由于涉及到数据结构链表，为了学习优秀的代码方式，学习链表的操作方式，将对增删改查依次分析源码。
- add()源码解读，见源码注释
public boolean add(E e) {//添加元素
linkLast(e);//下面介绍
return true;
}
/**
* Links e as last element.
*/
void linkLast(E e) {//将添加的元素链接到链表尾部
final Node<E> l = last;//last表示尾部节点
final Node<E> newNode = new Node<>(l, e, null);//构造一个新节点，该节点上一个元素为l，下一个元素为空
last = newNode;//最后一个节点变为了添加的节点
if (l == null)
//此处时判断旧的最后一个节点是否为空，为空则表示链表内无数据，此时第一个节点应为添加的节点
first = newNode;
else
//不为空，则表示链表内已有数据，链接到链表尾部即可，因为欸在构造新节点时
//已经指明他的上一个节点为l，所以此处无需指定反向指向的对象
l.next = newNode;
size++; //链表长度加一
modCount++;//修改次数加一
}
- get(index)源码解读，见源码注释
public E get(int index) {
checkElementIndex(index);//判断index是否超出了范围，超出范围将抛出越界异常
return node(index).item;//该部分才是返回数据部分，返回节点的item成员，即想查询的数据对象，详见下方函数
}
private void checkElementIndex(int index) {
if (!isElementIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}
/**
* Returns the (non-null) Node at the specified element index.
*/
Node<E> node(int index) {
// assert isElementIndex(index);
//上文有提，LinkedList维护的是一个双向链表，所以在查找数据时，如果该数据位置处于
//前半段，则正向查找，处于后半段，反向查找，这样比一个单向链表更快
if (index < (size >> 1)) {
//size >> 1,size表示链表长度，size>>1表示向右移位操作，即表示size/(2的1次方)
//条件成立,正向查找
Node<E> x = first;//起始节点为头节点
for (int i = 0; i < index; i++)//循环向下查找，直到向下找index次
x = x.next;//更新x节点
return x//返回索引为index节点
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)//从尾节点反向查找
x = x.prev;
return x;
}
}
- add(index, element)，在index位置添加对象element,其他列表元素逻辑上后移一位，实际进行的是链表的插入指针地址的改变,源码解读，详情见下文源码注释。
public void add(int index, E element) {
checkPositionIndex(index);//与上文中checkElementIndex类似，不再赘叙
if (index == size)//如果index==size，即表明插入位置为最后一个节点，直接链接到链表尾
linkLast(element);//该方法与上文中add()方法一致，不在介绍
else//如果不是插在尾部，而在其他地方，则进行插入操作
linkBefore(element, node(index));//此时传入的是要插入的对象element，和此时链表中index位置的节点，node(index)上文get()方法中已有解释，具体插入见下方linkBefore解释
}
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev;//pred为原链表的index处节点上一个节点
final Node<E> newNode = new Node<>(pred, e, succ);//利用插入对象e构建新节点，可知新节点的下一个节点为
//原链表的index处的节点succ，他的上一个节点为pred,此时我们只需要指定pred的下一个节点为新节点，succ上一个节点为新节点，即可完成插入
succ.prev = newNode;//succ上一个节点为新节点
if (pred == null)//pred为空，则代表链表中无数据，待插入节点为头节点
first = newNode;
else//否则，指定pred的下一个节点为新节点
pred.next = newNode;
size++;
modCount++;
}
- remove(index),移除位于index位置处的元素，底层链表为移除位于index处的节点，源码及其个人解释见下文代码注释。
public E remove(int index) {
checkElementIndex(index);//判断index是否超出了范围，超出范围将抛出越界异常,上文已有介绍
return unlink(node(index));//node(index)表示处于index位置的节点，上文已有介绍
}
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;//element待删除节点的内容
final Node<E> next = x.next;//next表示待删除节点下一个节点
final Node<E> prev = x.prev;//待删除结点上一个节点
//由以上三个变量可知，我们只需要将next和prev进行链接即可，
//即prev.next=next,next.prev=prev即可完成插入操作.
if (prev == null) {//如果prev为空，则表示待删除节点为头节点，此时应将next变为头节点
first = next;
} else {
prev.next = next;
x.prev = null;//此处逻辑上不置空也可以，但此时x节点仍旧指向链表，虽然不影响遍历等操作
//个人认为此处置空则可以对该节点进行垃圾回收，不置空则不行
}
if (next == null) {如果next为空，则表示待删除节点为尾节点，此时应将pred变为尾节点
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;//链表长度减一
modCount++;//链表修改次数加一
return element;//返回已删除节点的内容
}