数据结构与算法-循环链表(js实现)
程序员文章站
2024-01-23 21:15:46
...
循环链表和单向链表很相似,唯一的区别是,循环链表的尾节点是指向头节点的,例如下面这样的结构
可以将其理解为一个环形结构,没有头没有尾,很适合做一些无限循环的东西,比如轮播图
循环链表的代码实现
我们只需要在单向链表的基础上稍加改造即可完成循环链表的实现(点击进入单向链表的实现详解)
/************节点*************/ function Node(element) { this.element = element;//当前节点的数据 this.next = null;//下一个节点数据 } /*************************链表*****************************/ function LList() { this.head = new Node("head");//头节点 this.head.next=this.head;//注意这里 } LList.prototype={ //查找某一节点 find:function (item) { var currNode = this.head; while (currNode.element != item) { currNode = currNode.next; if (currNode==this.head)return null; } return currNode; }, //查找尾节点 findLast:function(){ var currNode = this.head; while (!(currNode.next == this.head)) { currNode = currNode.next; } return currNode; }, //向某一元素后面插入新节点 insert:function(newElement,item){ var newNode = new Node(newElement); var current = this.find(item)||this.findLast();//默认插入到尾部 newNode.next = current.next; current.next = newNode; }, //查找某一节点的前一个节点(前驱) findPrevious:function(item){ var currNode = this.head; while (!(currNode.next == this.head) &&(currNode.next.element != item)) { currNode = currNode.next; } return currNode; }, //删除某一个节点 remove:function(item){ var prevNode = this.findPrevious(item); if (!(prevNode.next == this.head)) {//不能删除头 prevNode.next = prevNode.next.next; } }, //修改某一节点的数据 edit:function(item,newItem){ var element=this.find(item); element.element=newItem; }, //在控制台打印出所有节点(为了方便预览) display:function(){ var currNode = this.head; while (!(currNode.next == this.head)) { console.log(currNode.next.element); currNode = currNode.next; } } }测试
插入四个节点
var lkk=new LList; lkk.insert("likek"); lkk.insert("zhangsan"); lkk.insert("lisi","zhangsan");//指定插入位置 lkk.insert("haha");查看当前所有节点的情况
lkk.display(); /*likek zhangsan lisi haha*/删除节点
lkk.remove("zhangsan"); lkk.display(); /*likek lisi haha*/
上一篇: web性能优化_(转载文)