中国建设银行车主卡网站,科技馆,推广之家,中国建设银行手机appJavaScript中怎么实现链表#xff1f; 学习数据结构的的链表和树时#xff0c;会遇到节点#xff08;node#xff09;这个词#xff0c;节点是处理数据结构的链表和树的基础。节点是一种数据元素#xff0c;包括两个部分#xff1a;一个是实际需要用到的数据#xff1b…JavaScript中怎么实现链表 学习数据结构的的链表和树时会遇到节点node这个词节点是处理数据结构的链表和树的基础。节点是一种数据元素包括两个部分一个是实际需要用到的数据另一个存储下一个节点位置。 链表是一系列节点串联形成的数据结构链表存储有序的元素集合链表中的元素在内存中并不是连续放置的。每个元素由一个存储元素本身的部分和一个指向下一个元素的链接部分组成。因此链表增删非首尾元素时不需要移动元素只需要更改链接部分的值即可。 在此仅看单链表单链表每个节点的结构如下 单链表在这种类型的数据结构中任何两个数据元素之间只有一个链接参见下图 链表的操作包括了创建、删除、插入、输出等。 创建就是空间的分配将头、尾指针及链表结点个数等初始化。删除和插入根据被操作元素的位置可以细分为头删除插入尾删除插入中间删除插入。
插入操作
头插入实际上是增加一个新节点然后把新增加的结点指针指向原来头指针指向的元素再把头指针指向新增的节点。 尾插入也是增加一个新节点该节点指针置为null然后把原尾结点指针指向新增加的节点最后把尾指针指向新增加的节点即可。 中间插入稍复杂首先增加一个节点然后新增节点的指针指向插入位置的后一个节点把插入位置的前一个节点指针指向新插入节点即可。 删除操作
删除头元素时先将头指针指向下一个节点然后把原头结点的指针置空即可。 删除尾元素时首先找到链表倒数第2个元素然后把尾指针指向这个元素接着把原倒数第2个元素的指针置空。 删除中间元素相对复杂一些首先将要删除的节点的前一个节点指针指向要删除的节点的下一个节点然后把要删除节点的指针置空。 上面提到是单链表最基本的操作除此之外还有其它操作不多说了。下面给出代码示例。
在 JavaScript中我们怎么实现链表呢
现在以单链表的建立和遍历为例介绍。项目结构如下 SingleLinkedList.js文件内容如下
//定义单向链表的节点类
class Node{constructor(data){this.data data //节点的数据部分this.next null //节点的链接部分(指针部分) }
}
//定义单向链表类
class SingleLinked{ constructor(){this.size 0 //单链表的长度用来记录链表中的节点个数为一个空链表this.head new Node(head) //是链表的头指针记录链表的起始地址this.currentNode //用来记录当前节点}//获取链表的长度getLength(){return this.size}//判断链表是否为空isEmpty(){return this.size 0 //如果this.size为0则说明链表为空即返回true}//遍历链表:不重复的访问链表中的每一个节点displayList(){var list var currentNode this.head //指向链表的头指针while(currentNode){ //若当前节点不为空则执行循环listcurrentNode.data //连接节点的数据域currentNode currentNode.next //让当前指针指向当前节点的下一个节点if(currentNode){ //如果currentNode不为空则加上连接符list - //链表节点的连接符}}console.log(list)}//获取链表的最后一个节点findLast(){var currNode this.headwhile(currNode.next){ //若当前节点的next域为空则他是链表的最后一个节点跳出循环currNode currNode.next //若当前节点的next域不为空则让指针指向当前节点的下一个节点}return currNode}//采用尾插法给链表插入元素appendNode(element){var currNode this.findLast() //找到链表的最后一个节点var newNode new Node(element) //创建一个新的节点currNode.next newNodenewNode.next nullthis.size //链表的长度加1}//删除链表中的一个节点delete(element){//this.displayList()var currentNode this.headtry{while((currentNode.next!null)(currentNode.next.element!element)){ //判断如果节点靠后则节点的next的next为空不为空时进行删除if(currentNode.next.data element){currentNode.next currentNode.next.next this.size--}else{currentNode currentNode.next}}}catch(e){ //测试函数判断函数的运行错误console.log(e)}}
}测试代码内容如下我这里保存文件名为 单链表测试.html将此文件和SingleLinkedList.js放到同一目录中
script src./SingleLinkedList.js/scriptscript //不能写在有js代码的JavaScript中var slist new SingleLinked()console.log(slist.isEmpty()) //打印链表是否为空若为空则输出trueslist.appendNode(1001) //创建链表节点slist.appendNode(1002) //创建链表节点//创建链表更多节点var arr [1020,1234,1006,788,5512]for(var i0;iarr.length;i){slist.appendNode(arr[i])}//遍历输出链表slist.displayList()//删除链表中的1006元素slist.delete(1006)slist.displayList()
/script用浏览器打开 单链表测试.html按下F12键单开控制台查看结果 更多情况可见https://segmentfault.com/a/1190000017970029
