集合之LinkedList源码分析
转载请注明出处:http://www.cnblogs.com/qm-article/p/8903893.html
一、介绍
在介绍该源码之前,先来了解一下链表,接触过数据结构的都知道,有种结构叫链表,当然链表也分多种,如常见的单链表、双链表等,单链表结构如下图所示(图来自百度)
有一个头结点指着下一个节点的位置,a1节点又存储着a2节点的内存位置….,这样就构成了一个单链表形式,下面看一下双链表的结构
相比于单链表结构,双链表的每个节点多存储了一个数据,就是它的前一个节点的内存地址,链表和数组的区别如下
1、链表的内存不一定是连续的,而数组的内存地址一定是连续的
2、链表的增删操作快,数组的查询操作快。
3、数组一旦开辟了内存地址,基本上大小是固定的,而链表的大小却不固定。
而这篇博文所介绍的java类就是一个链表式结构,而且是一个双向链表,下面呢,就围绕着它的使用来进行分析,说起一个数据结构的操作,无非就是增删改查,接下来来看下该类的源码设计
二、链表设计
如果不先看源码,让我们自己来设计一个功能相对简单的双向链表,那思路该如何,学过面向对象的应该很快就知道,要设计链表,而链表又是由每个节点构成,那么就设计一个内部节点类,让它来表示每个节点,属性呢,按照常规操作,那肯定有该节点值,该节点的前一个节点,该节点的下一个节点,再配上该类的构造函数,如下面的代码
1 private static class Node{//为了简单,这里没使用泛型,仅以int型代表该节点值得类型 2 int val; 3 Node pre; 4 Node next; 5 public Node(int val, Node pre, Node next) { 6 super(); 7 this.val = val; 8 this.pre = pre; 9 this.next = next; 10 } 11 12 }
很简单,一个内部类设计完成,考虑完每个节点后,那接下来肯定是考虑整个链,那肯定要写一个类,该类含有内部类Node,至于属性,因为这是双链表,那肯定有头结点,尾节点,还有链表的长度所以很容易就得到下面这段代码
1 public class LinkedList { 2 private Node first;//头结点 3 private Node last;//尾节点 4 private Node size;//链表长度 5 6 7 private static class Node{ 8 int val; 9 Node pre; 10 Node next; 11 public Node(int val, Node pre, Node next) { 12 super(); 13 this.val = val; 14 this.pre = pre; 15 this.next = next; 16 } 17 18 } 19 }
既然我们设计出来这个类,那肯定是要用它,用一个数据结构,就像前面说的,就是增删改查。
2.1、增加
这里只是简单的介绍下,增加过程。对于增加节点,可以大致分为这几类
1、在原头结点前增加节点
2、在原尾节点前增加节点
3、在头结点和尾节点之间增加节点
其中的2和3,相信诸位都见得多,那对于1怎么进行处理呢,继续看下去
1、若我们是第一次增加,此时头结点和尾节点都是null,那么很简单,直接用增加的节点去同时赋给头结点和尾节点
2、若不是第一次增加,我们要把结点添加到头结点之前,首先呢,肯定要获取头结点,具体逻辑如下。
1 public void addHeadNode(Node node){ 2 //将头结点引用赋给临时节点,避免直接操作first变量 3 Node temp = first; 4 if(temp == null){//表示第一次添加 5 first = node;// 1 6 last = node;//头结点都为null,那last节点肯定也为null,所以同时赋值给尾节点 7 }else{ 8 temp.pre = node;//将原头结点的pre指针指向添加节点 9 node.next = temp;//将添加节点的next指针执行原头结点, 10 first = node;//将添加节点赋给头结点 ,2 11 } 12 size++;//链表长度+1; 13 }
对于以上代码,标记1和2的两行代码其实可以合并的。这里为了好判别,就区分开来了
那对于类型2,原理和类型1差不多,不做过多解释,代码,如下
1 public void addLastNode(Node node){ 2 Node temp = last;//临时节点 3 if(temp == null){//第一次添加 4 first = node; 5 last = node; 6 }else{ 7 temp.next = node;//将原尾节点next指针执行添加节点 8 node.pre = temp;//将添加节点的pre指针执行原尾节点 9 last = node;//将添加节点设为尾节点 10 } 11 size++;//链表长度+1 12 }
对于类型三,相比1和2,要稍微复杂一点,不过其实也差不多,将该种类型拟作类型2,无非就是后面多了节点,语言好像描述不太清楚,大家清楚那个意思就行,如下面这个逻辑
有链表a->b->c->d,(额!这个是双向链表,表达式没体现出来),闲杂要在b和c直接插入节点e,那么肯定是用一个临时变量来替换c节点,如f=b.next,以此来保证该节点不被丢失,千万不能直接b.next=e,这样会丢失c后面的节点。之后就基本和类型2一样,最后再做一个e.next = f,f,pre = e,保证节点的通畅性。代码如下
1 //preNode代表要在该节点后插入node节点 2 public void add(Node preNode,Node node){ 3 //这里不作校验,(本来是要做些preNode是不是不·存在或啥的校验) 4 Node nextNode = preNode.next; 5 //下面这两行代码是用来preNode和node节点的连通性 6 preNode.next = node; 7 node.pre = preNode; 8 9 //这两行代码是保证node节点和nextNode节点的连通性 10 node.next = nextNode; 11 nextNode.pre = node; 12 13 size++; 14 }
2.2、删除
那对于链表的删除操作呢,也可以类似增加一样,把它分成三类
1、删除原有的头结点,并返回删除节点值。
2、删除原有的尾节点,并返回删除节点值。
3、删除头结点和尾节点之间的某一个节点值。
原理和增加类似,不过多叙述,直接上代码
1 //删除头结点 2 public int deleteFirstNode(){ 3 Node temp = first; 4 int oldVal = temp.val; 5 Node next = temp.next; 6 if(temp == null){//说明该链表没有节点 7 throw new RuntimeException("the class do not have head node"); 8 } 9 first = next; 10 first.pre = null; 11 if(next == null){//若条件满足,则表示链表只有一个节点,即first==last为true; 12 last = null; 13 }else{ 14 temp = null; 15 } 16 size--; 17 return oldVal; 18 } 19 20 //删除尾节点 21 public int deleteLastNode(){ 22 Node temp = last; 23 int oldVal = last.val; 24 Node pre = temp.pre; 25 if(temp == null){//说明该链表没有节点 26 throw new RuntimeException("the class do not have last node"); 27 } 28 last = pre;//把原尾节点的前一个节点作为尾节点 29 if(pre == null){//只有一个节点 30 first = null; 31 }else{ 32 temp = null; 33 } 34 size--; 35 return oldVal; 36 } 37 38 //删除头结点和尾节点之间的某个节点,pre为node节点的前一个节点 39 //这里也不考虑一些特殊情况,也就是删除节点一定在两节点之间 40 public int delete(Node pre,Node node){ 41 int oldVal = node.val; 42 Node next = node.next; 43 //构建node前后节点之间的连通性 44 pre.next = next; 45 next.pre = pre; 46 47 node = null; 48 return oldVal; 49 }
2.3、修改
这个操作,很简单,找到该节点,将该节点值设为新值即可,寻找过程不像数组那样可以直接定位下标,这个寻找过程要做链表的遍历操作,代码如下
1 //true代表设值成功,false为设值失败 2 public boolean set(int oldVal,int newVal){ 3 Node temp = first; 4 while(temp != null){ 5 if(temp.val == oldVal){ 6 temp.val = newVal; 7 return true; 8 } 9 temp = temp.next; 10 } 11 return false; 12 }
2.4、查找
查找和修改类似,只是少了设值这一操作,代码如下
1 //返回查找的节点 2 public Node find(int val){ 3 Node temp = first; 4 while(temp != null){ 5 if(temp.val == val){ 6 return temp; 7 } 8 temp = temp.next; 9 } 10 return null; 11 }
其实细心的可以发现,要是相同值怎么办,说实话,在这里只会查找到距离头结点最近的节点,若是用了泛型,则可以对泛型里的类型重写hash和equals方法来尽量保证唯一性。
——————————————————————————————————————–分界线————————————————————————————————————————————————————-
上面叙述了一大堆关于自己实现双向链表的操作,那下面来看看jdk源码怎么实现的。
三、源码分析
关于源码分析,对于和前面设计类似的原理,避免啰里啰嗦,就一笔带过
3.1、增加
关于LinkedList的增加方法,有多个增加
如左图,第一个和第二个是该类的构造函数,后面三个方法的作用域是private、protected、protected,作用分别为,
1、在头结点前增加节点
代码也很比较简洁,和之前设计的代码类似,不过多叙述,原理类似,至于modCount的作用,请翻阅之前的一篇博客集合之ArrayList的源码分析
1 private void linkFirst(E e) { 2 final Node<E> f = first; 3 final Node<E> newNode = new Node<>(null, e, f); 4 first = newNode; 5 if (f == null) 6 last = newNode; 7 else 8 f.prev = newNode; 9 size++; 10 modCount++; 11 }
2、在尾节点后增加节点
1 void linkLast(E e) { 2 final Node<E> l = last; 3 final Node<E> newNode = new Node<>(l, e, null); 4 last = newNode; 5 if (l == null) 6 first = newNode; 7 else 8 l.next = newNode; 9 size++; 10 modCount++; 11 }
3、在头结点和尾节点之间添加节点
1 void linkBefore(E e, Node<E> succ) { 2 // assert succ != null; 3 final Node<E> pred = succ.prev; 4 final Node<E> newNode = new Node<>(pred, e, succ); 5 succ.prev = newNode; 6 if (pred == null) 7 first = newNode; 8 else 9 pred.next = newNode; 10 size++; 11 modCount++; 12 }
至于右图,是该类暴露给其他类中使用的。但最后都调用了上述三个方法之一来完成增加操作
经常使用的add(E)方法是默认添加在尾节点后的,
对于add(int,E)方法要注意一下,按照我们正常猜想,先是直接遍历该链表,找到某个节点,在该节点之后插入新节点,但是!!!,这里并不是这样的,它是类似数组那样直接在某个位置插入,别慌,先来贴下代码
1 public void add(int index, E element) { 2 checkPositionIndex(index);//检查index的正确性 3 4 if (index == size)//即在尾节点后插入 5 linkLast(element); 6 else 7 linkBefore(element, node(index));//注意这里的node(int)方法 8 } 9 10 11 Node<E> node(int index) { 12 // assert isElementIndex(index); 13 14 if (index < (size >> 1)) { 15 Node<E> x = first; 16 for (int i = 0; i < index; i++) 17 x = x.next; 18 return x; 19 } else { 20 Node<E> x = last; 21 for (int i = size - 1; i > index; i--) 22 x = x.prev; 23 return x; 24 } 25 }
可以看到node方法里的操作,相比之前直接从头结点遍历链表的效率要高一点,有点类似折半查找,找到对应的节点,之后操作类似
3.2、删除
和增加方法一样,左图的三个删除方法是核心,右边的删除是暴露给其他方法中使用的,原理和前面说的类似,其中右图最后两个方法是怕有两个相同的obj,所以分了下类,从头结点开始找,和从尾节点开始找,找到了即删除。
其中remove()默认的也是移除头节点
3.3、修改
该类只有这一个方法,
其中也是先利用node方法查找index对应的节点,然后设值。并返回
3.4、查询
其中get(int)也是利用了node方法来查找对应的node节点
3.5、小结
对于LinkedList的其他方法,这里不作介绍,我们平时用该类也是围绕着增删改查来用,所以这里只介绍这四类。
4、和ArrayList的比较
一、它们的数据结构不一样,ArrayList的结构是数组,LinkedList的结构是链表,所有它们的内存地址排序不一样,一个是连续的,一个非连续
二、理论上,ArrayList的长度最大为Integer.MAX_VALUE,而链表的长度理论上无上限
三、ArrayList的增删慢,查询快,LinkedList的增删快,查询慢,两者恰好相反
四、两者都可以添加null元素,且都可以添加相同元素
五、两者都有线程安全性问题
5、最后
对于该类,我认为只需要了解它内部的增删改查原理,它的数据结构,它和ArrayList的区别即可。
若有不足或错误之处,还望诸位指正