LinkedList 源码分析
1. 成员变量
transient int size = 0;
/**
* Pointer to first node.
* Invariant: (first == null && last == null) ||
* (first.prev == null && first.item != null)
*/
transient Node<E> first;
/**
* Pointer to last node.
* Invariant: (first == null && last == null) ||
* (last.next == null && last.item != null)
*/
transient Node<E> last;可以看到,共3个成员变量,一个代表存储的元素容量,一个指向第一个节点,一个指向最后一个节点.
两个节点默认情况下为null.
2. 构造方法
a. 无参构造
啥都没做.
b. 有参构造
将Collection集合添加到此List中.
addAll方法下面再分析.
3. 添加元素
可以看到,add方法传入一个元素,然后直接调用了linkLast方法将此元素加入到了List的最后.
Node类组成如下:
可以看到,是一个双向链表,存储的是原对象.
linkLast方法,将传入的元素添加至链表的最后一个元素.
首先声明了一个新的l变量,并将指向链表最后的引用last赋值给它,同时new了一个新节点,新节点pre指向l,也就是上一个节点,next指向null,因为它就是最后一个节点.
将last指向新创建的节点,也就是newNode.
接下来判断l的值,如果l为空代表这个节点是这个链表第一个添加的元素,也就是头节点,那么将firtst也指向它.否则将上一个节点,也就是之前的last节点的next指向新节点.
最后将size++即完成了一个元素添加到末尾.
addLast(),addfirst()方法同理.
4. 移除元素
a. remove(int)
首先我们看remove(int)方法,删除指定位置的元素.
先检查元素索引是否有效.
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}一个对索引值很简单的判断,如果无效则抛出IndexOutOfBoundsException异常.
然后执行了unlink方法,执行前得先找到对应的元素在链表中的位置,通过node方法.
如上,这里的源码,做了一点小小的优化,就是判断这个元素的位置在上半部分还是在下半部分,如果在上半部分,从头开始遍历,否则从尾部开始往上遍历.
unlink方法如上,首先拿到这个要删除的元素的内容,以及拿到它的next和pre.
如果它的pre为null,则表示这个要被删除的节点之前就是头节点,那么把它的next节点指定为first节点.
否则就将pre的下一个节点指向next节点.如下示意图,比如我们要删除b节点.
最后执行上面代码后
此时b与前半部分分离.
随后删除后半部分,先检查next是不是空.
如果是空表示它就是最后一个节点,让last节点指向它的上一个节点.
如果不为空,则将下一个节点的pre指向pre,且让当前要删除的节点的next指向null
这样就把b节点从链表中删除了.
很多将节点指向null主要是为了帮助GC
最后将size--
然后返回删除的元素
b. remove(Object)
直接传入对象其实与传入索引差不多,首先也是先找到指定元素,然后unlink
第一个循环我们可以看出来,LinkedList可以存储null,第二个循环则是根据equals方法去判断,找到则直接unlink,然后return了.
5. offer(Object)和poll()
通常我们可能会把LinkedList当作链表用,使用offer和poll会比较多
offer(Object)方法就不多说了,与上面的add方法相同.
poll()方法,是取出队列第一个,并将其从队列中移除.
如上可以看到,首先拿到了first指向的节点,在判断它是不是null,也就是判断是不是空的链表,是null直接返回null,不是则调用unlinkFirst(Node)将其移除.
如上,由于调用前已经对f判空了,这里源码里面将第一行注释了.
然后拿到第一个节点对应对应的对象,在用next指向下一个节点.
再将f和f.next指向null,用于帮助GC.
将first指针指向next指针,因为第一个已经被移除了,所以下一个对象成了第一个.
再判断next指针是不是为空,如果为空,表示则是一个空链表了,那么将last的值也置为null
不为空的话,就将下一个指针(新的头节点)的pre指向null,最后size--,返回即完成.
6. addAll(int, Collection)
addAll方法会将一个Collection集合添加到指定的位置后面,如果未指定位置,则在末尾添加.
前置工作,首先检查索引的合法性
随后将待添加的Collection集合转换为Object数组,再获取待添加数组的大小,如果为0则不添加,直接返回false.
下面继续判断index是否等于size,等于则表示直接再末尾添加,否则表示从中间插入.
如果等于,将succ置空,将pred置为最后一个元素.其中pred代表前一部分的结束,succ代表后一部分的开始.我们插入的集合就在pred和succ之间.
否则先再链表中找到索引为index的节点,赋值给succ,将pred赋值为succ的上一个节点.
接下来就开始循环的插入节点.
每次循环,都会new一个新节点,将集合中的值封装到新的Node节点中,并且指定next指向null,pre指向pred.
如果发现pred为null,则表示当前插入这个节点为第一个节点,也就是再头部插入,那么直接把first指向这个新节点.
否则的话将pred的next节点指向新节点.
最后更改pred的指向,将pred指向新节点.继续下一次循环.
循环结束后,判断succ是否为null,如果为null,我们是在末尾添加的,那么需要将last引用指向pred(最后插入的节点).
如果不为null表示我们是在中间插入了集合,那么我们只需要将pred也就是我们最后插入的节点的next指向succ,同时改变succ的pre的指向即可.
