Java之LinkedList源码分析（第三篇：添加元素-List接口）
（注意：本文源码基于JDK1.8）
LinkedList添加元素的方法太多了……，本篇从List接口中定义的添加元素方法做一个分析
传入一个参数类型E的add（）方法分析
public boolean add(E e) {
linkLast(e);
return true;
}add（E）方法是LinekdList中最常用的添加元素的方法
1、将传入的元素对象e，再传入到实际进行添加元素的方法中
实际调用linkLast（）方法，将元素插入，元素会插入到双向链表的尾部
2、返回值为true，表示LinkedList添加一个元素成功
linkLast（）方法分析
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}实际向双向链表尾部添加一个元素的方法，无返回值，传入的参数e表示要添加的元素对象
1、保存当前双向链表的最后一个元素到局部变量中
首先将LinkedList对象持有的实例变量last，赋值给局部变量l保存，last指向的是双向链表的最后一个结点对象（结点对象中持有的元素）
2、创建一个Node对象，用于持有传入的元素对象e，并赋值给一个局部变量保存
通过new创建一个Node对象，Node的构造方法需传入3个参数，局部变量l表示的尾节点、元素对象e、以及一个null值，新创建的Node对象会赋值给一个局部变量newNode负责保存
PS：局部变量l与局部变量newNode都用final修饰，这是为何？
3、更新双向链表的尾节点为新创建的Node对象
将实例变量last指向新创建的结点对象newNode，此时新创建的结点对象成为双向链表的最后一个结点
4、处理第一次添加元素的情况
如果LinkedList是第一次添加元素，将新创建的结点对象newNode赋值给LinkedList对象持有的first，实例变量first永远指向双向链表的第一个结点对象
如果LinkedList不是第一次添加元素，则将临时保存的旧的尾结点对象l持有的实例变量next指向新添加的结点对象newNode，完成双向链表之间连接
5、更新LinkedList持有的元素总数
添加完新的结点对象，再将LinkedList持有的元素总数size值，增加1
6、fail-fast机制更新值，防止多线程下使用LinkedList
再把fail-fast机制用的modCount值增加1
Node构造方法分析
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}Node类定义在LinkedList的内部，为静态内部类，它产生的每个对象表示作为双向链表的节点对象，Node的构造方法需传入3个参数
第一个参数prev表示当前Node对象连接的上一个Node对象，第二个参数element表示当前Node持有的元素对象，第三个参数next表示当前Node对象连接（指向）的下一个Node对象
1、首先为Node对象持有的item赋值
Node对象持有的item负责保存传入的元素对象element
2、为Node对象持有的next赋值
Node对象持有的next，表示连接（指向）的下一个Node对象，这里直接将传入的next赋值给实例变量next
3、为Node对象持有的prev赋值
Node对象持有的prev表示连接（指向）的上一个Node对象，同样直接将传入的prev赋值给实例变量prev
传入两个参数的add（）方法分析
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}用于在指定位置插入元素的方法（注意：第一个位置的下标是0）
第一个参数index表示下标，第二个参数element表示插入的元素对象
1、检查下标值是否合法
首先检查下标值是否超出范围，将传入的下标index传入到checkPositionIndex（）方法中，只有符合下标要求的元素才能插入到LinkedList中
2、判断是否在双向链表尾部插入元素
符合范围的下标值，会检查元素是否为插入到双向链表的尾部，这里将下标index与元素总数size作比较，如果index与size相等则说明是要插入到双向链表的尾部，所以此时会调用linkLast（）方法完成在尾部插入元素
3、在双向链表的中间部分插入元素
如果元素不是插入到尾部，那一定是插入到中间的元素，此时先将下标index传入到node（）方法中，node（）方法会返回一个指定下标index的前面或者后面的一个已经存在的Node对象，最后再将即将要插入的元素对象element与node（）方法返回的Node对象，作为参数一并传入到linkBefore（）方法中，由linkBefore方法完成最终的插入
checkPositionIndex（）方法分析
private void checkPositionIndex(int index) {
if (!isPositionIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}用于检查下标index是否在有效范围内的方法
1、将传入的下标index传入到isPositionIndex（）方法中
2、不符合要求抛出异常告知用户
isPositionIndex（）方法的返回值若返回flase，则代表传入的下标index并不在有效的范围内，此时整个方法抛出IndexOutOfBoundsException对象，IndexOutOfBoundsException对象接受了一个outOfBoundsMsg（）方法返回的字符串！
isPositionIndex（）方法分析
private boolean isPositionIndex(int index) {
return index >= 0 && index <= size;
}用于检查传入的下标index是否符合范围
必须同时满足两个条件，才能作为LinkedList中有效范围内的下标
1、下标index必须大于等于0
2、下标index必须小于等于元素总数size
返回值true表示下标符合范围，false表示不符合范围……
node（int）方法
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;
}
}用于返回指定下标index的前面或者后面的Node对象，返回的Node对象取决于下标值更接近双向链表的头部还是尾部
按照下标index距离头结点或尾结点哪个更近，所以分出了两种情况
1、传入下标index若小于元素总数size的一半，证明index距离第一个结点更近，此时从第一个结点开始查找要插入的位置的后一个结点
将LinkedList对象持有的头结点引用first赋值给局部变量x，接着开始遍历找到符合要求的结点，比如要新插入一个元素到index等于3的位置，此时x返回的是当前index为3的结点对象（它会作为新插入结点对象的下一个结点对象而存在）
2、传入下标index若大于等于元素总数size的一半，证明index距离最后一个结点更近，此时从最后一个结点开始查找要插入的位置的后一个结点
先获得LinkedList对象持有的last并赋值给局部变量x，last总是指向双向链表的最后一个结点，接着从最后一个结点开始向前进行遍历，找到符合要求的结点，返回的x也是当前位置index的结点对象（它同样也是作为新插入结点对象的下一个结点对象而存在的）
linkBefore（）方法分析
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}用于将一个新的结点对象插入到某一个结点对象的前面，传入的局部变量e代表插入的元素对象，传入的局部变量succ代表新插入结点对象连接（指向）的下一个结点对象
1、首先将传入的结点对象succ持有的prev赋值给局部变量pred（局部变量pred连接（指向）的结点将会成为新插入结点对象连接（指向）的上一个结点）
2、接着会创建一个新的结点对象，这是通过Node的构造方法完成的（见2号知识点），它接受三个参数，第一个是它指向的上一个结点对象、第二个是要插入的元素对象，第三个是它指向的下一个结点对象，最终新创建的对象会被赋值给局部变量newNode负责持有
3、将结点对象succ持有的prev连接（指向）新插入的结点对象newNode（succ结点是新插入结点对象连接（指向）的下一个结点）
4、如果新插入的是第一个结点，则将first连接（指向）到结点对象newNode
5、不是第一个结点对象的话，将结点对象pred的next连接（指向）到新插入的结点对象newNode
最后元素总数size加1，modCount增加1，代表结点的插入已经完成
outOfBoundsMsg（）方法分析
private String outOfBoundsMsg(int index) {
return "Index: "+index+", Size: "+size;
}负责返回异常字符串的方法，它会将传入的下标index与其他字符串共同组成一个新的字符串，我们看到的异常信息，就是这个方法返回的字符串
addAll（Collection）方法分析
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}负责将集合中的所有元素添加到LinkedList对象持有的双向链表中，传入的Collection对象c会被传入到addAll方法中
addAll（int，Collection）方法分析
public boolean addAll(int index, Collection<? extends E> c) {
checkPositionIndex(index);
Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0)
return false;
Node<E> pred, succ;
if (index == size) {
succ = null;
pred = last;
} else {
succ = node(index);
pred = succ.prev;
}
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
Node<E> newNode = new Node<>(pred, e, null);
if (pred == null)
first = newNode;
else
pred.next = newNode;
pred = newNode;
}
if (succ == null) {
last = pred;
} else {
pred.next = succ;
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
}1、首先检查下标的范围是否合法
将下标index传入到checkPositionIndex（）方法中
2、将Collection对象转为一个数组对象，并由局部变量a负责持有
3、获取数组对象a的长度，由局部变量numNew负责持有
4、传入的数组对象长度为0时，会直接返回false
5、定义两个局部变量，一个pred、一个succ、它们都是Node类型，pred代表新插入结点对象连接（指向）的上一个结点，succ代表新插入结点对象连接（指向）的下一个结点
6、index==size时，代表元素插入到双向链表的尾部，此时succ赋值为null，pred则为last
7、不是向尾部插入时，则通过node方法（）得到一个新插入结点未来连接（指向）的下一个结点对象，赋值给succ保管，接着从succ取出上一个结点，赋值给pred保存（这里只是插入多个元素，你可以把它们假装看成是一个元素）
8、接着对集合中所有元素进行遍历的连接，每个元素都会创建为一个Node对象，直到最后一个元素，此时它会成为pred
9、接着判断两种情况，一个是在尾部插入元素的情况，一个是在中间插入元素的情况，把LinkedList持有的最后一个结点更新上来
10、更新LinkedList的元素总数size
11、更新用于fail-fast机制modCount值
12、返回一个true，表示插入元素成功
总结
linkLast（）方法中的局部变量l与局部变量newNode都用了final修饰，这是为何？
本文地址：https://blog.csdn.net/cadi2011/article/details/105084700