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