大家好,又见面了,我是你们的朋友全栈君。
其实无论在任何语言中,一种数据结构往往会有很多的延伸和变种以应对不同场景的需要。其实前面我们所学过的栈和队列也是可以用链表来实现的。有兴趣的小伙伴可以自己尝试着去实现以下。
有点跑题了…,我们还是说回链表,在基础链表之外,还有双向链表和循环链表和双向循环链表。这篇文章会详细的介绍一下双向链表,但是不会详细的去讲解循环链表。因为其实真的没有太大的区别。链表和循环链表的唯一的区别在于,最后一个元素指向下一个元素的指针不是null,而是head。
其实循环链表只能从头到尾的循环,而双向循环链表可以两个方向循环,想怎么玩怎么玩。
嗯…又跑题了,我们还是来说双向链表吧。
顾名思义…双向链表就是….双向链表!额…开个玩笑…咱们进入正题吧….
其实简单说双向链表与链表的区别就在于,双向链表不仅仅有一个指向下一个节点元素的指针,还同时拥有一个指向上一个节点元素的指针。前后都可以链接,故,称之为双向链表。
那么既然是双向的指针,所以我们的代码需要新增一些东西。
由于双向链表内的一些方法与链表无异,所以这里只说明一下那些区别明显有重要意义的地方。不再贴上所有的代码。
function DoublyLinkedList() { let Node = function (element) { this.element = element; this.next = null; //在双向链表中,这里多了个指向前一个节点元素的指针prev this.prev = null; } let length = 0; let head = null; //同样的这里多了一个保存链表最后一项节点的引用变量,为什么要加这个变量? //因为是双向链表,普通链表只能从头到尾的迭代各节点元素,一方面是因为普通链表中只有一个存储头部节点元素的head变量。 //但是双向链表可以从尾部开始迭代,这就是tail的意义。 let tail = null; }
这就是双向链表的类的变动(不包括其中的方法),我们可以看到只是多了node节点元素中prev(前一个)节点元素的指针,还有tail变量对尾部节点元素的引用。
那么下面我们来看看insert方法的变化。
//我们来看看双向链表中insert方法,普通链表中,我们只需要控制next指针就可以了,但是在双向链表中,在控制next指针的同时,我们还要控制prev指针 this.insert = function (position,element) { //在普通链表中在任意位置添加元素有两种情况,一个是添加到头部,另外一个是除了头部以外的其他位置, //在双向链表中除了这两种情况,还多了一种,添加在链表尾部 if(position >= 0 && position <= length) { let node = new Node(element); let current = head; let previous; let index = 0; //添加到头部的情况 if(position === 0) { //这里,如果head为null,也就是说该链表是没有任何节点元素的情况,那么加入的这个节点元素在链表中是唯一的 //所以,head引用为node,tail的引用也为node if(!head) { head = node; tail = node; //那么如果,head不为null,说明链表中存在至少一个元素。 } else { //由于current就是head,那么要插入节点元素的话只要把node的next指针指向current,就说明我们在current前面插入了该节点元素。 node.next = current; //因为是双向列表,我们还要给current.prev一个指向。 current.prev = node; //那么既然我们在current前面插入了元素,这里也就要改变head的引用,变为我们插入的node head = node; } //如果我们想要插入尾部的情况 } else if(position === length) { //这里稍微有趣一点,这里我们要在尾部加入元素,不用像普通链表那样迭代到最后一项再操作。 //我们只需要把current直接置为tail的引用就可以了,方便快捷 current = tail; //那么我们已经拿到了最后一项节点元素的引用并且设置为了current。 //我们只需要把current(tail)的next指向node节点元素,并且把node的prev只想current。 //其实就是说,current节点的next指针不再是null了,因为我们在它的后面增加了一个“插入元素”,所以它的next指针为node //而此时node的prev指针也就理所当然的指向了current。 current.next = node; node.prev = current; //插入元素完成,但是我们此时的tail其实是current不是node,所以更改一下tail的引用。 tail = node; } else { while(index++ < position) { //依次往后移动...不多说 previous = current; current = current.next; } //在移动到需要插入节点元素的位置时。 //我们要插入在current的前面,自然就会有下面的结果了 node.next = current; previous.next = node; //但是我们由于是双向链表,我们不仅仅要修改next指针,还要修改prev指针 current.prev = node; node.prev = previous; } length++; return true; } else { return false; } }
其实insert方法在双向链表中,只是多了一种尾部情况的判断以及prev指针的改变,注释已经说的很详细了,不多说废话,我们继续看看removeAt方法在双向链表中的实现。
this.removeAt = function (position) { if(position > -1 && position < length) { let current = head,previous,index = 0; if(position === 0) { head = current.next; if(length === 1) { tail = null } else { head.prev = null; } } else if(position === length - 1) { current = tail; tail = current.prev; tail.next = null; } else { while(index++ < position) { previous = current; current = current.next; } previous.next = current.next; current.next.prev = previous; } length --; return current.element; } else { return null; } }
这是双向链表的removeAt方法,我不想解释了,因为我觉得如果你认真的阅读了这两篇文章,这个方法你绝对可以看懂了。如果你还是看不懂,请从头再来!
这里我们就基本介绍完了双向链表…等等…不是还有其它的方法么?怎么不说了?
insert可以在任意位置插入元素,removeAt可以在任意位置移除元素,想要实现其它方法就不难了吧。。。。。再说下去也是重复前面说过的内容了。实在无须如此….
那么我们对于链表的了解就告一段落,下一篇文章我们一起来看看集合这个东东。感觉会比链表好玩一些。嗯…对,跟数学中的集合有关系。
最后,由于本人水平有限,能力与大神仍相差甚远,若有错误或不明之处,还望大家不吝赐教指正。非常感谢!
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/124425.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...