一：摘要概述
- ArrayList继承结构讲解
- ArrayList实现数据结构与初始化时间
- ArrayList数组扩容策略
- ArrayList插入操作
- ArrayList遍历操作
- LinkedList数据结构
- LinkedList继承结构
- LinkedList遍历操作
- LinkedList结构变更效率
- Vector线程安全保证
二：ArrayList继承结构
ArrayList作为集合中常用的类,归属于Collection下List实现子类。其特殊的实现接口有RandomAccess、Cloneable
2.1 RandomAccess
该接口为空实现标志接口,具体的用处在Collections工具类中211行方法binarySearch二分查找课件端倪。同样是遍历查找,实现了RandomAccess接口的类使用for循环遍历,其余的就用迭代器。所以这里可以引申出一个观点：
List中子类ArrayList遍历最好采用for循环,如LinkedList等未实现RandomAccess接口的子类采用迭代器进行循环遍历
2.2 Clonable
深度克隆标志性接口,实现该接口以后重写Object提供的clone()方法可以实现深度克隆。源码位置353行可以看到克隆时将数组进行了复制,并且将modCount属性置零,因为该属性标志ArrayList修改次数
三：ArrayList实现数据结构
3.1 数组实现
ArrayList中采用数组作为底层数据存储结构,这也就导致了其查询速度优越但是结构修改缓慢的特点。elementData属性就是数据存储的数组
3.2 数组初始化
elementData数组什么时候进行初始化?ArrayList提供了几种构造函数的重载,其中主要看无参构造与数组初始容量构造：
- 无参构造：elementData默认赋值常量
DEFAULTCAPACITY_EMPTY_ELEMENTDATA空数组,当调用add函数增加元素时再通过grow扩容函数进行数组初始化。数组大小使用默认初始化容量DEFAULT_CAPACITY=10 - 初始容量：直接初始化数组,数组容量大小为传入参数值
四：ArrayList数组扩容策略
ArrayList底层数组支持动态扩容,扩容策略核心代码如下所示：
private void grow(int minCapacity) {
// 计算现有数组长度
int oldCapacity = elementData.length;
// 现有数组长度增加1/2
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 扩容以后的数组容量是否满足本次元素插入最小容量需要
if (newCapacity - minCapacity < 0)
// 不满足就将本次扩容数组容量设置为插入所需最小
newCapacity = minCapacity;
// 判断数组容量超过限制最大值
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 初始化新容量数组并将原数据复制
elementData = Arrays.copyOf(elementData, newCapacity);
}
五：ArrayList插入操作
ArrayList提供了三组数据插入API,具体效果如下所示：
- add(E e)函数直接加入数组尾端
- add(int index,E e)按照index序列插入
- set(int index,E e)index位置元素覆盖
六：ArrayList遍历操作
ArrayList因为底层采用数组的方式实现,并且其父类接口也提供了Iterator迭代器方案,并且自身也对父类提供的迭代器进行了优化。但是回忆上文讲RandomAccess接口时所讲,ArrayList的遍历最好还是使用for循环进行遍历
七：ArrayList频繁结构修改效率
讲到ArrayList就会提到频繁结构修改的场景不适合ArrayList,为什么会有这个说法?查看源码remove函数亦或是add(int index,E e)都会发现System.arraycopy函数的调用。使用remove函数源码如下讲解：
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
// 第一个elementData表示源数组
// index + 1表示开始复制的坐标
// 第二个elementData表示目标数组
// index表示目标数组开始接收复制元素的位置坐标
// 比如原有数据 1 2 3 4 5
// index设置为2表示要删除第三个元素3
// 那么过程就是将第四个元素复制4到第三个元素3的位置覆盖
// 后续元素以此类推完成整个数组结构变更
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
总结起来就一句话,ArrayList的数据结构变更将会涉及到变更index后的所有元素数据。所以频繁的结构变更必然效率不高
八：LinkedList数据结构
LinkedList底层数据结构通过其内部类Node实现,Node源码如下：LinkedList是一个双向链表
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中处理List相关接口抽象类实现之外需要关注 Deque接口。双向队列接口提供了系列API,如队列操作 offer、 poll、栈操作 push、 pop
十：LinkedList遍历
前面讲解ArrayList实现RandomAccess接口后在Collections工具类中二分搜索使用for循环实现遍历,LinkedList并未实现该接口。Collections的处理是使用迭代器进行遍历,所以得知LinkedList的遍历最好使用迭代器进行
十一：LinkedList效率问题
虽然在JDK1.8中增加了中间位置的判断提升检索效率,但是还是不可避免的效率低于ArrayList
Node<E> node(int 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;
}
}
结构修改函数remove中首先通过node函数查询到对应节点后直接修改该节点前后节点指针即可。所以最大的时间消耗就在线性的节点搜索中，相比于ArrayList还是很优秀的
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
十一：Vector线程安全
Vector是List子类实现中提供的一个线程安全子类,其线程安全的保证使用Synchronized实现。查看源码可以发现它在所有方法上都使用了Synchronized修饰