List接口
List是一个接口，继承自Collection接口，其下方还有ArrayList、LinkedList、Vertor的实现类。
类图可参考：文章《Collection》
本文将记录List下实现类的源码debug流程，以及源码分析。
一、ArrayList??
1. 简介
在源码的头部注释中写道：实现自List接口，是一个可调整数组的实现，允许所有元素包括null的添加，除了实现List接口内的方法之外，还包含一些方法用于操作内部数组的大小。这个类是类似于Vertor的，但它是非同步的。当向内部添加元素的时候，它的容量可以自动增加。由于是非同步(非线程安全)的类，所以如果有多线程并发操作ArrayList实例，则可能会抛出ConcurrentModificationException(并发修改异常)异常。
从以上内容中可以得知ArrayList有几个特点：
- 内部由一个
Object数组实现 - 可以添加
null值，且可以重复 - 使用数组实现，随机查改效率高，增删效率低，因为设计了数组的扩容
- 会自动扩容
- 线程不安全：不可以并发操作此类
- 性能比
Vector高，因为没有加同步锁
2. 类核心属性
-
elementData存放数据的-
transient Object[] elementData;transient修饰，代表不可以被序列化
-
-
EMPTY_ELEMENTDATA-
private static final Object[] EMPTY_ELEMENTDATA = {};用空实例的共享空数组实例。
-
-
DEFAULT_CAPACITY初始化大小-
private static final int DEFAULT_CAPACITY = 10;默认初始容量
-
-
DEFAULTCAPACITY_EMPTY_ELEMENTDATA用作初始化的空数组-
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};elementData默认值
-
-
size当前集合长度-
private int size;集合长度
-
-
modCount用于记录被修改的次数，来自父类：AbstractList-
protected transient int modCount = 0;
-
-
MAX_ARRAY_SIZE允许的集合最大长度-
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;因为在数组类型属于特殊的数据类型，在
JVM中可能需要8个空间存储_length信息，不同的JVM平台可能不一样，为了保险起见，才将最大长度进行-8处理。
-
3. 构造方法
ArrayList有3个构造方法，分别为：
-
ArrayList()无参构造方法-
public ArrayList() { // 初始化一个空数组 就是将elementData初始化一下 this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }
-
-
ArrayList(int initialCapacity)-
public ArrayList(int initialCapacity) { // 如果传入进来的初始化大小大于0，就构建一个指定长度的数组 if (initialCapacity > 0) { this.elementData = new Object[initialCapacity]; // 如果长度等于0 就用默认的空数组 // EMPTY_ELEMENTDATA = {} } else if (initialCapacity == 0) { this.elementData = EMPTY_ELEMENTDATA; // else对应小于0 他看你不爽就抛个异常给你 告诉你值不合法 } else { throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); } }
-
-
ArrayList(Collection<? extends E> c)-
public ArrayList(Collection<? extends E> c) { // 先转一下数组，如果传了个null 他就给你个空指针 Object[] a = c.toArray(); // 有数据 if ((size = a.length) != 0) { // 是否是ArrayList类型的 if (c.getClass() == ArrayList.class) { // 是的话 直接赋值 elementData = a; } else { // 不是的话 就复制 elementData = Arrays.copyOf(a, size, Object[].class); } } else { // replace with empty array. // 和无参构造方法一致 初始化一个空数组 elementData = EMPTY_ELEMENTDATA; } }
-
4. add()方法
先说结论：当调用ArrayList的add()方法时
-
调用时，会首先调用判断内部的
elementData大小是否满足当前元素的放入，如果不满足的话，则会调用grow()方法进行数组的扩容，扩容时会计算新数组的长度，计算时分为两种情况，第一次进入的时候原数组是个空的，所以会给一个默认的长度10，第二次及以后进入，才会 * 1.5，来计算，得出新数组长度后会进行Arrays.copyOf()复制操作，将原数组赋值给新数组，并初始化至newCapacity新的容量。
为什么是1.5倍?
-
首先
1.5是由(oldCapacity >> 1计算得出) -
因为
1.5可以充分利用移位操作，减少浮点数或者运算时间和运算次数。 -
其次扩容
1.2倍未免过于太小，而2倍又太大，在权衡之下就采用1.5倍的做法。
源码：
第一步先看add(E e)方法
public boolean add(E e) {
// 确认内部大小是否可以满足当前元素的放入，参数为当前数组长度+1(也就是存放当前元素后的数组长度)
ensureCapacityInternal(size + 1); // Increments modCount!!
// 扩容完之后直接赋值就好
elementData[size++] = e;
// 返回成功
return true;
}
第二步ensureCapacityInternal()方法
-
确保内部大小足够
-
参数
minCapacity为期望的最小容量
// minCapacity 为期望的最小容量
private void ensureCapacityInternal(int minCapacity) {
// 确保内部大小，会进行数组的扩容
// calculateCapacity() 方法，确保第一次进入是有长度的
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
// 计算最小容量，确保第一次进入是有长度的
// elementData 当前数组，minCapacity 最小期望容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
// 如果数组等于空的， 备注：DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// 就给个默认大小 DEFAULT_CAPACITY = 10
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
// 如果不是空的，就返回最小大小
return minCapacity;
}
第三步ensureExplicitCapacity()方法
- 确保内部大小是足够的，并会执行扩容操作
private void ensureExplicitCapacity(int minCapacity) {
// 记录操作次数
modCount++;
// 如果期望的最小容量 - 数组当前长度 > 0
// 翻译一下就是我最少需要11个容量，数组现在有10个容量，那么是不满足我的需求的，所以需要执行grow()方法执行扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
第四步grow()方法
- 数组扩容,确保至少可以容纳
minCapacity个元素
private void grow(int minCapacity) {
// 记录当前容量
int oldCapacity = elementData.length;
// 将当前容量位移1，相当于 oldCapacity / 2
// 使用位移操作，减少浮点和加减运算，使用位移操作更快
// 获取新的容量，公式：当前容量 * 1.5
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果计算的最新容量 - 期望的容量小于0
// 检查新的容量是否大于期望的最小容量，如果小于就是用最小容量
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 检查新容量是否超出数组允许的最大容量
// MAX_ARRAY_SIZE = Integer.MAX_VALUE -8
// 因为在不同平台的JVM虚拟机中，可能会有8个容量用于保存头部信息(用于存储__length字段)，为了兼容所以规定为int最大值 - 8，以保证不会出现oom
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);
}
// 在执行第一步的 elementData[size++] = e; 即可完成添加操作
第四步的->hugeCapacity()方法
此处可能会抛出OOM异常
在方法hugeCapacity(minCapacity)内会判断，minCapacity是否小于0，但是一步一步的往上查找，发现，minCapacity的值是size + 1，那么正常情况下理解，这个参数应该是不会小于0的，那为什么要加这个判断呢?
private static int hugeCapacity(int minCapacity) {
// 为什么会小于0呢 ?
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
// 如果期望的最小容量大于允许的最大容量，就返回int最大值，否则返回允许的最大容量
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
这个地方有两个问题
-
1. 为什么最小容量会小于0
-
**2. **为什么明明最大容量是
Integer.MAX_VALUE - 8，这里还要返回Integer.MAX_VALUE呢？-
我觉得吧：因为期望的最小容量已经大于允许的容量了，所以这个规则就已经被打破了，所以此时别无选择了，只能指定为是
Integer.MAX_VALUE，总不能超过Integer.MAX_VALUE吧。
-
二、LinkedList
1. 简介
LinkedList是一个使用了双向链表实现的一个数据结构，和ArrayList有着很大的区别，同时它也是一个线程不安全的集合，可能会抛出ConcurrentModificationException。
- 使用双向链表进行实现
- 可以添加
null值 - 使用双向链表实现，不涉及扩容，增删效率高
- 随机查找需要循环，效率慢
- 不可以并发修改
2. 类的核心属性
-
first指向双向连表的头部节点-
transient Node<E> first;transient修饰不需要被序列化
-
-
last指向双向连表的尾部节点-
transient Node<E> last;transient修饰不需要被序列化
-
-
Node<E>内部结构-
/** * 双向链表的内部结构 */ private static class Node<E> { // 真正用于存储数据的节点 E item; // 下一个结点的指针 // 如果该Node==last 则next==null Node<E> next; // 上一个节点的指针 // 如果该Node==first 则prev==null Node<E> prev; Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; } }
-
3. 构造方法
LinkedList共有2个构造方法
-
LinkedList()无参构造-
public LinkedList() { }
-
-
LinkedList(Collection<? extends E> c)赋值构造-
从指定的集合类中将值赋给自身的双向链表中
-
public LinkedList(Collection<? extends E> c) { this(); addAll(c); }
-
4. add() 方法
先说结论：当调用LinkedList的add()方法时：
默认会往双向链表的尾部添加一个元素，等价于
addLast()方法。如果last属性等于null的话，则代表是第一次添加，此时将会把first属性赋值为添加的元素，否则就创建一个新节点，将last节点的next属性指向这个创建的新节点，完成双向连表的赋值和连接操作。
源码：
public boolean add(E e) {
// 实际调用了linkLast()进行添加元素
linkLast(e);
return true;
}
linkLast() 方法
- 意思为连接尾部的意思，将新节点连接到当时尾部的
next属性下
void linkLast(E e) {
// 先记录一下当前尾部指针
final Node<E> l = last;
// 创建一个新的节点，prev属性为当前的尾部节点，这样做的话就可以使链表连接起来了
final Node<E> newNode = new Node<>(l, e, null);
// 将尾部赋值给新节点
last = newNode;
// 第一次调用add()方法 last肯定是空的
if (l == null)
// 就将新节点赋值给头部节点
first = newNode;
// 不是第一次添加
else
// 就将原有的last属性内的下一个节点指向当前的新元素
l.next = newNode;
// 修改长度 +1
size++;
// 修改操作次数 +1
modCount++;
}
注：看到这个方法有没有想到，如果我添加一个null进来，头部节点会被覆盖掉吗？
答：并不会?，因为
null只是Node中item属性的值，所以l == null并不成立，所以并不会被覆盖。😜
5. add(index) 方法
- 将元素插入到指定
index的位置，如果该位置有元素的话就将其右移。
源码：
public void add(int index, E element) {
// 判断一下有没有这个下标，如果没有的话就抛出IndexOutOfBoundsException异常
checkPositionIndex(index);
// 如果插入的索引==元素长度的话(就相当于尾插)，就在尾部添加一个元素
if (index == size)
linkLast(element);
else
// 就在指定元素的头部添加当前元素
linkBefore(element, node(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;
}
}
6. linkBefore() 方法
- 意思为往头部插入元素，将内部
first属性赋值给传入元素 - 方法备注：将元素
e插入到，一定不为空的元素succ之前
源码：
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
// succ肯定不为空，记录一下succ元素的前一个元素
final Node<E> pred = succ.prev;
// 创建一个新元素，将succ的prev赋值到新元素的prev，并将succ作为新元素的next
final Node<E> newNode = new Node<>(pred, e, succ);
// 将succ的上一个元素指向 当前的新元素
succ.prev = newNode;
// 如果是第一次添加
if (pred == null)
// 直接将头部赋值给新元素
first = newNode;
else
// 将前一个元素的next指向新元素
pred.next = newNode;
// 修改长度 +1
size++;
// 修改更新次数 +1
modCount++;
}
7. 备注
在调用
iterator()方法时，会首先去校验，调用时记录的modCount是否等于自身当前的modCount，如果不等于的话则会抛出并发修改异常ConcurrentModificationException()
三、Vector
1. 简介
Vector是一个线程安全的集合类，你可以在使用iterator()方法时，调用其他修改的方法(会等待锁释放)，不会产生线程安全的问题，因为在Vector的实现方法内，基本的都被加上了synchronzied关键字修饰，iterator()方法在执行的时候更是会锁住类，其他方法执行的时候都会等待锁的释放。
- 线程安全的集合类
- 效率没有
ArrayList高，因为加了synchronzied关键字，会使线程同步，因此会影响效率。 - 底层使用
Object数组进行实现
2. 和ArrayList的区别
-
底层的扩容机制不一样，
ArrayList是扩容至自身的1.5倍，而Vector直接扩容至自身的2倍。 -
这么做的原因可能是因为：本身就添加了
synchronzied，导致效率低，所以扩容的大一些，避免了多次扩容。提升一点性能。
3. add()方法
- 可以参考
ArrayList的add()方法，除了扩容机制不一样，其它基本一致。
四、集合类选型
三种集合特性对比
-
ArrayList (90%的应用场景，推荐指数：??????????)
- 随机查询，随机修改快，可以通过索引下标直接选中
- 线程不安全，并发场景不同时修改同一对象
- 添加效率低，需要进行扩容，效率较低
-
LinkedList (根据业务需求，进行灵活使用 推荐指数：??????)
-
随机查询，随机修改效率低，需要循环比对找到对应的
Node才可以操作 -
增加删除较快，使用双向连表实现，无需考虑扩容。
-
线程不安全，并发场景不同时修改同一对象
-
-
Vector (多线程并发场景使用，并发场景推荐指数：??????????，其余场景不推荐使用)
- 修改效率最低，因为添加了
synchronzied，进行线程同步 - 并发场景时使用
- 修改效率最低，因为添加了